Quicksort nierekurencyjny

Odpowiedz Nowy wątek
2017-04-04 18:55
any
0

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

Pozostało 580 znaków

2017-04-06 19:45
pelikan
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!);

Pozostało 580 znaków

2017-08-09 11:31
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ą

edytowany 1x, ostatnio: nowy121105, 2017-08-09 11:36

Pozostało 580 znaków

2017-09-04 15:57
0

Poczytaj Cormena

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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