Quicksort nierekurencyjny

Witam! Poszukuję jakichkolwiek wskazówek jak napisać algorytm quicksort iteracyjnie bez używania rekurencji oraz stosu.

Oh snap, gdyby tylko istniała taka wyszukiwarka, która filtrowałaby zawartości różnych stron internetowych pod kątem wprowadzonych haseł.
Na przykład coś takiego: http://lmgtfy.com/?q=iterative+quicksort

Super znalazłeś coś iteracyjnego bez użycia stosu?

http://alienryderflex.com/quicksort/

Wiesz, szukane wyrażenie można rozbudować - iterative quicksort without stack nadal zwraca rezultaty ;-)

Co oznacza #define MAX_LEVELS 300? Czy da się to jakoś zastąpić?

@any ma słuszność, nie zawsze szukanie w googlach jest najlepszym rozwiązaniem. Po co wtedy fora? Fakt, trafił tutaj z trudnym problemem, ale to nie powód żeby odsyłać go do googli. Ja zamiast do googli odeślę do konkretnego źródła. Algorytmy i Struktury danych, K.Diks, W.Rytter, L.Banachowski.

Idea jest taka, że stos wciąż istnieje, ale organizujesz go na liczbach ciągu. Ale ten stos to pamięć O(1), więc jakby go nie ma ;). To jest dość trudne, nie potrafiłbym tego z miejsca wytłumaczyć. Najpierw przekontempluj wersję (także w tej książce) z stosem rozmiaru O(log n), a potem ten drugi.

Mówiąc o liczbach ciągu masz na myśli tablice?

Idź do księgarni i poproś o Cormena. Następnie zarezerwuj pół roku i czytaj od deski do deski ;). Lepszej porady nie dostaniesz.

any napisał(a):

Witam! Poszukuję jakichkolwiek wskazówek jak napisać algorytm quicksort iteracyjnie bez używania rekurencji oraz stosu.

Nie ma takiej wersji.
Iteracyjna wersja ma jawny stos... o rozmiarze minimum 2log(n);
czyli nieduży, np. 2*20 indeksów trzeba pamiętać dla n = milion;
no, ale w fatalnym przypadku rozmiar stosu może sięgać nawet n.

Zupełnie bez stosu, i o podobnej szybkości: nlogn, jest np. sortowanie stogowe;

to nie jest prawda, trzeba z tym stosem sprytnie postępować.

Wtedy zapewne otrzymasz coś zupełnie innego od quicksort... np. slowsort. :)

A tak w ogóle ten qsort i tak jest zwykle słaby, o czym sam się przekonałem przy sortowaniu słownika.

Mając słownik np. 100000 słówek na dysku, można tak zrobić aby to posortować:

A. czytamy cały słownik do tablicy, a potem odpalamy na tym qsort.
B. czytam po jednym słówku i od razu wsadzam go do tablicy w odpowiednim miejscu - za pomocą wyszukiwania binarnego.

Która wersja będzie szybsza?

Wesja II jest szybsza i do tego potężnie - chyba z 50 razy!

pelikan napisał(a):

Wesja II jest szybsza i do tego potężnie - chyba z 50 razy!

"Różne wersje sortowań mają różne wyniki przy innych danych"

No kto by kurde się tego spodziewał :P.

Smutny Ogórek napisał(a):

pelikan napisał(a):

Wesja II jest szybsza i do tego potężnie - chyba z 50 razy!

"Różne wersje sortowań mają różne wyniki przy innych danych"

No kto by kurde się tego spodziewał :P.

W tym przypadku nie zależy od danych, bo słownik jest ten sam!

Zresztą nietrudno wykazać że qsort jest w tym przypadku gorsza od metody... powiedzmy 'binarnego wstawiania' - BInsert.

Przy sortowaniu słów (stringów, np. do 20 znaków) decyduje liczba porównań, a nie kopiowań.

Wiemy że metoda qsort ma nlog(n) porównań, natomiast BI ma tyle:

log1 + log(2) + log(3) + ... log(n)
ile to jest - więcej czy mniej od: n x log(n)?

Pewnie że mniej:
n x logn = logn + logn + ... logn > log1 + log2 + ... logn;

albo tak:
n log n = log(n^n), natomiast BI: log1 + log(2) + log(3) + ... log(n) = log(n!);
log(n^n) > log(n!);

U Wirtha Algorytmy+struktury danych=programy jest przykładowy kod ale używa stosu

W przypadku sortowania przez scalanie można było zapisać algorytm iteracyjnie pomijając etap dzielenia
tutaj mamy dwa wywołania rekurencyjne i tylko jedno stosunkowo łatwo jest zastąpić pętlą

Poczytaj Cormena