суббота, 11 апреля 2009 г.

Нерекурсивная быстрая сортировка на C++

Всё, наконец-то алгоритм работает как надо )
Ввиду того, что в инете нет сорса нормальной нерекурсивной функции бысторой сортировки на C++ (зато есть куча нерабочих или слишком хитровытраханных), выкладываю свой, вдруг кому-нибудь да пригодится.

void Quick(int arr[], int n)
{
int base, left, right, i, j;
base = left = right = i = j = 0;
Stack stack;

stack.Push(n - 1);
stack.Push(0);
do { // while (stack.GetSP() != NULL)
left = stack.Pop();
right = stack.Pop();
if (((right - left) == 1) && (arr[left] > arr[right]))
swap(arr[left], arr[right]);
else {

base = arr[(left + right) / 2];
i = left;
j = right;
// цикл продолжается, пока индексы i и j не сойдутся
do { // while (i > j)
// пока i-ый элемент не превысит опорный
while ((base > arr[i]))
++i;
// пока j-ый элемент не окажется меньше опорного
while (arr[j] > base)
--j;
if (i <= j)
swap(arr[i++], arr[j--]);
} while (i <= j);
}
if (left < j) {
stack.Push(j);
stack.Push(left);
}
if (i < right) {
stack.Push(right);
stack.Push(i);
}
} while (stack.GetSP() != NULL);
}


Со стеком, я думаю, всё понятно. В конце концов, если человек не понимает, как реализовать Push и Pop, то он ещё не дорос до Хоара и эта писанина для него тёмный лес.

5 комментариев:

need_nourishment комментирует...

Спасибо большое) Пригодилась.
Сейчас буду просматривать

AccessD комментирует...

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

Анонимный комментирует...

Спасибо большое :) Очень выручил, ибо на размерности выше 30к рекурсия не катит :)

Анонимный комментирует...

Объясните, пожалуйста, что значит вот это выражение: (stack.GetSP() != NULL);

AccessD комментирует...

Проверка - есть ли еще что-то в стеке. Т.е. получение указателя на верхушку стека и если там не NULL, а в стеке что-то, то выполнить тело цикла.