Поиск и сортировка данных в массивах
 Скачать 52.65 Kb.
|
|
Тема: поиск и сортировка данных в массивах. Методы сортировки элементов массива Сортировка пузырьком. При данной сортировке (в порядке возрастания) нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом, элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале. Пример. Пусть исходный массив имеет вид:  . Отсортируем его в порядке возрастания:  Сортировка перемешиванием (шейкерная сортировка). Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа на-лево.  Сортировка выбором Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массив не будет полностью отсортирован.  Методы поиска элемента в массиве Бинарный поиск Данный вид поиска применяется в отсортированном массиве. Определение значения элемента в середине структуры данных. Полученное значе-ние сравнивается с ключом. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй. Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом. Процесс продолжается до тех пор, пока не будет найден элемент со значением клю-ча или не станет пустым интервал для поиска. Ключ - искомый элемент массива. Предположим, искомый элемент равен 3,тогда  Линейный, последовательный поиск (перебор, сквозной поиск) Исследования начинаются с первого элемента массива. Если искомое значение не равно значению ключа, то осуществляется переход к следующему значению. То есть в результате каждой проверки количество проверяемых элементов уменьшается на один. Итоговая работа «Исследование алгоритмов сортировки и поиска данных в массивах». Необходимо разработать и реализовать программы сортировки заданного числового массива действительных чисел, находящегося в файле на диске приведенными выше методами. Файл можно создать, используя блокнот, разделяя числа пробелами. Для каж-дого метода найти и вывести на экран количество операций сравнения, требуемых при его реализации. Отсортированный массив вывести в дисковый файл (исходный файл сохраняется!). Исходный файл состоит из 20 положительных, отрицательных и нулевых элементов. Кроме отчета необходимо выслать исходный и отсортированный файлы. Далее требуется реализовать алгоритмы бинарного и сквозного поиска для исходного массива и сравнить результаты их работы. Приложение. Организация ввода (вывода) элементов массива из файла (в файл). #include #include using namespace std; void bubbleSort(double arr[], int n, int& compCount) { bool swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - i - 1; j++) { compCount++; if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) { break; } } } void selectionSort(double arr[], int n, int& compCount) { int minIndex; for (int i = 0; i < n - 1; i++) { minIndex = i; for (int j = i + 1; j < n; j++) { compCount++; if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { swap(arr[i], arr[minIndex]); } } } void shuffleSort(double arr[], int n, int& compCount) { srand(time(NULL)); for (int i = n - 1; i > 0; i--) { int j = rand() % (i + 1); swap(arr[i], arr[j]); compCount++; } bubbleSort(arr, n, compCount); } void binarySearch(double arr[], int n, double x, int& compCount, int& index) { int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; compCount++; if (arr[mid] == x) { index = mid; return; } else if (arr[mid] < x) { l = mid + 1; } else { r = mid - 1; } } } void linearSearch(double arr[], int n, double x, int& compCount, int& index) { for (int i = 0; i < n; i++) { compCount++; if (arr[i] == x) { index = i; return; } } } int main() { const int SIZE = 20; double arr[SIZE]; ifstream inputFile("input.txt"); for (int i = 0; i < SIZE; i++) { inputFile >> arr[i]; } inputFile.close(); int compCount = 0; bubbleSort(arr, SIZE, compCount); ofstream outputFile("output_bubble.txt"); for (int i = 0; i < SIZE; i++) { outputFile << arr[i] << " "; } outputFile.close(); cout << "Сортировка пузырьком: " << compCount << endl; compCount = 0; selectionSort(arr, SIZE, compCount); outputFile.open("output_selection.txt"); for (int i = 0; i < SIZE; i++) { outputFile << arr[i] << " "; } outputFile.close(); cout << "Сортировка выбором: " << compCount << endl; compCount = 0; shuffleSort(arr, SIZE, compCount); outputFile.open("output_shuffle.txt"); for (int i = 0; i < SIZE; i++) { outputFile << arr[i] << " "; } outputFile.close(); }  Рис.1 Исходный файл input.txt  Рис.2 Отсортированные файлы output_.txt |