Dyskusja:Sortowanie szybkie

Ten artykuł jest pod opieką Wikiprojektu Informatyka, którego celem jest rozwijanie artykułów z dziedziny informatyki. Jeśli chcesz współuczestniczyć w projekcie, odwiedź jego stronę, gdzie można przyłączyć się do dyskusji i zobaczyć listę otwartych zadań. Ten artykuł został oceniony jako zalążkowy na skali jakości. Temu artykułowi przypisano niskie znaczenie na skali ważności.

Zalążek Niskie

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

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 ${\displaystyle O(n\log n)}$. 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)[odpowiedz]

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)[odpowiedz]

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 ${\displaystyle O(n\log n)}$. 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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

już na pierwszy rzut oka widać że z tym przykładem jest coś nie tak. wykonuje niepotrzebne operacje, zamienia ze sobą dwa elementy a potem to cofa.

          Repeat
              Repeat i := i+1 Until pivot <= t[i];
              Repeat j := j-1 Until pivot >= t[j];
              b:=t[i]; t[i]:=t[j]; t[j]:=b
          Until i >= j;
          t[j]:=t[i]; t[i]:=b;

teoretycznie quicksort w posortowanej tablicy nie powinien dokona żadnej zmiany a ten algorytm je wykonuje. może się nie znam ale wg mnie lepiej jest tak:

    procedure quicksort (var t: array of longint; l, r : longint);
         var pivot, g, i, j : longint;
    begin
         pivot := t[random(r-l) + l+1];
         pokaz(-1,-1,l,r, pivot);
         begin
              i := l; j := r;
              while pivot > t[i] do inc(i);
              while pivot < t[j] do dec(j);
              while i < j do
                  begin
                       g := t[i]; t[i] := t[j]; t[j] := g;
                       pokaz(i,j,l,r, pivot);
                       Repeat inc(i) Until pivot <= t[i];
                       Repeat dec(j) Until pivot >= t[j]
                   end;
              if l < i - 1 then quicksort(t, l, i - 1);
              if i < r then quicksort(t, i, r);
         end;
    end;

Naprawdę konieczne jest podawanie w kilku językach. Wystarczyło by napisać w jednym języku albo najlepiej w pseudokodzie Tashi _dyskusja 14:17, 12 sty 2010 (CET)[odpowiedz]

Artykuł Sortowanie szybkie został napisany lub poprawiony 2 lutego 2013 w ramach Wikimaratonu.

Zapraszam współautorów do próby znalezienia błędu w algorytmie
      http://pl.wikipedia.org/w/index.php?title=Sortowanie_szybkie&oldid=34646759#Algorytm
CiaPan (dyskusja) 09:46, 7 lut 2013 (CET)[odpowiedz]

Nie ma odważnych...? No cóż, trudno. Oto odpowiedź:
brak wymagania co do końcowej pozycji elementu dzielącego dopuszcza możliwość i = r (np. w razie wybrania elementu ostatniego jako dzielącego i pozostawienia go na końcu, jeśli jest akurat największym w tablicy). Skutkiem takiego zbiegu okoliczności będzie nieskończona rekurencja przez pierwsze wywołanie i awaryjne przerwanie algorytmu przez przepełnienie stosu.
Poprawka: http://pl.wikipedia.org/w/index.php?diff=prev&oldid=34744781
--CiaPan (dyskusja) 08:47, 15 lut 2013 (CET)[odpowiedz]

Ops; a w CLR jest właśnie tak :> Spoko, rozkminiając drzewa czerwono-czarne też tam znalazłem błąd, pewnie specjalnie je zostawiają żeby studenci się nie nudzili. --<A.J.>--<?>-- 14:44, 15 lut 2013 (CET)[odpowiedz]

Jon Bentley w Perełkach oprogramowania pisze, że w ćwiczeniach z ponad setką zawodowych programistów zaledwie co dziesiąty zdołał napisać procedurę wyszukiwania binarnego, która przechodziła podstawowe testy poprawności! Co więcej, cytuje z Knutha:

A przecież bsearch jest sporo prostszy od qsort-a....
CiaPan (dyskusja) 23:33, 2 mar 2013 (CET)[odpowiedz]

Użycie zmiennej o nazwie "l" (małe L) jest bardzo nieczytelne bo przypomina cyfrę "1" (jeden). Chwilę mi zajęło.

Myślę że znacznie czytelniej i lepiej byłoby używać całych nazw "left" i "right". Żadna to oszczędność urywać słowa.

--powyższy wpis dodał 94.254.148.49 (dyskusja) 26 mar 2018 (a podpis dodał CiaPan (dyskusja) 14:05, 27 mar 2018 (CEST))[odpowiedz]