Алгоритмы сортировки и простая консольная оболочка для них
Сортировка – это упорядочение элементов массива по возрастанию или убыванию (точнее, по неубыванию или невозрастанию).
В любых начальных курсах по программированию алгоритмам сортировки уделяется большое внимание, в связи как с их распространённостью на практике (весьма часто нам нужно упорядочить свои данные по определённому признаку), так и наглядностью, с которой эти алгоритмы дают представление о временной сложности.
В информатике временная сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе.
В реальности время выполнения программы зависит от "железа", операционной системы и других системных характеристик, поэтому оценивается не быстродействие программы на конкретном компьютере, а обобщённая характеристика производительности алгоритма.
Временная сложность алгоритма обычно выражается с использованием нотации "O" большое, которая учитывает только слагаемое самого высокого порядка, а также отбрасывает константные множители (коэффициенты). Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть, при стремлении размера входа к бесконечности.
Например, если существует число n0, такое, что время работы алгоритма для всех входов длины n > n0 не превосходит 5n3+3n, то временную сложность данного алгоритма можно асимптотически оценить как О(n3).
Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1). В таких обозначениях полное время исполнения и число элементарных операций, выполненных алгоритмом, отличаются максимум на постоянный множитель, который не учитывается в O-нотации.
Существуют десятки алгоритмов сортировки, среди которых нет абсолютно лучшего: разные алгоритмы оптимальны для разных наборов и типов данных. Самые популярные из них - пузырьковая сортировка, сортировка перемешиванием, сортировка расчёской, сортировка вставками, сортировка выбором, быстрая сортировка, пирамидальная сортировка и другие.
Одни алгоритмы просты в реализации и хорошо подходят для разъяснения принципов, другие - для работы с большими массивами данных, третьи оптимизированы по числу процессорных циклов, скорости, и так далее.
Рассмотрим основные алгоритмы сортировки.
Сортировка пузырьком - один из самых известных алгоритмов сортировки. Его суть в последовательном сравнении значений двух соседних элементов слева направо: если предыдущее больше последующего, они меняются местами. При сортировке элементов по убыванию, наоборот: в конец списка уходят элементы с наименьшим значением.
Здесь во внутреннем цикле перебираем значения, начиная с последнего (n-1), и в каждом следующем проходе уменьшаем количество просмотренных элементов (j > i).
void bubble_sort(const int n, int a[]) { int i, j; for (i = 0; i < n - 1; i++) { //внешний цикл отвечает за номер прохода for (j = n - 1; j > i; j--) { //внутренний - за перебор элементов в одном проходе if (a[j - 1] > a[j]) std::swap (a[j - 1], a[j]); } } }
Вызвать нашу функцию из main
можно так:
bubble_sort(n, a);
Сложность алгоритма составляет О(n2).
Алгоритм хорошо себя показывает с большими наборами данных, где элементы почти отсортированы и требуется всего одна итерация, чтобы определить, отсортирован ли список до конца.
В случае с совершенно неотсортированным списком, для пузырьковой сортировки он должен быть хотя бы небольшим.
Улучшенными версиями пузырькового метода являются сортировки перемешиванием (шейкерная) и расчёской.
Сортировка вставками. Это простая сортировка, при которой массив постепенно перебирается слева направо. При этом элемент сравнивается со всеми предыдущими элементами и размещается так, чтобы оказаться в подходящем месте среди ранее упорядоченных элементов. Так происходит до тех пор, пока набор входных данных не будет исчерпан. Звучит сложно, но на деле это довольно простой алгоритм.
void inserting_sort(const int n, int a[]) { int i, j, temp; for (i = 1; i < n; i++) { temp = a[i]; for (j = i; j > 0 && temp < a[j - 1]; j--) { a[j] = a[j - 1]; } a[j] = temp; } }
Вызов функции аналогичен пузырьковой сортировке. Сложность алгоритма составляет О(n2).
Как и в случае с пузырьковой сортировкой, этот алгоритм работает быстрее всего на очень маленьком или почти отсортированном наборе данных.
Данный алгоритм также используется как часть алгоритма сортировки Шелла.
Сортировка выбором - это некий гибрид между пузырьковой сортировкой и вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее не отсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце.
void selection_sort(const int n, int a[]) { int min, imin, i, j; for (i = 0; i < n; i++) { min = a[i]; imin = i; for (j = i + 1; j < n; j++) { if (a[j] < min) { min = a[j]; imin = j; } } std::swap (a[imin], a[i]); } }
Вызов функции аналогичен пузырьковой сортировке. Сложность алгоритма также соответствует О(n2).
Быстрая сортировка относится к эффективным алгоритмам и состоит из нескольких шагов:
1. Из массива выбирается опорный элемент, чаще всего посередине массива.
2. Другие элементы массива распределяются таким образом, чтобы меньшие размещались до него, а большие - после.
3. Далее первые шаги рекурсивно применяются к подмассивам, которые разделились опорным элементом на две части - слева и справа от него.
void quick_sort(const int n, int a[], int low, int high) { if (n == 0 || low >= high) return; //завершить, если массив пуст или уже нечего делить int middle = low + (high - low) / 2; int opora = a[middle]; //выбираем опорный элемент int i = low, j = high; //разделяем на подмассивы while (i <= j) { while (a[i] < opora) i++; while (a[j] > opora) j--; if (i <= j) { //меняем местами std::swap (a[i],a[j]); i++; j--; } } if (low < j) { //рекурсия для сортировки левой и правой части quick_sort(n, a, low, j); } if (high > i) { quick_sort(n, a, i, high); } }
Так как алгоритм рекурсивен, в функцию дополнительно передаются аргументы low и high, хранящие индексы начала и конца текущего подмассива.
Соответственно, вызов подпрограммы будет иметь вид
quick_sort(n, a, 0, n - 1);
Сложность алгоритма: O(n log n) в среднем, O(n2) в худшем случае.
Быстрая сортировка очень популярна, но она далеко не всегда O(n log n), так как в худших случаях она становится О(n2).
Быстрая сортировка более эффективна для наборов данных, которые помещаются в доступную память. Для больших наборов она неэффективна, и в этом случае более предпочтительна, например, сортировка слиянием.
Быстрая сортировка - это сортировка на месте (т. е. она не требует дополнительной памяти), поэтому её целесообразно использовать для массивов.
Стандартный алгоритм C++ std::sort использует интроспективную сортировку, основанную на идее алгоритма quick sort.
Сортировка Шелла. Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными "грубыми" проходами.
void shell_sort(const int n, int a[]) { for (int step = n / 2; step > 0; step /= 2) { for (int i = step; i < n; i++) { for (int j = i - step; j >= 0 && a[j] > a[j + step]; j -= step) { if (a[j] > a[j + step]) std::swap(a[j],a[j+step]); } } } }
Вызов функции аналогичен первым трём сортировкам. Сложность алгоритма: О(n2) в худшем случае, O(n log2 n) в среднем.
Несмотря на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
- отсутствие потребности в памяти под стек;
- отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n2), что случается чаще, чем худшее гарантированное время для сортировки Шелла.
Сортировка слиянием. Этот алгоритм упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа "разделяй и властвуй", то есть, хорошо подходит для распараллеливания на несколько процессоров. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
void merge(int a[], int const low, int const mid, int const hi) { //Слияние подмассивов a[low..mid] и a[mid+1..hi] //Эта функция нужна для работы merge_sort const int n_low = mid - low + 1, n_hi = hi - mid; //Создать временные массивы int *a_left = new int[n_low], *a_right = new int[n_hi]; //Скопировать данные в них for (int i = 0; i < n_low; i++) a_left[i] = a[low + i]; for (int j = 0; j < n_hi; j++) a_right[j] = a[mid + 1 + j]; int i_left = 0, i_right = 0; //Начальные индексы в подмассивах int index = low; //Начальный индекс в массиве слияния //Сливаем временные массивы в a[low..hi] while (i_left < n_low && i_right < n_hi) { if (a_left[i_left] <= a_right[i_right]) { a[index] = a_left[i_left]; i_left++; } else { a[index] = a_right[i_right]; i_right++; } index++; } //Копируем оставшиеся элементы while (i_left < n_low) { a[index] = a_left[i_left]; i_left++; index++; } while (i_right < n_hi) { a[index] = a_right[i_right]; i_right++; index++; } delete[] a_left; delete[] a_right; } void merge_sort(int a[], const int low, const int hi) { if (low >= hi) return; int mid = low + (hi - low) / 2; merge_sort (a, low, mid); merge_sort (a, mid + 1, hi); merge(a, low, mid, hi); }
Эта сортировка использует в качестве буфера дополнительный массив как минимум с таким же размером как у a
и, подобно алгоритму быстрой сортировки, является рекурсивной, то есть, требует передачи ещё двух дополнительных аргументов, отвечающих за текущую длину сортируемой части. Поэтому вызов функции выглядит так:
merge_sort(a, 0, n-1);
Сложность алгоритма: O(n log n) и в худшем случае, и в среднем.
Про стабильность алгоритмов сортировки писалось вот здесь. В современных версиях C++ есть стандартный алгоритм стабильной сортировки std::stable_sort.
Для написания программы-"оболочки" используем небольшой класс таймера и сделаем ей консольное меню, где можно выбрать метод сортировки, указать размерность массива данных и включить или выключить вывод отсортированного массива на экран. Добавив в меню вызов других подпрограмм из статьи, Вы без труда расширите этй "заготовку". Код проверялся в Visual Studio актуальных сборок версий 2019, 2022.
Для обмена местами двух элементов массива в наших функциях мы применяем стандартный алгоритм std::swap.
//Сортировки, консольное приложение C++, вставьте листинг в пустой файл Source.cpp #include <iostream> #include <iomanip> #include <algorithm> #include <cstdlib> #include <ctime> #include <chrono> class Timer { //класс таймера std::chrono::high_resolution_clock::time_point start; public: Timer() { start = std::chrono::high_resolution_clock::now(); } double stop() { std::chrono::high_resolution_clock::time_point end = std::chrono::high_resolution_clock::now(); std::chrono::duration <double> time_span = std::chrono::duration_cast <std::chrono::duration<double>>(end - start); return time_span.count(); } }; template <typename T> void fill_array(const int n, T a[], T low, T step) { //заполнение массива a[n] случайными числами из диапазона значений [low,hi] srand((unsigned int)time(NULL)); a[0] = low; for (int i = 1; i < n; i++) a[i] = a[i - 1] + rand() % step; } template <typename T> void type_array(const int n, T a[]) { //вывод массива a[n] std::cout << std::fixed; for (int i = 0; i < n; i++) std::cout << std::setw(12) << a[i]; //или другая ширина столбца в скобках std::cout << std::endl; } void selection_sort(const int n, int a[]) { //выбором int min, imin, i, j; for (i = 0; i < n; i++) { min = a[i]; imin = i; for (j = i + 1; j < n; j++) { if (a[j] < min) { min = a[j]; imin = j; } } std::swap <int >(a[imin], a[i]); } } void bubble_sort(const int n, int a[]) { //пузырьком int i, j; for (i = 0; i < n - 1; i++) { //внешний цикл отвечает за номер прохода for (j = n - 1; j > i; j--) { //внутренний - за перебор элементов в одном проходе if (a[j - 1] > a[j]) std::swap <int >(a[j - 1], a[j]); } } } void inserting_sort(const int n, int a[]) { //вставками int i, j, temp; for (i = 1; i < n; i++) { temp = a[i]; for (j = i; j > 0 && temp < a[j - 1]; j--) { a[j] = a[j - 1]; } a[j] = temp; } } void quick_sort(const int n, int a[], int low, int high) { //быстрая if (n == 0 || low >= high) return; //завершить, если массив пуст или уже нечего делить int middle = low + (high - low) / 2; int opora = a[middle]; //выбираем опорный элемент int i = low, j = high; //разделяем на подмассивы while (i <= j) { while (a[i] < opora) i++; while (a[j] > opora) j--; if (i <= j) { //меняем местами std::swap(a[i], a[j]); i++; j--; } } if (low < j) { //рекурсия для сортировки левой и правой части quick_sort(n, a, low, j); } if (high > i) { quick_sort(n, a, i, high); } } void shell_sort(const int n, int a[]) { //Шелла for (int step = n / 2; step > 0; step /= 2) { for (int i = step; i < n; i++) { for (int j = i - step; j >= 0 && a[j] > a[j + step]; j -= step) { if (a[j] > a[j + step]) std::swap(a[j], a[j + step]); } } } } void merge(int a[], int const low, int const mid, int const hi) { //Служебный для "слиянием" //Слияние подмассивов a[low..mid] и a[mid+1..hi] //Эта функция нужна для работы merge_sort const int n_low = mid - low + 1, n_hi = hi - mid; //Создать временные массивы int* a_left = new int[n_low], * a_right = new int[n_hi]; //Скопировать данные в них for (int i = 0; i < n_low; i++) a_left[i] = a[low + i]; for (int j = 0; j < n_hi; j++) a_right[j] = a[mid + 1 + j]; int i_left = 0, i_right = 0; //Начальные индексы в подмассивах int index = low; //Начальный индекс в массиве слияния //Сливаем временные массивы в a[low..hi] while (i_left < n_low && i_right < n_hi) { if (a_left[i_left] <= a_right[i_right]) { a[index] = a_left[i_left]; i_left++; } else { a[index] = a_right[i_right]; i_right++; } index++; } //Копируем оставшиеся элементы while (i_left < n_low) { a[index] = a_left[i_left]; i_left++; index++; } while (i_right < n_hi) { a[index] = a_right[i_right]; i_right++; index++; } delete[] a_left; delete[] a_right; } void merge_sort(int a[], const int low, const int hi) { //Слиянием if (low >= hi) return; int mid = low + (hi - low) / 2; merge_sort(a, low, mid); merge_sort(a, mid + 1, hi); merge(a, low, mid, hi); } void refresh() { //сброс консоли после ошибки ввода std::cin.clear(); std::cin.ignore(100, '\n'); } int main() { int n = 10000; int* a = new int[n]; if (!a) { std::cout << "No memory!" << std::endl; return -1; } double time; bool show = true; do { std::cout << "Select the action:" << std::endl << "1 - Selection sorting" << std::endl << "2 - Bubble sorting" << std::endl << "3 - Inserting sorting" << std::endl << "4 - Quick sorting" << std::endl << "5 - Shell sorting" << std::endl << "6 - Merge sorting" << std::endl << "7 - New array size (now is " << n << ")" << std::endl << "8 - Show sorted: (now is " << (show ? "on" : "off") << ")" << std::endl << "0 - Exit" << std::endl; char choice; std::cin >> choice; refresh(); switch (choice) { case '1': case '2': case '3': case '4': case '5': case '6': fill_array <int> (n, a, -n, n); { //только чтобы описать внутри таймер Timer t; switch (choice) { case '1': selection_sort(n, a); break; case '2': bubble_sort(n, a); break; case '3': inserting_sort(n, a); break; case '4': quick_sort(n, a, 0, n - 1); break; case '5': shell_sort(n, a); break; case '6': merge_sort(a, 0, n - 1); break; } time = t.stop(); } std::cout << "time: " << std::fixed << time << " sec." << std::endl; if (show) type_array(n, a); break; case '7': do { std::cout << "Current size is " << n << std::endl << "Put new size (integer >99): "; std::cin >> n; if (!std::cin.good() || n < 100) { refresh(); continue; } else break; } while (1); if (a) { delete[] a; a = nullptr; a = new int[n]; if (!a) { std::cout << "No memory for n=" << n << std::endl; return -1; } } break; case '8': show = !show; break; case '0': exit(0); default: std::cout << "Bad action, repeat it, please" << std::endl; break; } } while (1); return 0; }
После запуска отключите из меню (клавишей "8") тестовый вывод отсортированных массивов и собирайте приложение в профиле Release, а не Debug, чтобы результаты были корректными.
О том, как измерить время выполнения подпрограммы при меняющихся в достаточно широких пределах размерностях входных данных, а также графически оценить временную сложность алгоритма, напишем в следующей заметке.
28.03.2023, 17:56 [459 просмотров]