Быстрая сортировка — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Ulysses (обсуждение | вклад) (→Реализация на C (случай массива целых чисел)) |
Ulysses (обсуждение | вклад) (→Реализация на C (случай массива целых чисел)) |
||
| Строка 16: | Строка 16: | ||
using std::swap; | using std::swap; | ||
| − | // pivot - "опорный" элемент | + | // pivot - указатель на "опорный" элемент |
// partition - переупорядочивает элементы части массива, | // partition - переупорядочивает элементы части массива, | ||
| − | // заданной отрезком [left, right | + | // заданной отрезком [left, right], так что в начале |
| − | // следуют элементы меньшие pivot, а в конце - большие; | + | // следуют элементы меньшие *pivot, а в конце - большие или равные; |
| − | // возвращает место начала блока элементов, больших pivot; | + | // возвращает место начала блока элементов, |
| − | int * partition(int * left, int * right, int pivot) { | + | // больших или равных *pivot, причём этот блок начинается с *pivot; |
| + | int * partition(int * left, int * right, int * pivot) { | ||
int * store = left; // место для вставки элементов, меньших pivot | int * store = left; // место для вставки элементов, меньших pivot | ||
| + | int pivotValue = *pivot; | ||
| + | swap(*pivot, *right); // перемещаем опорный в конец | ||
for (int * p = left; p != right; ++p) | for (int * p = left; p != right; ++p) | ||
| − | if (*p < | + | if (*p < pivotValue) |
swap(*p, *store++); | swap(*p, *store++); | ||
| − | return store; | + | swap(*store, *right); // возвращаем опорный на место, указываемое store |
| + | return store; | ||
} | } | ||
void my_qsort(int * arr, int n) { | void my_qsort(int * arr, int n) { | ||
| + | using namespace std; | ||
if (n <= 1) | if (n <= 1) | ||
return; // массив в 1 или 0 элементов уже упорядочен | return; // массив в 1 или 0 элементов уже упорядочен | ||
| − | int * pivotPtr = arr + rand() % n; // случайный выбор опорного элемента | + | int * pivotPtr = arr + rand() % n; // случайный выбор опорного элемента |
| − | int newPivotIdx = partition(arr, arr + n, | + | int newPivotIdx = partition(arr, arr + n - 1, pivotPtr) - arr; |
| − | my_qsort(arr, newPivotIdx | + | my_qsort(arr, newPivotIdx); // двух рекурсивных вызовах исключён элемент в позиции |
| − | my_qsort(arr + newPivotIdx, n - | + | my_qsort(arr + newPivotIdx + 1, n - newPivotIdx - 1); // newPivotIdx, который уже стоит на нужном месте |
} | } | ||
</source> | </source> | ||
Версия 20:57, 3 декабря 2010
Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком сэром Тони Хоаром. Один из самых быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов).
Краткое описание алгоритма
- выбрать элемент, называемый опорным;
- сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие;
- повторить рекурсивно для «меньших» и «больших».
Реализация на C (случай массива целых чисел)
#include <iostream>
#include <iterator>
#include <cstdlib>
using std::rand;
using std::swap;
// pivot - указатель на "опорный" элемент
// partition - переупорядочивает элементы части массива,
// заданной отрезком [left, right], так что в начале
// следуют элементы меньшие *pivot, а в конце - большие или равные;
// возвращает место начала блока элементов,
// больших или равных *pivot, причём этот блок начинается с *pivot;
int * partition(int * left, int * right, int * pivot) {
int * store = left; // место для вставки элементов, меньших pivot
int pivotValue = *pivot;
swap(*pivot, *right); // перемещаем опорный в конец
for (int * p = left; p != right; ++p)
if (*p < pivotValue)
swap(*p, *store++);
swap(*store, *right); // возвращаем опорный на место, указываемое store
return store;
}
void my_qsort(int * arr, int n) {
using namespace std;
if (n <= 1)
return; // массив в 1 или 0 элементов уже упорядочен
int * pivotPtr = arr + rand() % n; // случайный выбор опорного элемента
int newPivotIdx = partition(arr, arr + n - 1, pivotPtr) - arr;
my_qsort(arr, newPivotIdx); // двух рекурсивных вызовах исключён элемент в позиции
my_qsort(arr + newPivotIdx + 1, n - newPivotIdx - 1); // newPivotIdx, который уже стоит на нужном месте
}