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





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);
}


getCPUTime - измерение процессорного времени:
#pragma once

#if defined(_WIN32)
#include <Windows.h>

#elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__))
#include <unistd.h>
#include <sys/resource.h>
#include <sys/times.h>
#include <time.h>

#else
#error "Unable to define getCPUTime( ) for an unknown OS."
#endif

/**
 * Returns the amount of CPU time used by the current process,
 * in seconds, or -1.0 if an error occurred.
 */
double getCPUTime()
{
#if defined(_WIN32)
	/* Windows -------------------------------------------------- */
	FILETIME createTime;
	FILETIME exitTime;
	FILETIME kernelTime;
	FILETIME userTime;
	if (GetProcessTimes(GetCurrentProcess(),
		&create;Time, &exit;Time, &kernel;Time, &user;Time) != -1)
	{
		SYSTEMTIME userSystemTime;
		if (FileTimeToSystemTime(&user;Time, &user;SystemTime) != -1)
			return (double)userSystemTime.wHour * 3600.0 +
			(double)userSystemTime.wMinute * 60.0 +
			(double)userSystemTime.wSecond +
			(double)userSystemTime.wMilliseconds / 1000.0;
	}

#elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__))
	/* AIX, BSD, Cygwin, HP-UX, Linux, OSX, and Solaris --------- */

#if defined(_POSIX_TIMERS) && (_POSIX_TIMERS > 0)
	/* Prefer high-res POSIX timers, when available. */
	{
		clockid_t id;
		struct timespec ts;
#if _POSIX_CPUTIME > 0
		/* Clock ids vary by OS.  Query the id, if possible. */
		if (clock_getcpuclockid(0, &id;) == -1)
#endif
#if defined(CLOCK_PROCESS_CPUTIME_ID)
			/* Use known clock id for AIX, Linux, or Solaris. */
			id = CLOCK_PROCESS_CPUTIME_ID;
#elif defined(CLOCK_VIRTUAL)
			/* Use known clock id for BSD or HP-UX. */
			id = CLOCK_VIRTUAL;
#else
			id = (clockid_t)-1;
#endif
		if (id != (clockid_t)-1 && clock_gettime(id, &ts;) != -1)
			return (double)ts.tv_sec +
			(double)ts.tv_nsec / 1000000000.0;
	}
#endif

#if defined(RUSAGE_SELF)
	{
		struct rusage rusage;
		if (getrusage(RUSAGE_SELF, &rusage;) != -1)
			return (double)rusage.ru_utime.tv_sec +
			(double)rusage.ru_utime.tv_usec / 1000000.0;
	}
#endif

#if defined(_SC_CLK_TCK)
	{
		const double ticks = (double)sysconf(_SC_CLK_TCK);
		struct tms tms;
		if (times(&tms;) != (clock_t)-1)
			return (double)tms.tms_utime / ticks;
	}
#endif

#if defined(CLOCKS_PER_SEC)
	{
		clock_t cl = clock();
		if (cl != (clock_t)-1)
			return (double)cl / (double)CLOCKS_PER_SEC;
	}
#endif

#endif

	return -1;      /* Failed. */
}


Все тесты были проведены на машине на проц. 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

