Tekst źródłowy strony Sortowanie

{{dopracować|źródła=2014-12|więcej przypisów|data=2014-06}}
'''Sortowanie''' – jeden z podstawowych [[Sytuacja trudna|problemów]] [[informatyka|informatyki]], polegający na uporządkowaniu [[Zbiór|zbioru]] danych względem pewnych cech charakterystycznych każdego elementu tego zbioru{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=22}}. 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 [[sortowanie zewnętrzne|sortowania zewnętrznego]].

Algorytmy, do działania których nie jest potrzebna większa niż stała pamięć dodatkowa (elementy sortowane przechowywane są przez cały czas w tablicy wejściowej), nazywane są algorytmami działającymi '''w miejscu'''{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=23}}.

Algorytmy sortujące, które dla elementów o tej samej wartości zachowują w tablicy końcowej kolejność tablicy wejściowej, nazywamy algorytmami '''stabilnymi'''{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=210}}.

== Problem sortowania ==
Formalna definicja ''problemu sortowania''{{odn|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein|s=22}}
: '''Dane wejściowe''': ciąg <math>n</math> liczb <math>\langle a_0,a_1,\dots a_n\rangle.</math>
: '''Wynik''': [[permutacja]] (zmiana uporządkowania) <math>\langle a'_0,a'_1,\dots a'_n\rangle</math> ciągu wejściowego taka, że <math>a'_0 \leqslant a'_1 \leqslant \dots \leqslant a'_n.</math>

== Klasyfikacja ==
Algorytmy sortowania są zazwyczaj [[Klasyfikacja statystyczna|klasyfikowane]] według{{fakt|data=2014-06}}:
* [[złożoność obliczeniowa|złożoności]] (pesymistyczna, oczekiwana) – zależność liczby wykonanych operacji w stosunku od liczebności sortowanego zbioru <math>(n).</math> Typową, dobrą złożonością jest średnia <math>\mathrm{O}(n \log n)</math> i pesymistyczna <math>\Omega(n^2).</math> Idealną złożonością jest <math>\mathrm{O}(n).</math> Algorytmy sortujące nie przyjmujące żadnych wstępnych założeń dla danych wejściowych wykonują co najmniej <math>\mathrm{O}(n \log n)</math> operacji w modelu obliczeń, w którym wartości są „przezroczyste” i dopuszczalne jest tylko ich porównywanie (w niektórych bardziej ograniczonych modelach istnieją asymptotycznie szybsze algorytmy sortowania);
* złożoność pamięciowa
* sposób działania: '''algorytmy sortujące za pomocą porównań''' to takie algorytmy sortowania, których sposób wyznaczania porządku jest oparty wyłącznie na wynikach porównań między elementami; Dla takich algorytmów dolne ograniczenie złożoności wynosi <math>\Omega(n \log n);</math>
* stabilność: '''stabilne algorytmy sortowania''' utrzymują kolejność występowania dla elementów o tym samym kluczu (klucz – cecha charakterystyczna dla każdego elementu zbioru, względem której jest dokonywane sortowanie). Oznacza to, że dla każdych dwóch elementów <math>R</math> i <math>S</math> o tym samym kluczu, jeśli <math>R</math> wystąpiło przed <math>S</math> to po sortowaniu stabilnym <math>R</math> nadal będzie przed <math>S;</math>

Kiedy elementy o tym samym kluczu są nierozróżnialne, stabilność nie jest istotna.

Przykład: (para liczb całkowitych sortowana względem pierwszej wartości)

 (4, 1) (3, 7) (3, 1) (5, 6)

W tym przypadku są możliwe dwa różne wyniki sortowania:

 (3, 7) (3, 1) (4, 1) (5, 6) – kolejność zachowana
 (3, 1) (3, 7) (4, 1) (5, 6) – kolejność zmieniona

* Stabilne algorytmy sortowania gwarantują, że kolejność zostanie zachowana.
* Niestabilne algorytmy sortowania mogą zmienić kolejność.

Algorytmy sortujące dzielimy na '''proste''' („naiwne”) i '''zaawansowane''' („logarytmiczne”). Powstanie lepszych niż proste algorytmów sortowania spowodowane było konsekwencjami poniższego faktu:

W losowym rozmieszczeniu <math>n</math> elementów <math>a[0],a[1],\dots, a[n-1]</math> każdy element jest przesunięty względem swojej pozycji w posortowanym ciągu <math>a'[0],a'[1],\dots, a'[n-1]</math> średnio o <math>\frac{n}{3}</math> pozycji.

