Почему быстрая сортировка на самом деле медленная? Новый метод сортировки массива

в 8:37, , рубрики: c++, merge sort, mergesort, newgenerationsort, O(n), quick sort, quicksort, Алгоритмы, алгоритмы сортировки, быстрая сортировка, ненормальное программирование, Программирование, сортировка вставками, сортировка выбором, сортировка нового поколения, сортировка слиянием

imageМногие программисты думают, что Quick Sort — самый быстрый алгоритм из всех существующих. Отчасти это так. Но работает она действительно хорошо только если правильно выбран опорный элемент (тогда сложность составляет O (n log n)). В противном же случае асимптотика будет примерно такой же как и в пузырика (то-есть O (n2)).
При этом, если массив уже отсортирован, то алгоритм всё-равно будет работать не быстрее, чем за O (n log n)

Исходя из этого, я решил написать свой алгоритм для сортировки массива, который работал бы лучше за quick_sort. И если массив уже отсортирован, то не прогонять его кучу раз, как это бывает у многих алгоритмов.

«Дело было вечером, делать было нечего», — Сергей Михалков.

Требования:

  1. Лучший случай O (n)
  2. Средний случай O (n log n)
  3. Худший случай O (n log n)
  4. В среднем быстрее быстрой сортировки

А теперь давайте обо всём по порядку

Чтобы наш алгоритм всегда работал быстро, нужно чтобы в среднем случае асимптотика была хотя бы O (n log n), а в лучшем — O (n). Все мы прекрасно знаем, что в лучшем случае сортировка вставками работает за один проход. Но в худшем ей придётся гонять по массиву столько раз, сколько в нём элементов.

Предварительная информация

Функция слияния двух массивов
int* glue(int* a, int lenA, int* b, int lenB) {
	int lenC = lenA + lenB;
	int* c = new int[lenC]; // результирующий массив
	int indx_a = 0;
	int indx_b = 0;
	int i = 0;
			
	for (; i < lenC; ++i) {
		if (indx_a < lenA) {
			if (indx_b < lenB) { // Оба массива содержат элементы
				c[i] = (a[indx_a] < b[indx_b]) ? 
					a[indx_a++] : 
					b[indx_b++];
				continue;
			} // Элементы есть только в первом
			while (indx_a < lenA)
				c[i++] = a[indx_a++];
		}
		else // Элементы есть только во втором
			while (indx_b < lenB)
				c[i++] = b[indx_b++];
		break;
	}
			
	return c;
}

Функция слияния двух массивов, сохраняет результат в указанный.

void glueDelete(int*& arr, int*& a, int lenA, int*& b, int lenB) {
	if (lenA == 0) { // если первый пустой
		delete[] a; // высвобождаем от него память
		arr = b; // результирующий будет вторым массивом
		return;
	}
	if (lenB == 0) { // если второй пустой
		delete[] b; // высвобождаем от него память
		arr = a; // результирующий будет вторым массивом
		return;
	}

	int *copy = glue(a, lenA, b, lenB); // сливаем
	delete[]a; // удаляемо ненужные массивы
	delete[]b; // удаляемо ненужные массивы
	arr = copy;  // изменяем указатель
}

Функция, которая делает сортировку вставками в границах от lo до hi

void insertionSort(int*& arr, int lo, int hi) {
	for (int i = lo + 1; i <= hi; ++i)
		for (int j = i; j > 0 && arr[j - 1] > arr[j]; --j)
			swap(arr[j - 1], arr[j]);
}

Начальная версия алгоритма (не оптимальная):

Основная идея алгоритма состоит в так называемом поиске максимума (и минимума). На каждой итерации выбираем из массива элемент. Если он больше предыдущего максимума, то добавляем этот элемент в конец выборки. Иначе если он меньше предыдущего минимума, то дописываем этот элемент в начало. Иначе кладём в отдельный массив.

На вход функция принимает массив и количество элементов в этом массиве

void FirstNewGeneratingSort(int*& arr, int len)

Для хранения выборки из массива (наши максимумы и минимумы) и остальных элементов выделим память

