Алгоритм быстрой сортировки (Quick sort). Сортировка Хоара.
Алгоритм быстрой сортировки — это один из самых быстрых существующих алгоритмов сортировки (на момент написания данной статьи), который является примером стратегии «разделяй и властвуй». Большинство готовых библиотек и методов по сортировке используют quick sort алгоритм как основу.
Пошаговое описание работы алгоритма быстрой сортировки
1. Выбрать опорный элемент из массива. Обычно опорным элементом является средний элемент.
2. Разделить массив на два подмассива: элементы, меньше опорного и элементы, больше опорного.
3. Рекурсивно применить сортировку к двум подмассивам.
В результате таких действий рекурсии, программа дойдет до того, что массивы будут делиться пока не будет один элемент, который потом и отсортируется. Звучит немного запутано и странно. Для наглядности посмотрите анимацию и картинки ниже.
Подробный анализ алгоритма быстрой сортировки
Исходный массив
Выбор опорного элемента. В данном случае мы взяли первый элемент 3
Разбиваем массив на подмассивы: те, что больше 3 и те, что меньше 3
Проделаем то же самое с левый подмассивом
Выбор опорного элемента
Разбиение на подмассивы
Выбор опорного и разбиение на подмассивы. Не забываем, что мы проделываем эти шаги пока не будет один элемент в подмассиве.
Как видим, левая часть отсортирована. То же самое проделывается и для правой части от опорного элемента 3.
“Шейкерная” сортировка
Рассмотрев “пузырьковую” сортировку массива можно перейти к разбору её разновидности – “шейкер”-сортировке. Вы можете встретить несколько её названи: сортировка перемешиванием, пульсирующая сортировка, двунаправленная сортировка “пузырьком”.
Внимательно присмотревшись к тому, как проходит сортировка “пузырьком” – можно сказать следующее: часть массива, в котором перестановки элементов уже не происходят (отсортированная часть массива), то эту часть можно исключить из рассмотрения и не обрабатывать на следующих итерациях. Второе, что вы могли заметить – это то, что минимальный (самый “легкий” элемент) при сортировке сразу перемещается в самое начало массива, а “тяжелые” элементы сдвигаются только на одну позицию “вниз”. Так массив
будет отсортирован за один проход вложенным циклом, а для массива
понадобится три итерации.
Поэтому была придумана более эффективная форма сортировки “пузырьком” -“шейкер”-сортировка. В ней пределы той части массива в которой есть перестановки, сужаются. Плюс – внутренние циклы проходят по массиву то в одну, то в другую сторону, поднимая самый легкий элемент вверх и опуская самый тяжелый элемент в самый низ за одну итерацию внешнего цикла.
| #include <iostream> using namespace std; //ф-ция для обмена значений ячеек void swapEl(int *arr, int i) { int buff; buff = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = buff; } //ф-ция "шейкер"-сортировки void myShakerSort(int *arr, int size) { int leftMark = 1; int rightMark = size - 1; while (leftMark <= rightMark) { for (int i = rightMark; i >= leftMark; i--) if (arr[i - 1] > arr[i]) swapEl(arr, i); leftMark++; for (int i = leftMark; i <= rightMark; i++) if (arr[i - 1] > arr[i]) swapEl(arr, i); rightMark--; cout << "\nИтерация: " << leftMark - 1; // просмотр количества итераций } } int main() { setlocale(LC_ALL, "rus"); int size = 0; cout << "Размер массива: "; cin >> size; int *A = new int[size]; for (int k = 0; k < size; k++) { A[k] = size - k; // запись значений по убыванию cout << A[k] << " | "; } myShakerSort(A, size); // сортировка cout << "\nМассив после сортировки:\n"; for (int k = 0; k < size; k++) { cout << A[k] << " | "; } cout << endl; return 0; } |
public static void shakerSort(int array[]) {
2 int buff;
3 int left=0;
4 int right=array.length-1;
5 do {
6 for (int i=left; i<right;i++) {
7 if (array[i]>array[i+1]) {
8 buff = array[i];
9 array[i] = array[i + 1];
10 array[i + 1] = buff;
11 }
12 }
13 right--;
14 for (int i=right; i>left; i--) {
15 if (array[i]<array[i-1]) {
16 buff = array[i];
17 array[i] = array[i - 1];
18 array[i - 1] = buff;
19 }
20 }
21 left++;
22 } while (left <right);
23 }
https://habr.com/ru/post/198114/
https://habr.com/ru/post/198114/