Quicksort nierekurencyjny

0

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

1

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

0

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

0

http://alienryderflex.com/quicksort/

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

0

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

0

@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.

0

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

0

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

0
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;

0

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!

1
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.

0
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!);

0

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ą

0

Poczytaj Cormena

1 użytkowników online, w tym zalogowanych: 0, gości: 1