Sortowanie

Sortowanie jest jednym z najczęściej rozwiązywanych problemów informatycznych. Według różnych autorów, komputery spędzają od 25 do 80 procent czasu na porządkowaniu informacji. Porządek wśród elementów ułatwia i przyspiesza wykonywanie innych operacji (np. przeszukiwania).

Sortowanie jest też przykładem problemu, który może być rozwiązany na wiele sposobów, a ich efektywność jest istotnie różna. Za efektywność algorytmów sortujących przyjmuje się liczbę porównań wykonywanych między elementami danych. Zwykle jest ona podawana jako zależność od liczby elementów do uporządkowania.

Problem sortowania można zdefiniować następująco:

1. Danymi wejściowymi jest ciąg n liczb.
2. Wynikiem jest taka ich permutacja (czyli zmiana kolejności), że tworzą one ciąg rosnący (niemalejący).
3. Zadaniem algorytmu sortowania jest takie przestawienie elementów danego ciągu, aby były one uporządkowane rosnąco (niemalejąco).

Oto przykłady algorytmów sortowania:

Spróbujmy dokonać krótkiej analizy podanych algorytmów:

Opisy sortowań:

1. Bąbelkowe
2. Przez zliczanie
3. Szybkie