Быстрая сортировка :: Quick sort
Простой в реализации и очень быстрый способ. Считается эталоном скорости для алгоритмов сортировки. Когда заходит о временной сложности какого-либо эффективного метода сортировки, то обычно его сравнивают именно с Quick sort.
Способ разработал 26-летний аспирант из Оксфорда Чарльз Хоар. В том далёком 1960 году он стажировался в СССР. В МГУ он обучался компьютерному переводу, а в школе Колмогорова изучал теорию вероятности.
Алгоритм
- Выбирается опорный элемент (например, посередине массива).
- Массив просматривается слева-направо и производится поиск ближайшего элемента, больший чем опорный.
- Массив просматривается справа-налево и производится поиск ближайшего элемента, меньший чем опорный.
- Найденные элементы меняются местами.
- Продолжается одновременный двухсторонний просмотр по массиву с последующими обменами в соответствии с пунктами 2-4.
- В конце концов, просмотры слева-напрво и справа-налево сходятся в одной точке, которая делит массив на два подмассива.
- К каждому из двух подмассивов рекурсивно применяется "Быстрая сортировка".
Характеристики алгоритма
| Название | Быстрая сортировка (Quick sort) | |
|---|---|---|
| Автор | Сэр Чарльз Э́нтони Ри́чард Хо́ар(Sir Charles Antony Richard Hoare) | |
| Год | 1960 | |
| Класс | Сортировки обменами | |
| Устойчивость | Нет | |
| Сравнения | Да | |
| Сложность по времени | Лучшая | O(n) |
| Средняя | O(n log n) | |
| Худшая | O(n2) | |
| Сложность по дополнительной памяти | Нативная | O(n) |
| Седжвик | O(log n) | |
Быстрая сортировка
Реализация на различных ЯП