- EldarProxy's Blog
- Log in to post comments
Вчера супруга, которая решила посмотреть вокруг место работы получше и начала каждый вечер делать программистские задачки на C#, C++ и Python, полвечера убила на быструю сортировку (quicksort). Я тем временем опять удивился насколько много граничных условий вылезает в исходном алгоритме Хоара. Да-да, знаю, уже придумали улучшенную и починенную версию, но захотелось исправить сохранив дух решения, с двумя индексами сходящимися к центру. И вот что получилось. Вроде работает. Кто-нибудь видит баг?
static public void Quicksort(int[] ar)
{
if (ar.Length > 1) Quicksort(ar, 0, ar.Length - 1);
}static private void Quicksort(int[] ar, int left, int right)
{
if (left == right) return;
int i = left + 1;
int j = right;
int pivot = ar[left];
// Loop invariant i <= j
while (i < j)
{
if (ar[i] <= pivot) i++;
else if (ar[j] > pivot) j--;
else
{ // Swap ith and jth elements
int m = ar[i]; ar[i] = ar[j]; ar[j] = m;
}
}
// Now i == j
if (ar[j] <= pivot /* it also means that i == right, because j was never moved */)
{
// Left most element is array's maximum
int m = ar[left]; ar[left] = ar[right]; ar[right] = m;
Quicksort(ar, left, right-1);
}
else
{
Quicksort(ar, left, i - 1);
Quicksort(ar, i, right);
}
}
Пока возился обратил внимание на забавный момент: как бы ни распределялись данные, количество нетривиальных вызовов Quicksort (когда i<j) всегда равно длине массива минус один. Сначала удивился, а потом дошло почему. Можете ответить? Ответ вот здесь (да, да, я решил перестать публиковать белым по белому. Слишком много браузеров на которых это не работает).