Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwienia stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.
Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego.
Przykładowe algorytmy sortowania
W podanej złożonościStabilne
Elementy o równej wartości będą występowały, po posortowaniu, w takiej samej kolejności jaką miały w zbiorze nieposortowanym.- sortowanie bąbelkowe (ang. bubblesort) –
- sortowanie przez wstawianie (ang. insertion sort) –
- sortowanie przez scalanie (ang. merge sort) –
, wymaga
dodatkowej pamięci
- sortowanie przez zliczanie (ang. counting sort lub count sort) –
, wymaga
dodatkowej pamięci
- sortowanie kubełkowe (ang. bucket sort) –
, wymaga
dodatkowej pamięci
- sortowanie pozycyjne (ang. radix sort) –
, gdzie
to wielkość domeny cyfr, a
szerokość kluczy w cyfrach. Wymaga
dodatkowej pamięci
- sortowanie biblioteczne (ang. library sort) –
, pesymistyczny
Niestabilne
- sortowanie przez wybieranie (ang. selection sort)
– może być stabilne po odpowiednich zmianach
- sortowanie Shella – (ang. shellsort) złożoność nieznana;
- sortowanie grzebieniowe – (ang. combsort) złożoność nieznana;
- sortowanie szybkie – (ang. quicksort) Θ
, pesymistyczny O
; z wykorzystaniem algorytmu selekcji "mediana median" ("magicznych piątek") do wyszukiwania mediany, optymistyczna złożoność to
,
- sortowanie introspektywne – (ang. introspective sort lub introsort)
;
- sortowanie przez kopcowanie – (ang. heapsort)
;
Brak komentarzy:
Prześlij komentarz