Jeżeli algorytm sortowania zamienia tylko elementy sąsiadujące ze sobą, musi dokonać średnio <math>\frac{n}{3}</math> zamian dla każdego z <math>n</math> elementów. A więc średnia liczba porównań wynosi <math>n\cdot \frac{n}{3}= \frac{n^2}{3}=O(n^2).</math> Jedynym sposobem zmniejszenia asymptotycznej złożoności algorytmów sortujących jest wprowadzenie możliwości zamieniania elementów nie sąsiadujących ze sobą.

== Przykładowe algorytmy sortowania ==
W podanej [[złożoność obliczeniowa|złożoności]] <math>n</math> oznacza liczbę elementów do posortowania, <math>k</math> 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'') – <math>O(n^2)</math>
* [[sortowanie przez wstawianie]] (ang. ''insertion sort'') – <math>O(n^2)</math>
* [[sortowanie przez scalanie]] (ang. ''merge sort'') – <math>O(n\log n),</math> wymaga <math>O(n)</math> dodatkowej pamięci
* [[sortowanie przez zliczanie]] (ang. ''counting sort'' lub ''count sort'') – <math>O(n+k),</math> wymaga <math>O(n+k)</math> dodatkowej pamięci
* [[sortowanie kubełkowe]] (ang. ''bucket sort'') – <math>O(n^2),</math> wymaga <math>O(k)</math> dodatkowej pamięci
* [[sortowanie pozycyjne]] (ang. ''radix sort'') – <math>O(d (n+k)),</math> gdzie <math>k</math> to wielkość domeny cyfr, a <math>d</math> szerokość kluczy w cyfrach. Wymaga <math>O(n+k)</math> dodatkowej pamięci
* [[sortowanie biblioteczne]] (ang. ''library sort'') – <math>O(n \log n),</math> pesymistyczny <math>O(n^2).</math>

=== Niestabilne ===
* [[sortowanie przez wybieranie]] (ang. ''selection sort'') <math>O(n^2)</math> – może być stabilne po odpowiednich zmianach
* [[sortowanie Shella]] – (ang. ''shellsort'') złożoność nieznana;
* [[sortowanie grzebieniowe]] – (ang. ''combsort'') optymistyczny <math>O (n \log n),</math> pesymistyczny <math>O(n^2);</math>
* [[sortowanie szybkie]] – (ang. ''quicksort'') <math>O(n \log n),</math> pesymistyczny <math>O(n^2);</math>
* [[sortowanie introspektywne]] – (ang. ''introspective sort'' lub ''introsort'') <math>O(n \log n);</math>
* [[sortowanie przez kopcowanie]] – (ang. ''heapsort'') <math>O(n \log n).</math>

== Problemy ==
* wyszukiwanie elementu o największej wartości funkcji porządkującej
* wyszukiwanie <math>n</math>-tego elementu.

== Zobacz też ==
* [[algorytm]]
* [[przeszukiwanie liniowe]]
* [[sortowanie zewnętrzne]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj książkę|autor=Thomas H. Cormen |autor2=Charles E. Leiserson |autor3=Ronald L. Rivest |autor4=Clifford Stein |tytuł=Wprowadzenie do algorytmów|wydawca=WNT |rok=2007 |wydanie= |odn = {{odn/id|Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein}}}}

== Linki zewnętrzne ==
* {{Pismo Delta | url = 2024/11/o-sortowaniu-rownoleglym/ | autor = Przemysław Kiciak | tytuł = O sortowaniu równoległym | data = listopad 2024 | data dostępu = 2024-11-01 }}
* {{cytuj stronę|url=http://cg.scs.carleton.ca/~morin/misc/sortalg/|tytuł=Wizualizacja wielu algorytmów sortowania|język=en}}
* {{Cytuj stronę | url = http://talkera.org.cp-in-1.webhostbox.net/wp/?p=95 | tytuł = Mergesort Java, Python, Ruby, Perl, C, PHP (ang.). | opublikowany = talkera.org.cp-in-1.webhostbox.net | archiwum = https://web.archive.org/web/20140608001032/http://talkera.org.cp-in-1.webhostbox.net/wp/?p=95 | zarchiwizowano = 2014-06-08}}
* {{otwarty dostęp}} Chand John, ''[https://www.youtube.com/watch?v=WaNLJf8xzC4 What's the fastest way to alphabetize your bookshelf?]'', kanał na TED-Ed na [[YouTube]], 28 listopada 2016 [dostęp 2024-08-24].

{{Algorytmy sortowania}}

{{Kontrola autorytatywna}}

[[Kategoria:Algorytmika]]