int* selection = new int[len << 1]; // то же что и new int[len * 2]
int left = len - 1; // индекс для хранения новых минимальных элементов
int right = len; // индекс для хранения новых максимальных элементов

int* restElements = new int[len]; // для элементов, которые не входят в выборку
int restLen = 0; // индекс следующего элемента для добавления

Как видим, для хранения выборки мы выделили в 2 раза больше памяти, чем наш исходный массив. Это сделано на случай если у нас массив отсортирован и каждый следующий элемент будет новым максимумом. Тогда будет занята только вторая часть массива выборки. Или же наоборот (если отсортирован по убыванию).

Для выборки сначала нужны начальные минимум и максимум. Просто выберем первый и второй элементы

if (arr[0] > arr[1])
	swap(arr[0], arr[1]);

selection[left--] = arr[0];
selection[right++] = arr[1];

Собственно сама выборка

for (int i = 2; i < len; ++i) {

	if (selection[right - 1] <= arr[i]) // проверяем на новый максимум
	{
		selection[right++] = arr[i];
		continue;
	}

	if (selection[left + 1] >= arr[i]) // проверяем на новый минимум
	{
		selection[left--] = arr[i];
		continue;
	}

	restElements[restLen++] = arr[i]; // если элемент не попал в выборку, он попадёт сюда
}

Теперь у нас есть отсортированный набор элементов, и «остальные» элементы, которые нам ещё нужно отсортировать. Но сначала нужно произвести некоторые манипуляции с памятью.

Освобождаем неиспользуемую память

int selectionLen = right - left - 1; // длина выборки 
int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); // в данном контексте просто копирует выборку

delete[] selection; // мы выделяли 2 * len памяти, и большая её часть скорее всего просто не используется, поэтому освобождаем лишнюю память
selection = copy; // изменяем указатель, так что теперь selection содержит только значащую информацию

delete[] arr; // далее будет рекурсивный вызов, а все элементы для сортировки у нас уже есть, поэтому освободим память от исходного массива

Делаем рекурсивный вызов сортировки для остальных элементов и сливаем их с выборкой

FirstNewGeneratingSort(restElements, restLen);
glueDelete(arr, selection, selectionLen, restElements, restLen);

Весь код алгоритма (Неоптимальная версия)

void FirstNewGeneratingSort(int*& arr, int len) {
	if (len < 2)
		return;

	int* selection = new int[len << 1];
	int left = len - 1;
	int right = len;

	int* restElements = new int[len];
	int restLen = 0;

	if (arr[0] > arr[1])
		swap(arr[0], arr[1]);

	selection[left--] = arr[0];
	selection[right++] = arr[1];

	for (int i = 2; i < len; ++i) {

		if (selection[right - 1] <= arr[i]) // проверяем на новый максимум
		{
			selection[right++] = arr[i];
			continue;
		}

		if (selection[left + 1] >= arr[i]) // проверяем на новый минимум
		{
			selection[left--] = arr[i];
			continue;
		}

		restElements[restLen++] = arr[i]; // если элемент не попал в выборку, он попадёт сюда
	}
	int selectionLen = right - left - 1; // длина выборки 
	int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); // в данном контексте просто копирует выборку

	delete[] selection; // мы выделяли 2 * len памяти, и большая её часть в большинстве случаев просто не используется, поэтому освобождаем лишнюю память
	selection = copy; // изменяем указатель, так что теперь selection содержит только значащую информацию

	delete[] arr; // далее будет рекурсивный вызов, а все элементы для сортировки у нас уже есть, поэтому освободим память от исходного массива
		
	FirstNewGeneratingSort(restElements, restLen);

	glueDelete(arr, selection, selectionLen, restElements, restLen);
}

Проверим скорость работы алгоритма по сравнению с Quick Sort

image

Как видим, это совсем не то, чего мы хотели. Почти в 6 раз дольше, чем QuickSort! Но разы в этом контексте неуместно использовать, так как здесь значение имеет именно асимптотика. В данной реализации алгоритма в худшем случае первый и второй элементы будут минимальным и максимальным. И остальные будут скопированы в отдельный массив.

