Быстрая сортировка — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Ulysses (обсуждение | вклад) (Новая страница: «'''Быстрая сортировка''' (англ. quicksort) — широко известный алгоритм сортировки, разработанный…») |
Ulysses (обсуждение | вклад) (→Реализация на C) |
||
| Строка 6: | Строка 6: | ||
* повторить рекурсивно для «меньших» и «больших». | * повторить рекурсивно для «меньших» и «больших». | ||
| − | ===Реализация на C=== | + | ===Реализация на C (случай массива целых чисел)=== |
<source lang="cpp"> | <source lang="cpp"> | ||
#include <iostream> | #include <iostream> | ||
| Строка 38: | Строка 38: | ||
} | } | ||
</source> | </source> | ||
| − | |||
===См. также=== | ===См. также=== | ||
[http://ru.wikipedia.org/wiki/Быстрая_сортировка Википедия: Быстрая сортировка] | [http://ru.wikipedia.org/wiki/Быстрая_сортировка Википедия: Быстрая сортировка] | ||
Версия 15:31, 19 ноября 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));
}