ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.12.2023
Просмотров: 23
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Тема: поиск и сортировка данных в массивах.
Методы сортировки элементов массива
Сортировка пузырьком.
При данной сортировке (в порядке возрастания) нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом, элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.
Пример. Пусть исходный массив имеет вид:
. Отсортируем его в порядке возрастания:
Сортировка перемешиванием (шейкерная сортировка).
Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа на-лево.
Сортировка выбором
Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массив не будет полностью отсортирован.
Методы поиска элемента в массиве
Бинарный поиск
Данный вид поиска применяется в отсортированном массиве.
-
Определение значения элемента в середине структуры данных. Полученное значе-ние сравнивается с ключом. -
Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй. -
Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом. -
Процесс продолжается до тех пор, пока не будет найден элемент со значением клю-ча или не станет пустым интервал для поиска.
Ключ - искомый элемент массива. Предположим, искомый элемент равен 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