Сложность алгоритма:

  • Худший случай: O (n 2)
  • Средний случай: O (n 2)
  • Лучший случай: O (n)

Хм, это ничем не лучше той же самой сортировки вставками. Да, действительно мы можем найти максимальный (минимальный) элемент очень быстро, и остальные просто не попадут в выборку.

Можем попытаться оптимизировать сортировку слиянием. Для начала проверим скорость обычной сортировки слиянием:

image

Сортировка слиянием с оптимизацией:

void newGenerationMergeSort(int* a, int lo, int hi, int& minPortion) {
	if (hi <= lo)
		return;

	int mid = lo + (hi - lo) / 2;
	if (hi - lo <= minPortion) { // если количество элементов вмещается в минимальный блок, то выполняем нашу сортировку
		int* part = glue(a + lo, hi - lo + 1, nullptr, 0); // просто копирует массив
		FirstNewGeneratingSort(part, hi - lo + 1);

		for (int i = lo; i <= hi; ++i) {
			a[i] = part[i - lo];
		}
		delete[] part;

		return;
	}

	newGenerationMergeSort(a, lo, mid, minPortion);
	newGenerationMergeSort(a, mid + 1, hi, minPortion);

	int* b = glue(a + lo, mid - lo + 1, a + mid + 1, hi - mid);

	for (int i = lo; i <= hi; i++)
		a[i] = b[i - lo];
	delete[] b;
}

Для простоты использования нужна какая-нибудь обёртка

void newMergeSort(int *arr, int length) {
	int portion = log2(length); // минимальный блок для нашей сортировки
	portion *= portion;
		
	newGenerationMergeSort(arr, 0, length - 1, portion);
}

Результат тестирования:

image

Да, прирост в скорости наблюдается, но всё-же эта функция работает не так быстро, как Quick Sort. Тем более мы не можем говорить про O (n) на отсортированных массивах. Поэтому этот вариант тоже откидаем.

Варианты оптимизации первого варианта

  1. Для того, чтобы сложность не была O (n2), мы можем складывать элементы, которые не попали в выборку не в 1 массив как ранее, а раскинуть на 2 массива. После чего останется просто отсортировать этих две подчасти, и слить их с нашей выборкой. В результате мы получим сложность равную O (n log n)

  2. Как мы уже заметили, абсолютно максимальный (минимальный) элемент в сортируемом массиве может найтись довольно быстро, и это не очень эффективно. Вот тут в помощь нам вступает сортировка вставками. На каждой итерации выборки будем проверять, можем ли мы вставить поточный элемент в набор из последних, например, восьми вставленных.

Если сейчас не понятно, то не расстраивайтесь. Так и должно быть. Сейчас на коде всё станет ясно и вопросы пропадут.

Остаточный правильный вариант алгоритма:

Сигнатура такая же как и в предыдущем варианте

void newGenerationSort(int*& arr, int len)

Но следует заметить, что данный вариант предполагает первым параметром указатель, на котором можно вызвать операцию delete[] (почему — мы увидим далее). То-есть когда мы выделяли память, мы именно для этого указателя присваивали адрес начала массива.

Предварительная подготовка

В данном примере так называемый «коэффициент навёрстывания» (catch up coefficient) — это просто константа со значением 8. Она показывает сколько максимум элементов мы попытаемся пройти, чтобы вставить новый «недо-максимум» или «недо-минимум» на своё место.

int localCatchUp = min(catchUp, len); // потому что мы не можем пытаться вставлять элемент за границами массива
insertionSort(arr, 0, localCatchUp - 1); // для начала сортируем первые localCatchUp элементов

if (len <= localCatchUp) // на случай если это массив на n <= catchUp элементов, а также 
	return; // это база рекурсии (так как при таких раскладах массив отсортирован)

Для хранения выборки создаём массив

Если что-то непонятно, то смотрите объяснение в начальной версии

int* selection = new int[len << 1]; // то же что и new int[len * 2]
int left = len - 1; // индекс для хранения новых минимальных элементов
int right = len;  // индекс для хранения новых максимальных элементов

