Sortowanie ciągu liczbowego

 

Sortowanie – jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.
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ści oznacza liczbę elementów do posortowania, liczbę różnych elementów.

Stabilne

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) ;