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

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

Текущая версия на 13:14, 11 декабря 2014

Быстрая сортировка (англ. 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) {
	if (n <= 1)                                                    // массив в 1 или 0 элементов уже упорядочен
		return; 
	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, который уже
                                                                       //     стоит на нужном месте
}

См. также