Заполним первые несколько элементов массива выборки

selection[left--] = arr[0];
for (int i = 1; i < localCatchUp; ++i) {
	selection[right++] = arr[i];
}

Напомню, что в левую сторону от центра массива выборки идут новые минимумы, а в правую — новые максимумы

Создадим массивы для хранения не избранных элементов

int restLen = len >> 1; // то же что и len / 2
int* restFirst = new int[restLen];
int* restSecond = new int[restLen];

int restFirstLen = 0;
int restSecondLen = 0;

Теперь, самое главное — правильная выборка элементов из исходного массива

Цикл начинается с localCatchUp (потому что предыдущие элементы уже попали в нашу выборку как значения от которых мы будем отталкиваться). И проходит до конца. Так что после в конце концов все элементы распределятся либо в массив выборки либо в один из массивов недо-выборки.

Для проверки, можем ли мы вставить элемент в выборку, мы просто будем проверять больше (или равен) ли он элементу на 8 позиций левее (right − localCatchUp). Если это так, то мы просто одним проходом по этим элементам вставляем его на нужную позицию. Это было для правой стороны, то-есть для максимальных элементов. Таким же образом делаем с обратной стороны для минимальных. Если не удалось вставить его ни в одну сторону выборки значит кидаем его в один из rest-массивов.

Цикл будет выглядеть примерно так:

for (int i = localCatchUp; i < len; ++i) {

	if (selection[right - localCatchUp] <= arr[i])
	{
		selection[right] = arr[i];

		for (int j = right; selection[j - 1] > selection[j]; --j)
			swap(selection[j - 1], selection[j]);

		++right;
		continue;
	}

	if (selection[left + localCatchUp] >= arr[i])
	{
		selection[left] = arr[i];

		for (int j = left; selection[j] >= selection[j + 1]; ++j)
			swap(selection[j], selection[j + 1]);

		--left;
		continue;
	}

	if (i & 1) { // i - непарное
		restFirst[restFirstLen++] = arr[i];
	}
	else {
		restSecond[restSecondLen++] = arr[i];
	}
}

Опять же, что здесь происходит? Сначала пытаемся пихнуть элемент в максимумы. Не получается? — Если возможно, кидаем его в минимумы. При невозможности и это сделать — кладём его в restFirst или restSecond.

Самое сложное уже позади. Теперь после цикла у нас есть отсортированный массив с выборкой (элементы начинаются с индекса [left + 1] и оканчиваются в [right − 1]), а также массивы restFirst и restSecond длиной restFirstLen и restSecondLen соответственно.

Как и в предыдущем примере, перед рекурсивным вызовом высвобождаем память от основного массива (все его элементы мы уже и так сохранили)

delete[] arr; 

У нас массив selection может содержать много ячеек неиспользуемой памяти. Перед рекурсивным вызовом нужно освободить её.

Освобождаем неиспользуемую память

int selectionLen = right - left - 1; // просто длина нашей выборки
int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); // копируем все элементы выборки в новый массив
			
delete[] selection; // удаляем массив размером 2 * len элементов и
selection = copy; // вместо него используем ровно столько памяти, сколько нужно

Теперь запускаем нашу функцию сортировки рекурсивно для массивов restFirst и restSecond

Для понимания того как оно всё отработает, сначала нужно посмотреть код до конца. Пока что нужно просто поверить что после рекурсивных вызовов массивы restFirst и restSecond будут отсортированными.

newGenerationSort(restFirst, restFirstLen);
newGenerationSort(restSecond, restSecondLen);

И, наконец, нам нужно слить 3 массива в результирующий и назначить его указателю arr.

Можно было бы сначала слить restFirst + restSecond в какой-нибудь массив restFull, а потом уже производить слияние selection + restFull. Но данный алгоритм обладает таким свойством, что скорее всего массив selection будет содержать намного меньше элементов, чем любой из rest-массивов. Припустим в selection содержится 100 элементов, в restFirst — 990, а в restSecond — 1010. Тогда для создания restFull массива нужно произвести 990 + 1010 = 2000 операций копирования. После чего для слияния с selection — ещё 2000 + 100 копирований. Итого при таком подходе всего копирований будет 2000 + 2100 = 4100.

