Быстрая сортировка — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Ulysses (обсуждение | вклад) м (→См. также) |
Ulysses (обсуждение | вклад) (→Реализация на C (случай массива целых чисел)) |
||
| Строка 20: | Строка 20: | ||
// заданной отрезком [left, right), так что в начале | // заданной отрезком [left, right), так что в начале | ||
// следуют элементы меньшие pivot, а в конце - большие; | // следуют элементы меньшие pivot, а в конце - большие; | ||
| − | // возвращает место pivot | + | // возвращает место начала блока элементов, больших pivot; |
int * partition(int * left, int * right, int pivot) { | int * partition(int * left, int * right, int pivot) { | ||
int * store = left; // место для вставки элементов, меньших pivot | int * store = left; // место для вставки элементов, меньших pivot | ||
Версия 01:11, 23 ноября 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;
int * partition(int * left, int * right, int pivot) {
int * store = left; // место для вставки элементов, меньших pivot
for (int * p = left; p != right; ++p)
if (*p < pivot)
swap(*p, *store++);
return store;
}
void my_qsort(int * arr, int n) {
if (n <= 1)
return; // массив в 1 или 0 элементов уже упорядочен
int * pivotPtr = arr + rand() % n; // случайный выбор опорного элемента
int newPivotIdx = partition(arr, arr + n, *pivotPtr) - arr;
my_qsort(arr, newPivotIdx + 1);
my_qsort(arr + newPivotIdx, n - (newPivotIdx + 1));
}