Z Wikipedii

Wydaje mi się, że algorytm quicksort jest jednak znacznie częściej stosowanym algorytmem sortowania danych niż np. algorytm mergesort, gdyż jego średni czas działania przy losowym wybieraniu elementu wynosi O(nlogn,) a stała ukryta w notacji O() jest mała.

c++man ;)

mergesort, potrzebuje duzo pamieci, dlatega go zamienilem na stogowe Kbsc

[edytuj] nieprawdziwe informacje

Kbsc, usunąłeś poniższy fragment:

Zaskakującym jest fakt, że aby to osiągnąć wystarczy zagwarantować, że podział na dwie części, zawsze zostawia chociaż jeden element po obu stronach przybliżonej mediany (o ile tablica ma co najmniej 3 elementy). Już w takim przypadku teoretyczna złożoność pesymistyczna wynosi O(nlogn). Znalezienie takiej mediany w czasie stałym jest bardzo proste: wystarczy rozpatrzyć trzy dowolne elementy w tablicy, np. pierwsze trzy.

Ciekawe na jakiej podstawie uważasz że jest nieprawdziwy. Być może nie wyraziłem się jasno. Zamiast tak bezpardonowo usuwać, może warto podjąć dyskusję? Informację tą można znaleźć np. w klasycznym podręczniku algorytmiki Cormen etal, gdzie znajduje się dowód. Nie mam w tej chwili tego w domu, ale w przyszłym tygodniu mogę podać referencję. Być może opacznie to sformułowałem i uznałeś to za z gruntu nieprawdziwe. Jeśli tak to napisz dlaczego. Może można to przeformułować. Jeśli nie będziesz się odzywał to przywrócę usunięty fragment. Wazow 18:46, 9 sie 2005 (CEST)

Jeśli dzielisz tablice n-elementowa na 1+1+(n-2) to wykonujesz co najmniej n-1 operacji (bo kazda liczbe musisz porownac z mediana)

nastepnie dzielisz tablice (n-2)-elementowa co daje co najmniej n-3 operacje

itd

mamy

(n-1)+(n-3)+(n-5)+...+2

ewentualnie

(n-1)+(n-3)+(n-5)+...+3+1

taka suma jest funkcja kwadratowa od n

Kbsc 19:34, 9 sie 2005 (CEST)

Proponuję następującą korektę:

Zaskakującym jest fakt, że aby to osiągnąć nie trzeba zagwarantować podziału zrównoważonego. Wystarczy zapewnić, że podział na dwie części gwarantuje co najmniej pewien ustalony współczynnik proporcjonalności. Na przykład wystarczy, aby procedura podziału dzieliła sortowaną podtablicę co najmniej w stosunku 1:9, lub nawet 1:99 (wielkość stałej nie ma znaczenia). We wszystkich takich przypadkach otrzymujemy algorytm o złożoności O(nlogn). Niestety zapewnienie współczynnika proporcjonalności podziału ograniczonego przez stałą nie jest proste do osiągnięcia w praktyce.

Sorry za pomyłkę. Wazow 09:49, 15 sie 2005 (CEST)

[edytuj] Przykładowe implementacje

Ktoś właśnie usunął wersję C++, bo były w niej błędy. Ja bym chętnie poszedł dalej. Nie jesteśmy zbiorem przykładowych programów dla developerów. Moim zdaniem umieszczanie implementacji w wielu jezykach, obniża wartość encyklopedyczną artykułu. Lepiej jest napisać więcej tekstu o własnościach, lub wynikach eksperymentalnych. Pascal albo C by wystarczył. Jakie Wasze zdanie? Wazow 14:20, 29 mar 2006 (CEST)

Jestem też przeciwny umieszczaniu wersji SML. Przynajmniej wymaga ona komentarza. Ta typowa implementacja w SML (czy podobna w Haskellu) daje algorytm o zupełnie innych właściwościach: ma on dramatycznie większe zużycie pamięci. Można dyskutować czy quicksort jest in situ, ale wersja funkcyjna z pewnością nie jest. Z tego powody zwykłem nie uważać tego typu implementacji w SMLu jako quicksort. Wazow 14:20, 29 mar 2006 (CEST)

[edytuj] Ze zgłoś błąd

zla definicja procedury powinno byc: PROCEDURE Quicksort (VAR A: array of INTEGER; l,r: INTEGER);
Zgłoszone: 11:17, 31 gru 2006 (CET)

Definicja nie jest zła, ale wymaga wcześniejszego określenia typu nazwanego w procedurze tab. W nowszych kompilatorach można użyć tabeli otwartej, czyli tak jak proponuje zgłaszający, ale w starszych wersjach Pascala, to nie przejdzie. Kolejnym problem to ograniczenie, w deklaracji zgłaszającego, typu elementów tablicy w nagłówku, jest to dopuszczalne dla tabel otwartych, ale nie jest dopuszczalne dla innych tabel i dlatego nie jest dobrym zwyczajem programistycznym. StoK 21:12, 1 sty 2007 (CET)