Давайте применим здесь оптимизацию. Сначала сливаем selection и restFirst в массив selection. Операций копирования: 100 + 990 = 1090. Далее сливаем массивы selection и restSecond на что потратим ещё 1090 + 1010 = 2100 копирований. Суммарно выйдет 2100 + 1090 = 3190, что почти на четверть меньше, нежели при предыдущем подходе.

Финальное слияние массивов

int* part2;
int part2Len;
if (selectionLen < restFirstLen) {
	glueDelete(selection, restFirst, restFirstLen, selection, selectionLen); // selection += restFirst 
	selectionLen += restFirstLen;
				
	part2 = restSecond;	
	part2Len = restSecondLen;
}
else {
	glueDelete(part2, restFirst, restFirstLen, restSecond, restSecondLen); // part2 = restFirst + restSecond
	part2Len = restFirstLen + restSecondLen;
}
			
glueDelete(arr, selection, selectionLen, part2, part2Len);

Как видим, если нам выгодней сливать selection с restFirst, то мы так и делаем. Иначе мы сливаем как в «restFull»

Финальный код алгоритма:

/// works only if arr is pointer assigned by new keyword
void newGenerationSort(int*& arr, int len) {
	int localCatchUp = min(catchUp, len); // потому что мы не можем пытаться вставлять элемент за границами массива
	insertionSort(arr, 0, localCatchUp - 1); // для начала сортируем первые localCatchUp элементов

	if (len <= localCatchUp) // на случай если это массив на n <= catchUp элементов
		return; // а также это база рекурсии

	int* selection = new int[len << 1]; // то же что и new int[len * 2]
	int left = len - 1; // индекс для хранения новых минимальных элементов
	int right = len;  // индекс для хранения новых максимальных элементов
			
	selection[left--] = arr[0];
	for (int i = 1; i < localCatchUp; ++i) {
		selection[right++] = arr[i];
	}

	int restLen = len >> 1;
	int* restFirst = new int[restLen];
	int* restSecond = new int[restLen];

	int restFirstLen = 0;
	int restSecondLen = 0;

	for (int i = localCatchUp; i < len; ++i) {

		if (selection[right - localCatchUp] <= arr[i]) 
		{
			selection[right] = arr[i];

			for (int j = right; selection[j - 1] > selection[j]; --j)
				swap(selection[j - 1], selection[j]);

			++right;
			continue;
		}

		if (selection[left + localCatchUp] >= arr[i])
		{
			selection[left] = arr[i];

			for (int j = left; selection[j] >= selection[j + 1]; ++j)
				swap(selection[j], selection[j + 1]);

			--left;
			continue;
		}

		if (i & 1) { // i - непарное
			restFirst[restFirstLen++] = arr[i];
		}
		else {
			restSecond[restSecondLen++] = arr[i];
		}
	}
	delete[] arr; 

	int selectionLen = right - left - 1; // просто длина нашей выборки
	int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); // копируем все элементы выборки в новый массив
			
	delete[] selection; // удаляем массив размером 2 * len элементов и
	selection = copy; // вместо него используем ровно столько памяти, сколько нужно

	newGenerationSort(restFirst, restFirstLen);
	newGenerationSort(restSecond, restSecondLen);

	int* part2;
	int part2Len;
	if (selectionLen < restFirstLen) {
		glueDelete(selection, restFirst, restFirstLen, selection, selectionLen); // selection += restFirst 
		selectionLen += restFirstLen;
				
		part2 = restSecond;	
		part2Len = restSecondLen;
	}
	else {
		glueDelete(part2, restFirst, restFirstLen, restSecond, restSecondLen); // part2 = restFirst + restSecond
		part2Len = restFirstLen + restSecondLen;
	}
			
	glueDelete(arr, selection, selectionLen, part2, part2Len);
}

Теперь время тестирования

