Quicksort partitions

Зарубился я тут в сортировки. И даже отгреб от этого головную боль.

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

	int Partition(int *a, int l, int r) {
	r--;
	int pivot = a[r];
	int i = l - 1;
	for (int j = l; j < r; j++)
	if (a[j] <= pivot)
	swap(a[++i], a[j]);
	swap(a[++i], a[r]);
	return i;
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

Видно, что он плохо себя ведет на отсортированном массиве, постоянно вызывает swap на один и тот же индекс. Улучшим:

	int Partition(int *a, int l, int r) {
	r--;
	int pivot = a[r];
	int i = l - 1;
	for (int j = l; j < r; j++)
	if (a[j] <= pivot)
	if (++i != j)
	swap(a[i], a[j]);
	swap(a[++i], a[r]);
	return i;
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

А теперь сравним с Хоаром:

	int Partition(int *a, int l, int r) {
	int x = a[l], i = l - 1, j = r;
	while (1) {
	do j--; while (a[j] > x);
	do i++; while (a[i] < x);
	if (i < j)
	swap(a[i],a[j]);
	else
	return j + 1;
	}
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

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

	fryday@fryday-HP-ZBook-15:~/sorts$ time ./quick_sort_lamuto 5000000 1234
	OK
	real 0m39.338s
	user 0m39.365s
	sys 0m0.000s
	fryday@fryday-HP-ZBook-15:~/sorts$ time ./quick_sort_lamuto_modified 5000000 1234
	OK
	real 0m16.236s
	user 0m16.143s
	sys 0m0.016s
	fryday@fryday-HP-ZBook-15:~/sorts$ time ./quick_sort_hoare 5000000 1234
	OK
	real 0m0.780s
	user 0m0.770s
	sys 0m0.004s

view raw gistfile1.txt hosted with ❤ by GitHub

Вот так вот. То ли Ламуто - ламото, то ли я ламото  -- криво заимплементил %)