Taneczne sortowanie

1 z 4

Sortowanie przez wstawianie

Sortowanie przez wstawianie (Insert Sort) do melodii rumuńskiego tańca ludowego.To sposób podobny do tego, jak ludzie porządkują karty do gry: wybierają kolejną kartę i wstawiają ją w odpowiednie miejsce w już uporządkowanych.

Dla każdego algorytmu określa się jego złożoność obliczeniową - ile trzeba wykonać porównań, by posortować wszystkie elementy. Ponieważ każde porównanie trwa tyle samo czasu, to złożoność obliczeniowa przekłada się na czas. Stopień złożoności przedstawia się w postaci O(n²) - liczba porównań jest proporcjonalna do kwadratu (²) liczby elementów.

W powyższym filmie, wspólny taniec każdej pary, to jedno porównanie.

Sortowanie przez wstawianie ma średnią złożoność O(n²), ale działa szybko dla małej liczby, prawie uporządkowanych elementów. Dlatego jest często wykorzystywany w końcowych etapach bardziej skomplikowanych algorytmów.

Tak wygląda mniej "taneczna" wizualizacja sortowania przez wstawianie:

2 z 4

Sortowanie bąbelkowe

Sortowanie bąbelkowe do węgierskiej melodii ludowej.

W tym algorytmie porównywane są kolejne pary elementów. Gdy znajdują się w dobrej kolejności - nic się nie dzieje, gdy w złej - są zamieniane miejscami. Nazwa pochodzi stąd, że elementy poruszają się podobnie jak bąbelki w gazowanych napojach - elementy najlżejsze powoli przesuwają się do góry, a najcięższe na dół.

Algorytm jest mało efektywny (średnia złożoność to O(n²)), praktycznie nie używany. Tak wygląda wizualizacja algorytmu:

3 z 4

Sortowanie Shella

Sortowanie Shella do melodii węgierskiej.

To zmodyfikowana wersja sortowania przez wstawianie. W najgorszym przypadku złożoność sortowania Shella wynosi O(nlog²n). Algorytm jest łatwy do zaprogramowania, ale trudny do analizy teoretycznej.

4 z 4

Sortowanie przez wybieranie

Sortowanie przez wstawianie do melodii cygańskiej

Algorytm jest bardzo prosty:

Znajdź najmniejszy element
Zamień go miejscami z pierwszym elementem
Powtórz działanie dla wszystkich elementów z wyjątkiem pierwszego

Zwykle jest szybszy niż sortowanie bąbelkowe, ale gorszy niż sortowanie przez wstawianie. Wygląda tak:

Żółte kolor oznacza elementy posortowane, czerwone - chwilowo najmniejszy, niebieski - największy w danym przebiegu.

Źródło: Korzystałem z materiałów o sortowaniu ze stron en.wikipedia.org. Wizualizacje sortowania wykonane przez: Simpsons contributor, Nuno Nogueira (Nmnogueira), en:Joestape89

algorytm sortowanie taniec