Выводы


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

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (38):

  1. Methos
    /#21166792 / +2

    Кратко.


    Я написал новый пупер алгоритм сортировки, он работает быстрее, чем быстрая сортировка, но я не уверен, что она работает правильно.

    • dipsy
      /#21168034 / +5

      Эволюция программиста:
      — свой, улучшенный, алгоритм сортировки
      — свой, улучшенный, алгоритм компрессии данных
      — своя библиотека контейнеров, улучшенная по сравнению с std::*
      — долгий и мучительный рефакторинг по замене всего вышенаписанного на «стандартные»

  2. Deosis
    /#21166994

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

  3. a1ex322
    /#21166996

    upd. to Methos:

    там вроде в коде есть проверка идентичности с результатом квиксорта (да, это не строгое доказательство)

  4. vesper-bot
    /#21167216

    А худший случай так и остался по сложности О(n^2)? Тогда чем эта сортировка лучше сортировки слиянием?

    • rela589n
      /#21167584 / +1

      Нет, худший случай O (n log n).

      • fougasse
        /#21167628 / +1

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

        Вы серьезно?

        • rela589n
          /#21170442

          Возможно на счёт

          вместо знака > поставить ?
          я переборщил, но у меня не было написать стабильный алгоритм. Тот же Quick Sort не является стабильным алгоритмом сортировки

  5. lair
    /#21167242

    (а) какая сложность по памяти?
    (б) что по сравнению с timsort?

    • rela589n
      /#21167798 / +1

      (а) O (3n)
      (б) с тимсортом не сравнивал

      • lair
        /#21167826

        O (3n)

        А у квиксорта — O(log n), если мне память не изменяет.


        с тимсортом не сравнивал

        А зря, потому что про него известно, что он быстрее квиксорта.

      • Dim0v
        /#21168014

        (а) O (3n)

        У вас на момент рекурсивного вызова выделено и не освобождено О(n) памяти (массивы restFirst и restSecond). Глубина рекурсии О(log n). Соответственно, сложность по памяти О(n * log n).


        UPD: пардон, там arr освобождается. Все таки O(n)

      • Dim0v
        /#21169470 / +2

        с тимсортом не сравнивал

        Сравнил за вас.
        Тимсорт лучше чуть менее, чем везде.


        Время выполнения на моей машине:


        image


                           qsort  std::sort    timsort    newSort
               random      79.56    51.2199    85.0301      122.1
               sorted    36.9301    13.1499   0.339997    4.02001
          part-sorted    78.5999       46.2    28.0399         31
         chunk-sorted    93.1501      43.41    2.73001       11.7
              rsorted      37.88      10.57   0.789863       4.54
         part-rsorted    71.7799      35.73       36.5      32.44
        chunk-rsorted      94.85      47.71    3.04001      13.71

        Исходник (слегка модифицированный авторский): https://pastebin.com/kQVC6Cam

        • rela589n
          /#21170276 / +2

          Это всё конечно очень круто, но в приведённом вами коде сортируются разные массивы. Если мы рандомно сгенерировали массив для сортировки с помощью qsort, а потом генерируем совсем другой массив с другими элементами для алгоритма timsort, то как-то необъективно получается.

          • Dim0v
            /#21170448 / +3

            В 4 случаях из 7 всем алгоритмам подаются абсолютно одинаковые массивы. В остальных 3 случаях данные отличаются, но их характер — нет. Необъективным было бы сравнивать одного случайной значение с другим. И на основе одного сравнения делать выводы. Здесь же этих случайных значений сто миллионов штук. И они имеют одинаковое распределение. Так что сравнение вполне себе объективно.


            Впрочем, если несогласны — добавьте строчку srand(1); между 982 и 983 строками. Получите одинаковые массивы и сравнение, которое на 95% объективнее. Вот только результат сравнения будет таким-же.

            • rela589n
              /#21170500 / +1

              Очень странно, я запустил ваш исходник у себя (что я изменил — так это то, что уменьшил в 10 раз количество элементов, так как при 106 ну ооочень долго выполняется), и результаты у нас кардинально отличаются. Можете посмотреть скрин ниже. Запускал из-под 19 студии.
              image
              На самом деле очень странно наблюдать такое поведение.

              • Dim0v
                /#21170522 / +3

                Потому что измерять производительность в отладочной сборке — все равно что измерять скорость гоночных болидов в болоте. Включите оптимизации компилятора и картина резко изменится. Хотя с моей может на 100% и не совпасть. Я собирал с gcc.

                • rela589n
                  /#21170568 / +2

                  Да, вы правы. Теперь всё стало на свои места. Вот такой результат:
                  image

                • speshuric
                  /#21176282 / +1

                  А бывает наоборот. Я как-то несколько лет назад находил багу в .NET, когда неудачный алгоритм инлайна в релизном режиме приводил к экспоненциально долгому и также экспоненциально прожорливому потреблению памяти JIT. Сейчас (после моего репорта в core, но проявлялось и в framework) багу уже пофиксили. Хотя, на мой взгляд и неидеально пофиксили, но всяко лучше, чем было.

              • lair
                /#21170524 / +3

                Запускал из-под 19 студии.

                Ээээ, вы тесты гоняли на дебажной сборке?


                (судя еще и по Debug на скриншоте)

        • rela589n
          /#21170292

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

          • Dim0v
            /#21170474 / +2

            Но это дало бы доп. прирост к скорости.

            Не дало бы. Ваши сливаемые массивы формируются совершенно иным образом, чем в тимсорт. Там за счет галопа получается выгода от частичной упорядоченности входных данных. У вас же на момент слияния данные из входного массива разбросаны по 3 другим массивам довольно таки произвольным образом.


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

  6. fougasse
    /#21167342 / +1

    • Зачем ручное управление памятью? Вектора тормозят? Меряли?
    • Зачем битовая арифметика? У вас простое возведение в степень тормозит? Аналогично с «i & 1».
    • «удаляем массив размером 2 * len элементов » или «2 ^ len»
    • "/// works only if arr is pointer assigned by new keyword" — вообще грусть какая-то, ИМХО.
    • Оценивали сложность по памяти?

    • rela589n
      /#21167916

      1) Когда я начинал писать этот алгоритм, то не планировал его вообще куда-то выкладывать. Я писал так, как мне было удобно работать в тот момент.
      2) Опять же мне приятней писать i & 1 чем i % 2 != 0
      3) Мы выделяли 2 * len памяти, соответственно освобождаем тоже 2 * len
      4) Это решается простой обёрткой над представленной реализацией. Мы же можем полностью скопировать массив и сортировать копию. Предоставленная здесь функция рекурсивная, и в ней есть хитрые манипуляции с памятью.
      5) Без обёртки O (3n). Если написать над ней обёртку, то O (4n).

      • Dim0v
        /#21167974

        Без обёртки O (3n). Если написать над ней обёртку, то O (4n).

        O(3n) = O(4n) = O(100500n) = O(n)

      • fougasse
        /#21168116 / +1

        1). Но ведь выложили
        3). Зачем делать len << 1, а не просто len * 2, если в комментариях у вас умножение? Попахивает, простите, байтойобсблудством
        5). Хитрые манипуляции имеют смысл? Константы в O-нотации принято игнорировать.

        Про сравнение
        Вообще, сравнивать in-place алгоритм с O(log n) дополнительной памяти и O(n) странновато.
        Тем более, с хитро скопируемой памятью.

        • maxzhurkin
          /#21170942 / +1

          Вам намекают, что их ещё и принято опускать

  7. Newm
    /#21168076 / +1

    У моего внутримозгового подсвечивателя ошибок и предупреждений загорелась лампочка на результатах тестов по времени. И какого-либо обоснования, почему на сортировку одного элемента при 100 тыс. элементов в массиве уходит больше времени, чем на сортировку при 10 тыс. и при 1 млн., я лично найти не могу (на случайном массиве). Мне очень кажется, что где-то там скрыт косяк.

    Я не вникал полностью в предложенный алгоритм, но для квиксорта это однозначно ненормальное поведение.

    • fougasse
      /#21168146

      Резона смотреть на одиночные тесты консольного приложения особо нет, как мне кажется.
      Тут снова возникает вопрос о правильной организации бенчмарка.
      Иначе получается, что getCPUTime() (кстати, что оно такое?) меряет непонятно что.
      Вдруг винда свопнтуься решила/апдейт качает или в телеграм нотификации пришли?

      • Newm
        /#21169042

        Ну, тестов там не мало. Причем ситуация повторяется в двух случаях, а в третьем с сортированным массивом квиксорт тоже показывает странное изменение по времени. Именно поэтому у меня и возникли подозрения, что имеются какие-то проблемы с измерениями.

  8. vics001
    /#21169112

    Вся любовь к QuickSort в том, что он делает in-place сортировку. Если ваш массив занимает 500 МБ, то вам не нужен новый массив и т.п. И 2-е в среднем статистически QuickSort работает O(n log n), т.е. попасть на O(n^2) случайно достаточно сложно.

  9. red_andr
    /#21169402

    Если изобретается новый гибридный алгоритм, то и сравнивать надо с такими же гибридными, а не с древним QuickSort (на минуточку, ему уже 60 лет!). Тут уже упомянули Timsort, который за последние годы стал стандартом во многих языках. Есть и другие.

  10. yleo
    /#21170312 / +1

    А какой есть хороший (ну более-менее) набор готовых тестов для оценки сортировок?


    Лучше что пока нашел — это "набора сортировок" от Christopher Swenson.

    • yleo
      /#21170696 / +1

      Взял исходники здесь и добавил в обозначенный выше бенчмарк.
      Пришлось немного поправить:


      1. Вместо int сортировать int64_t, как в остальных сортировках в бенчмарке.
      2. Увязать delete[] и malloc() в бенчмарке (он примерно на C):
        • каждый delete[] ptr => if (pfr != malloced_array) delete[] ptr;
        • копировать отсортированный массив если он был перевыделен (да, это искажает результаты, но не принципиально).

      В сухом остатке у показанной сортировки:


      • большие проблемы с low cardinality, до 1000 раз медленнее
      • на случайных данных вдвое медленнее std::sort
      • на упорядоченных данных часто примерно как timsort, иногда выигрывает в 2 раза, но местами проигрывает в 4-5-6 раз.

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


      gcc версия 9.2.1 20190827 (Red Hat 9.2.1-1) (GCC)
      Целевая архитектура: x86_64-redhat-linux
      CFLAGS = -Ofast -g -Wall -pedantic

      Все результаты (смотрим на sort_rela589n_int64)
      Running tests with random:
      extra.h yysort1_int64         - ok,   869995.0 usec
      extra.h yysort2_int64         - ok,   900374.0 usec
      extra.h sort_rela589n_int64   - ok,  1675713.0 usec
      sort.h tim_sort               - ok,  1629556.0 usec
      sort.h quick_sort             - ok,  1132862.0 usec
      extra.h std_sort_int64        - ok,   999762.0 usec
      extra.h std_stable_int64      - ok,  1285915.0 usec
      sort.h heap_sort              - ok,  1146402.0 usec
      sort.h merge_sort             - ok,  1503107.0 usec
      sort.h shell_sort             - ok,  2176027.0 usec
      sort.h merge_sort_in_place    - ok,  1463473.0 usec
      sort.h grail_sort             - ok,  1808871.0 usec
      sort.h sqrt_sort              - ok,  1515565.0 usec
      stdlib qsort                  - ok,  2027280.0 usec
      -------
      Running tests with random 50% duplicates:
      extra.h yysort1_int64         - ok,   860580.0 usec
      extra.h yysort2_int64         - ok,   898808.0 usec
      extra.h sort_rela589n_int64   - ok,  1669673.0 usec
      sort.h tim_sort               - ok,  1625739.0 usec
      sort.h quick_sort             - ok,  1120857.0 usec
      extra.h std_sort_int64        - ok,   996282.0 usec
      extra.h std_stable_int64      - ok,  1282137.0 usec
      sort.h heap_sort              - ok,  1140383.0 usec
      sort.h merge_sort             - ok,  1498133.0 usec
      sort.h shell_sort             - ok,  2147107.0 usec
      sort.h merge_sort_in_place    - ok,  1459049.0 usec
      sort.h grail_sort             - ok,  1810396.0 usec
      sort.h sqrt_sort              - ok,  1509897.0 usec
      stdlib qsort                  - ok,  2040143.0 usec
      -------
      Running tests with random two values:
      extra.h yysort1_int64         - ok,   253859.0 usec
      extra.h yysort2_int64         - ok,   128689.0 usec
      extra.h sort_rela589n_int64   - ok, 94094388.0 usec
      sort.h tim_sort               - ok,   452126.0 usec
      sort.h quick_sort             - ok,   115704.0 usec
      extra.h std_sort_int64        - ok,   229533.0 usec
      extra.h std_stable_int64      - ok,   362162.0 usec
      sort.h heap_sort              - ok,   580296.0 usec
      sort.h merge_sort             - ok,   525983.0 usec
      sort.h shell_sort             - ok,   485811.0 usec
      sort.h merge_sort_in_place    - ok,   434436.0 usec
      sort.h grail_sort             - ok,   611444.0 usec
      sort.h sqrt_sort              - ok,   544184.0 usec
      stdlib qsort                  - ok,   811069.0 usec
      -------
      Running tests with random of 0..9:
      extra.h yysort1_int64         - ok,   406745.0 usec
      extra.h yysort2_int64         - ok,   315560.0 usec
      extra.h sort_rela589n_int64   - ok,  7734804.0 usec
      sort.h tim_sort               - ok,   903047.0 usec
      sort.h quick_sort             - ok,   288444.0 usec
      extra.h std_sort_int64        - ok,   386615.0 usec
      extra.h std_stable_int64      - ok,   665899.0 usec
      sort.h heap_sort              - ok,   984863.0 usec
      sort.h merge_sort             - ok,   851956.0 usec
      sort.h shell_sort             - ok,   836794.0 usec
      sort.h merge_sort_in_place    - ok,   783045.0 usec
      sort.h grail_sort             - ok,  1697737.0 usec
      sort.h sqrt_sort              - ok,   881796.0 usec
      stdlib qsort                  - ok,  1303944.0 usec
      -------
      Running tests with mixed-pattern (1/2 sorted, 1/6 reverse, 1/3 random):
      extra.h yysort1_int64         - ok,   653220.0 usec
      extra.h yysort2_int64         - ok,   709562.0 usec
      extra.h sort_rela589n_int64   - ok,   708971.0 usec
      sort.h tim_sort               - ok,   646852.0 usec
      sort.h quick_sort             - ok,   885766.0 usec
      extra.h std_sort_int64        - ok,   789911.0 usec
      extra.h std_stable_int64      - ok,   625716.0 usec
      sort.h heap_sort              - ok,  1078595.0 usec
      sort.h merge_sort             - ok,   788254.0 usec
      sort.h shell_sort             - ok,  1972692.0 usec
      sort.h merge_sort_in_place    - ok,   678949.0 usec
      sort.h grail_sort             - ok,   979281.0 usec
      sort.h sqrt_sort              - ok,   769563.0 usec
      stdlib qsort                  - ok,  1114687.0 usec
      -------
      Running tests with mixed-pattern 50% duplicates:
      extra.h yysort1_int64         - ok,   651027.0 usec
      extra.h yysort2_int64         - ok,   710886.0 usec
      extra.h sort_rela589n_int64   - ok,   707473.0 usec
      sort.h tim_sort               - ok,   720871.0 usec
      sort.h quick_sort             - ok,   868391.0 usec
      extra.h std_sort_int64        - ok,   785505.0 usec
      extra.h std_stable_int64      - ok,   623365.0 usec
      sort.h heap_sort              - ok,  1075865.0 usec
      sort.h merge_sort             - ok,   794544.0 usec
      sort.h shell_sort             - ok,  1944434.0 usec
      sort.h merge_sort_in_place    - ok,   682350.0 usec
      sort.h grail_sort             - ok,  1044301.0 usec
      sort.h sqrt_sort              - ok,   771323.0 usec
      stdlib qsort                  - ok,  1180723.0 usec
      -------
      Running tests with mixed-pattern two values:
      extra.h yysort1_int64         - ok,   212801.0 usec
      extra.h yysort2_int64         - ok,    90349.0 usec
      extra.h sort_rela589n_int64   - ok, 70880347.0 usec
      sort.h tim_sort               - ok,   164127.0 usec
      sort.h quick_sort             - ok,   101332.0 usec
      extra.h std_sort_int64        - ok,   182024.0 usec
      extra.h std_stable_int64      - ok,   235439.0 usec
      sort.h heap_sort              - ok,   531226.0 usec
      sort.h merge_sort             - ok,   377192.0 usec
      sort.h shell_sort             - ok,   429685.0 usec
      sort.h merge_sort_in_place    - ok,   187419.0 usec
      sort.h grail_sort             - ok,   396649.0 usec
      sort.h sqrt_sort              - ok,   381190.0 usec
      stdlib qsort                  - ok,   603217.0 usec
      -------
      Running tests with mixed-pattern of 0..9:
      extra.h yysort1_int64         - ok,   301082.0 usec
      extra.h yysort2_int64         - ok,   220010.0 usec
      extra.h sort_rela589n_int64   - ok,  4049493.0 usec
      sort.h tim_sort               - ok,   327608.0 usec
      sort.h quick_sort             - ok,   193150.0 usec
      extra.h std_sort_int64        - ok,   282951.0 usec
      extra.h std_stable_int64      - ok,   348781.0 usec
      sort.h heap_sort              - ok,   928633.0 usec
      sort.h merge_sort             - ok,   492125.0 usec
      sort.h shell_sort             - ok,   653055.0 usec
      sort.h merge_sort_in_place    - ok,   343271.0 usec
      sort.h grail_sort             - ok,   944962.0 usec
      sort.h sqrt_sort              - ok,   517400.0 usec
      stdlib qsort                  - ok,   787898.0 usec
      -------
      Running tests with sorted:
      extra.h yysort1_int64         - ok,   140487.0 usec
      extra.h yysort2_int64         - ok,    22329.0 usec
      extra.h sort_rela589n_int64   - ok,    78184.0 usec
      sort.h tim_sort               - ok,    12440.0 usec
      sort.h quick_sort             - ok,   259474.0 usec
      extra.h std_sort_int64        - ok,   187773.0 usec
      extra.h std_stable_int64      - ok,   161101.0 usec
      sort.h heap_sort              - ok,  1001063.0 usec
      sort.h merge_sort             - ok,   294122.0 usec
      sort.h shell_sort             - ok,   349411.0 usec
      sort.h merge_sort_in_place    - ok,    28568.0 usec
      sort.h grail_sort             - ok,   390306.0 usec
      sort.h sqrt_sort              - ok,   240751.0 usec
      stdlib qsort                  - ok,   469580.0 usec
      -------
      Running tests with sorted 93.75%:
      extra.h yysort1_int64         - ok,   315492.0 usec
      extra.h yysort2_int64         - ok,   332510.0 usec
      extra.h sort_rela589n_int64   - ok,   688122.0 usec
      sort.h tim_sort               - ok,   527578.0 usec
      sort.h quick_sort             - ok,   667057.0 usec
      extra.h std_sort_int64        - ok,   343515.0 usec
      extra.h std_stable_int64      - ok,   422551.0 usec
      sort.h heap_sort              - ok,  1028983.0 usec
      sort.h merge_sort             - ok,   549670.0 usec
      sort.h shell_sort             - ok,  1811294.0 usec
      sort.h merge_sort_in_place    - ok,   614558.0 usec
      sort.h grail_sort             - ok,   816988.0 usec
      sort.h sqrt_sort              - ok,   669301.0 usec
      stdlib qsort                  - ok,   930576.0 usec
      -------
      Running tests with reverse:
      extra.h yysort1_int64         - ok,   272676.0 usec
      extra.h yysort2_int64         - ok,   313761.0 usec
      extra.h sort_rela589n_int64   - ok,    83115.0 usec
      sort.h tim_sort               - ok,    23235.0 usec
      sort.h quick_sort             - ok,   315033.0 usec
      extra.h std_sort_int64        - ok,   184726.0 usec
      extra.h std_stable_int64      - ok,   251171.0 usec
      sort.h heap_sort              - ok,   953360.0 usec
      sort.h merge_sort             - ok,   401169.0 usec
      sort.h shell_sort             - ok,   496127.0 usec
      sort.h merge_sort_in_place    - ok,   323996.0 usec
      sort.h grail_sort             - ok,   479127.0 usec
      sort.h sqrt_sort              - ok,   257342.0 usec
      stdlib qsort                  - ok,   535662.0 usec
      -------
      Running tests with 111......000:
      extra.h yysort1_int64         - ok,   164210.0 usec
      extra.h yysort2_int64         - ok,    20986.0 usec
      extra.h sort_rela589n_int64   - ok, 94005419.0 usec
      sort.h tim_sort               - ok,    17461.0 usec
      sort.h quick_sort             - ok,    44549.0 usec
      extra.h std_sort_int64        - ok,   135267.0 usec
      extra.h std_stable_int64      - ok,   171308.0 usec
      sort.h heap_sort              - ok,   496364.0 usec
      sort.h merge_sort             - ok,   300909.0 usec
      sort.h shell_sort             - ok,   359109.0 usec
      sort.h merge_sort_in_place    - ok,    61315.0 usec
      sort.h grail_sort             - ok,   258391.0 usec
      sort.h sqrt_sort              - ok,   309822.0 usec
      stdlib qsort                  - ok,   489699.0 usec
      -------
      Running tests with 999..., 888..., ..., ...000:
      extra.h yysort1_int64         - ok,   163028.0 usec
      extra.h yysort2_int64         - ok,    21040.0 usec
      extra.h sort_rela589n_int64   - ok, 33905532.0 usec
      sort.h tim_sort               - ok,    34008.0 usec
      sort.h quick_sort             - ok,    99381.0 usec
      extra.h std_sort_int64        - ok,   139307.0 usec
      extra.h std_stable_int64      - ok,   176955.0 usec
      sort.h heap_sort              - ok,   859782.0 usec
      sort.h merge_sort             - ok,   312193.0 usec
      sort.h shell_sort             - ok,   372891.0 usec
      sort.h merge_sort_in_place    - ok,   109063.0 usec
      sort.h grail_sort             - ok,   473525.0 usec
      sort.h sqrt_sort              - ok,   355316.0 usec
      stdlib qsort                  - ok,   513460.0 usec
      -------
      Running tests with all same:
      extra.h yysort1_int64         - ok,   167847.0 usec
      extra.h yysort2_int64         - ok,    21873.0 usec
      extra.h sort_rela589n_int64   - ok,    78372.0 usec
      sort.h tim_sort               - ok,    12293.0 usec
      sort.h quick_sort             - ok,    18023.0 usec
      extra.h std_sort_int64        - ok,   137651.0 usec
      extra.h std_stable_int64      - ok,   161931.0 usec
      sort.h heap_sort              - ok,    68188.0 usec
      sort.h merge_sort             - ok,   292633.0 usec
      sort.h shell_sort             - ok,   348899.0 usec
      sort.h merge_sort_in_place    - ok,    28329.0 usec
      sort.h grail_sort             - ok,   207439.0 usec
      sort.h sqrt_sort              - ok,   255837.0 usec
      stdlib qsort                  - ok,   459560.0 usec
      -------
      Running tests with sorted blocks of length 10:
      extra.h yysort1_int64         - ok,   831530.0 usec
      extra.h yysort2_int64         - ok,   868527.0 usec
      extra.h sort_rela589n_int64   - ok,  1670283.0 usec
      sort.h tim_sort               - ok,  1516381.0 usec
      sort.h quick_sort             - ok,  1083222.0 usec
      extra.h std_sort_int64        - ok,   961874.0 usec
      extra.h std_stable_int64      - ok,  1134245.0 usec
      sort.h heap_sort              - ok,  1128264.0 usec
      sort.h merge_sort             - ok,  1339936.0 usec
      sort.h shell_sort             - ok,  2029549.0 usec
      sort.h merge_sort_in_place    - ok,  1314025.0 usec
      sort.h grail_sort             - ok,  1688303.0 usec
      sort.h sqrt_sort              - ok,  1383832.0 usec
      stdlib qsort                  - ok,  1808273.0 usec
      -------
      Running tests with sorted blocks of length 100:
      extra.h yysort1_int64         - ok,   698704.0 usec
      extra.h yysort2_int64         - ok,   737751.0 usec
      extra.h sort_rela589n_int64   - ok,  1664662.0 usec
      sort.h tim_sort               - ok,   842203.0 usec
      sort.h quick_sort             - ok,   952365.0 usec
      extra.h std_sort_int64        - ok,   832443.0 usec
      extra.h std_stable_int64      - ok,   832485.0 usec
      sort.h heap_sort              - ok,  1100130.0 usec
      sort.h merge_sort             - ok,   992872.0 usec
      sort.h shell_sort             - ok,  1722663.0 usec
      sort.h merge_sort_in_place    - ok,  1054561.0 usec
      sort.h grail_sort             - ok,  1375290.0 usec
      sort.h sqrt_sort              - ok,  1088504.0 usec
      stdlib qsort                  - ok,  1415336.0 usec
      -------
      Running tests with sorted blocks of length 10000:
      extra.h yysort1_int64         - ok,   361783.0 usec
      extra.h yysort2_int64         - ok,   429301.0 usec
      extra.h sort_rela589n_int64   - ok,   309345.0 usec
      sort.h tim_sort               - ok,   153956.0 usec
      sort.h quick_sort             - ok,   658700.0 usec
      extra.h std_sort_int64        - ok,   492720.0 usec
      extra.h std_stable_int64      - ok,   280025.0 usec
      sort.h heap_sort              - ok,  1027617.0 usec
      sort.h merge_sort             - ok,   413609.0 usec
      sort.h shell_sort             - ok,   725664.0 usec
      sort.h merge_sort_in_place    - ok,   370757.0 usec
      sort.h grail_sort             - ok,   642283.0 usec
      sort.h sqrt_sort              - ok,   438289.0 usec
      stdlib qsort                  - ok,   664060.0 usec
      -------
      Running tests with swapped size/2 pairs:
      extra.h yysort1_int64         - ok,   749093.0 usec
      extra.h yysort2_int64         - ok,   778670.0 usec
      extra.h sort_rela589n_int64   - ok,  1602673.0 usec
      sort.h tim_sort               - ok,  1356477.0 usec
      sort.h quick_sort             - ok,  1042425.0 usec
      extra.h std_sort_int64        - ok,   857866.0 usec
      extra.h std_stable_int64      - ok,  1045840.0 usec
      sort.h heap_sort              - ok,  1123542.0 usec
      sort.h merge_sort             - ok,  1233686.0 usec
      sort.h shell_sort             - ok,  2143031.0 usec
      sort.h merge_sort_in_place    - ok,  1253314.0 usec
      sort.h grail_sort             - ok,  1547192.0 usec
      sort.h sqrt_sort              - ok,  1259113.0 usec
      stdlib qsort                  - ok,  1721907.0 usec
      -------
      Running tests with swapped size/8 pairs:
      extra.h yysort1_int64         - ok,   421713.0 usec
      extra.h yysort2_int64         - ok,   449412.0 usec
      extra.h sort_rela589n_int64   - ok,   969430.0 usec
      sort.h tim_sort               - ok,   749844.0 usec
      sort.h quick_sort             - ok,   753447.0 usec
      extra.h std_sort_int64        - ok,   460800.0 usec
      extra.h std_stable_int64      - ok,   563436.0 usec
      sort.h heap_sort              - ok,  1054573.0 usec
      sort.h merge_sort             - ok,   706547.0 usec
      sort.h shell_sort             - ok,  1947799.0 usec
      sort.h merge_sort_in_place    - ok,   783277.0 usec
      sort.h grail_sort             - ok,   986328.0 usec
      sort.h sqrt_sort              - ok,   803845.0 usec
      stdlib qsort                  - ok,  1112677.0 usec
      -------
      Running tests with known evil data (odd/even hi/low swap):
      extra.h yysort1_int64         - ok,   153238.0 usec
      extra.h yysort2_int64         - ok,   105138.0 usec
      extra.h sort_rela589n_int64   - ok,   145879.0 usec
      sort.h tim_sort               - ok,   305719.0 usec
      sort.h quick_sort             - ok,   515508.0 usec
      extra.h std_sort_int64        - ok,   169849.0 usec
      extra.h std_stable_int64      - ok,   243750.0 usec
      sort.h heap_sort              - ok,   984348.0 usec
      sort.h merge_sort             - ok,   403293.0 usec
      sort.h shell_sort             - ok,   624925.0 usec
      sort.h merge_sort_in_place    - ok,   431592.0 usec
      sort.h grail_sort             - ok,   675009.0 usec
      sort.h sqrt_sort              - ok,   380917.0 usec
      stdlib qsort                  - ok,   707122.0 usec

  11. PsyHaSTe
    /#21170340 / +4

    Ну, честно могу сказать, что это лучше, чем "Воронки", тут хотя бы есть код реализации чтобы можно было объективно сравнивать.

  12. MomoDev
    /#21174882 / +1

    1) аллокация памяти — зло. Если массив будет размером с гигабайт, получается вы ещё два выделяете? Это в принципе может как затормозить весь процесс, так и просто тут же вывалить bad_alloc
    2) Данные бывают абсолютно разные, не только случайные или упорядоченные. Как поведёт себ алгоритм, если данные лежат в обратном порядке, если равны, чередуются с нулем и 1… Много вариантов, и на самом деле все это может непредсказуемо работать по времени. И если вы соревнуетесь с библиотечной версией sort, то должны и их протестировать.
    Кстати у Александреску в этом году на cppcon как раз была про это лекция, как он сортировку улучшал (https://youtu.be/FJJTYQYB1JQ)