Алгоритм быстрой сортировки (Quick sort algorithm)

Алгоритм быстрой сортировки - это алгоритм из серии "разделяй и властвуй", поэтому разобьем алгоритм на три части: разделение, властвование и комбинирование.

Для наглядности позначим сортируемый массив  А[p...r].

Разделение.

В этой части массив А[p...r] разбивается на две части, а именно на А[p...q-1] и А[q+1...r], где элементы А[p...q-1]  меньше или равно значению A[q], а элементы подмассива А[q+1...r] больше или равны значению A[q]. Где элемент q - вычисляется при исполнении процедуры разбиения.

Властвование.

Полученные подмассивы А[p...q-1] и А[q+1...r] сортируются с помощью рекурсивного вызова алгоритма быстрой сортировки.

Комбинирование.

Правда комбинирование в алгоритме быстрой сортировки не понадобится, так как подмассивы сортируются на месте.

Пример кода алгоритма быстрой сортировки на Java:

/*
 * QuickSort Algorithm
 */
public static void QuickSort(Integer[] vector, int p, int r) {
	if (p < r) {
            int q = Partition(vector, p, r);
            QuickSort(vector, p, q - 1);
            QuickSort(vector, q + 1, r);
	}
}

Но главная часть алгоритма - это процедура разбиения и изменения порядка элементов массива, которая при этом не использует дополнительной памяти.

Пример на Java:

public static int Partition(Integer[] vector, int p, int r) {
	int x = vector[r];
	int i = p - 1;
	int ch;
	for (int j = p; j <= r - 1; j++) {
		if (vector[j] <= x) {
			i++;
			ch = vector[i];
			vector[i] = vector[j];
			vector[j] = ch;
		}
	}
	ch = vector[i + 1];
	vector[i + 1] = vector[r];
	vector[r] = ch;
	
	return i + 1;
}

Процедура Partition в качестве аргументов получает сам вектор и значения начального элемента и конечного элемента сортировки. Значение опорного элемента (это значение x в коде) беретса крайним правым значением (правда есть разные вариации даного алгоритма с использованием рандомизации выбора опорного аргумента и другие). По сути, массив неформально розбивается на четыре части (которые могут быть пустыми), а именно:

  1. Значения между индексами p и i: A[p...i] <= x;
  2. Значения между индексами i и j: A[i...j] > x;
  3. Подмассив A[j...r-1], в котором нет ограничений;
  4. Сам элемент x = A[r].

Эти области показаны на рисунку ниже:

В строках 5-12 алгоритма разбиения мы ищем элементы, которые меньше опорного и обмениваем их местами с элементами из области A[i...j], которые являются большими за элемент x. Таким образом в конце алгоритма мы получаем три области, а именно: элементы которые меньше опорного; элементы, которые больше опорного; сам опорный элемент.

В строках 13-15 мы помещаем наш опорные елемент в позицию между двумя полученными областями и возвращаем индекс нашего опорного элемента.

Алгоритм процедуры разбиения заключается в том, чтобы возвратить значение индекса, который будет разбивать массив на два подмассива, где в первом подмассиве все элементы будут меньше за опорный элемент, а во втором - все элементы больше опорного элемента.

Пример работы алгоритма быстрой сортировки можна увидеть вначале статьи на рисунке.

Всем спасибо за внимание. Если есть какие-то замечания, тогда пишите.

LikeMe: