Быстрая сортировка — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
м (См. также)
(Реализация на 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));
}

См. также