Cześć.
Standardowe algorytmy sortujące posiadają zróżnicowaną wydajność, w zalezności od wielkości sortowanego zbioru.
InsertionSort, Heapsort, Mergesort oraz QuickSort. Do jakiego rodzaju zbiorów nadaje się każdy z nich? Wiadomo, że InsertionSort najwydajniejszy jest dla zbiorów małych, ale co to znaczy? Dla jak wielkiego n?
Takie rzeczy sprawdza się eksperymentalnie.
zależy od implementacji. do n=1000 w zasadzie nie ma większego znaczenia jakiego algorytmu użyjesz, bo i tak wszystko wykona się w ciągu max kilku milisekund. Heapsort ma dużą zaletę, bo zawsze sortuje ze złożonością O(n log n) i dodawanie elementów do kopca można wykonać dość szybko. W quicksorcie w pesymistycznym przypadku może dojść aż do n^2/2 porównań (na szczęście powstało sortowanie intro sort które pesymistyczny przypadek wykonuje innym algorytmem). Merge sort za to jest stabliny (takie same elementy zostaną w zbiorze w tej samej kolejności). Jeśli zbiór liczb sortowanych jest mały, warto użyć sortowania przez zliczanie (O(n), z tym że złożoność pamięciowa wynosi tyle co wielkość zbioru)
W praktyce QuickSort jest najszybszy. Nie sprawdza się jedynie, gdy masz dziwne zbiory - typu posortowane lub posortowane odwrotnie (w zależności od implementacji)
@Noran teoretycznie możesz to sobie policzyć. Policz ile operacji porównania i przypisania wykonujesz w przypadku każdego z tych algorytmów (w funkcji n oczywiście) i rozwiąż kilka nierówności. Ale czy będzie to miarodajne? Trudno powiedzieć ;)
introsort to jest quicksort który w pesymistycznym przełącza się na heapsorta, więc można powiedzieć że jest szybszy
introsort potrafi być minimalnie wolniejszy od quicksorta w optymistycznych dla quicksorta przypadkach.
a w ogóle to najszybszy jest bogosort kwantowy: 1. wymieszaj losowo dane; 2. jeśli dane nie są posortowane, zniszcz wszechświat. :-)
Wszystko zależy co się sortuje, na czym i czym się wzbogaca struktury danych. Np dla sortowania wielu terabajtowych ciągów rekordów korzysta się z "polyphase merge sort" dla przykładu. Jeśli jest bardzo mało inwersji w ciągu (zawartym w RAM) to najlepiej korzystać z sortowania przez wstawianie, jeśli jest trochę więcej, ale dalej mało to dobrze sprawuje się smoothsort, itp Jeśli sortujemy listę jednokierunkową to quick sort działa tragicznie, ale merge sort bardzo wydajnie, etc