Najlepszy algorytm sortowania

Mam zestaw danych z przypadkowymi liczbami mogą być to zupełnie losowe liczby mogą być posortowane a mogą być posortowane odwrotnie. Jaki algorytm sortowania był by najlepszy? Jak można to nich ktoś podrzuci koda :]

QuickSort jest faktycznie niezłym kandydatem, ale tak naprawdę nie istnieje "najlepszy algorytm sortowania". Wszystko zależy od tego:

• ile elementów sortujemy ?
• co sortujemy (liczność dziedziny danych) ?
• czy sortowane elementy często się powtarzają ?

wyprzedzając dyskusję o notacji O(), powiem że jest to notacja graniczna, mająca rację bytu dla dużych ilości danych zresztą popatrzmy na takie zestawienie:

Wybrane algorytmy sortowania:
O(nn) insertionSort
O(nlogn) quickSort
O(k+n) sortowaniePrzezZliczanie (countingSort),
O(k+n) sortowanieKoszykowe (bucketSort),
O(d*n) radixSort

Tak, są algorytmy sortowania o czasie liniowym ! Wiążą się z pewnymi założeniami odnośnie tego co sortujemy (dziedziny, liczności lub rozkładu).

Ponadto insertionSort uchodzi za najszybszy algorytm sortowania jeśli liczba sortowanych elementów jest niewielka (w tej sytuacji narzut związany z rekurenyjną naturą metod n*logn jest większy od zysku wynikającego z dziel-i-rządź).

Reasumując: najlepszy ? to zależy.

Na stronie http://gege01.prv.pl w zakladce pomoce znajdziesz kilka sprawozdań z algorytmów i struktur danych. W spr_3 i spr_4 znajdziesz dokładne opisy wybranych metod sortowań.

Pozdrawiam.

Kapustka: witamy z powrotem :)
Co do sortowania... Najszybszy jest ten dla 3 elementów ;)

A tak z własnego doświadczenia, to mogę powiedzieć, że jak masz mniej niż 50 elementów, to bierz najprostszy jaki masz (chyba insertion z wymienionych przez Kapustke). Proste algorytmy dla małych ilości danych są chyba najszybsze, a na pewno najmniej się namęczysz pisząc je :)

To ja tylko dodam, ze jesli masz bardzo duzo danych, to jednym z najlepszych sa heap-sort oraz merge-sort (zwlaszcza oba na raz). Heap-sortem mozna posortowac za jednym zamachem srednio 2N liczb majac tylko pamieci na N*. QuickSort tego nie potrafi.

*tylko raz czytajac je wszystkie z dysku i raz zapisujac (!)