Основной код в Source.cpp:

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include "time_utilities.h"
#include "sort_utilities.h"

using namespace std;
using namespace rela589n;

void printArr(int* arr, int len) {
	for (int i = 0; i < len; ++i) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

bool arraysEqual(int* arr1, int* arr2, int len) {
	for (int i = 0; i < len; ++i) {
		if (arr1[i] != arr2[i]) {
			return false;
		}
	}
	return true;
}

int* createArray(int length) {
	int* a1 = new int[length];

	for (int i = 0; i < length; i++) {
		a1[i] = rand();
		//a1[i] = (i + 1) % (length / 4);
	}

	return a1;
}

int* array_copy(int* arr, int length) {
	int* a2 = new int[length];
	for (int i = 0; i < length; i++) {
		a2[i] = arr[i];
	}

	return a2;
}

void tester(int tests, int length) {
	double t1, t2;

	int** arrays1 = new int* [tests];
	int** arrays2 = new int* [tests];

	for (int t = 0; t < tests; ++t) { // просто заполнение массивов
		int* arr1 = createArray(length);
		arrays1[t] = arr1;
		arrays2[t] = array_copy(arr1, length);
	}

	t1 = getCPUTime();
	for (int t = 0; t < tests; ++t) {
	 	quickSort(arrays1[t], 0, length - 1);
	}
	t2 = getCPUTime();
	
	cout << "Avg Qsort       time for " << length << " elements: " << (t2 - t1) * 1000 / tests << endl;
	
	int portion = catchUp = 8;
	
	t1 = getCPUTime();
	for (int t = 0; t < tests; ++t) {
		newGenerationSort(arrays2[t], length);
	}	
	t2 = getCPUTime();

	cout << "Avg newGenSort  time for " << length << " elements: " << (t2 - t1) * 1000 / tests //<< " Catch up coef: "<< portion
		<< endl;

	bool confirmed = true; // проверяем идентичны ли массивы
	for (int t = 0; t < tests; ++t) {
		if (!arraysEqual(arrays1[t], arrays2[t], length)) {
			confirmed = false;
			break;
		}
	}
	if (confirmed) {
		cout << "Confirmed" << endl;
	}
	else {
		cout << "Review your code! Something wrong..." << endl;
	}
}
 
int main() {
	srand(time(NULL));

	int length;
	double t1, t2;

	cout << "size: ";
	cin >> length;
	
	int t;
	cout << "tests: ";
	cin >> t;
	tester(t, length);
	system("pause");

	return 0;
}

Реализация Quick Sort, что была использована для сравнения при тестировании:

Небольшая ремарка: я использовал именно эту реализацию quickSort для того, чтобы всё было честно. Стандартная sort из библиотеки algorithm хотя и универсальна, но работает в 2 раза медленней представленной ниже.

// [min, max]
int random(int min, int max) {
	return min + rand() % ((max + 1) - min);
}

void quickSort(int * arr, int b, int e)
{
	int l = b, r = e;
	int piv = arr[random(l, r)];
	while (l <= r)	
	{
		for (; arr[l] < piv; ++l);

		for (; arr[r] > piv; --r);

		if (l <= r)
			swap(arr[l++], arr[r--]);
	}
	if (b < r)
		quickSort(arr, b, r);
	if (e > l)
		quickSort(arr, l, e);
}

Все тесты были проведены на машине на проц. Intel core i3 7100u и 8ГБ ОЗУ

Полностью рандомный массив

a1[i] = rand();

image
image
image
image
image

Частично упорядоченный массив

a1[i] = (i + 1) % (length / 4);

image
image
image
image
image

Полностью отсортированный массив

a1[i] = (i + 1);

image
image
image
image
image

Выводы

Как видим, алгоритм работает, и работает хорошо. По крайней мере всё чего мы хотели, было достигнуто. На счёт стабильности, не уверен, не проверял. Можете сами проверить. Но по-идее она должна достигаться очень легко. Просто в некоторых местах вместо знака > поставить ≥ или что-то того.

Автор: Сидельник Евгений

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js