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:
Danymi wejściowymi jest ciąg n liczb.
Wynikiem jest taka ich permutacja (czyli zmiana kolejności), że tworzą one ciąg rosnący (niemalejący).
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:
LP TYP
1. Bąbelkowe
2. Przez wyszukiwanie
3. Przez wstawianie
4. Przez zliczanie
5. Sortowanie szybkie
Spróbujmy dokonać krótkiej analizy podanych algorytmów:
LP TYP ZŁOŻONOŚĆ CZASOWA PRZYKŁADOWY CZAS WYKONANIA DLA TABLICY ZŁOŻONEJ Z N ELEMENTÓW
N
5000 10000 20000
ms ms ms
1. Bąbelkowe (BubbleSort) O(N2) 79 297 1234
2. Przez wyszukiwanie (SelectionSort) 47 140 563
3. Przez wstawianie (InsetionSort) 15 63 265
4. Przez zliczanie O(N) <1 <1 <1
5. Sortowanie szybkie (QuickSort) O(NlnN) <1 <1 <1
Opisy sortowań:
Bąbelkowe
Przez zliczanie
Szybkie
Dodatek: TABLICA KOLORÓW
#FFFFCC
#FFCC99
Silver
Gray