Algorytmy sortujące pokazane poprzez taniec

Każdy z nas wie czym jest sortowanie... wiele razy uczyliśmy się tego na podstawach programowania... pisaliśmy wiele algorytmów, sprawdzaliśmy czas sortowania tablic, porównywaliśmy które sortowanie jest najszybsze... ale czy przyszło komuś do głowy, że można wszystkie te algorytmy przedstawić poprzez taniec? ;-)

1. Sortowanie bąbelkowe

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany. [wikipedia.org]

2. Sortowanie przez wstawianie

Jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty - kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe. [wikipedia.org]

3. Sortowanie metodą Shell'a

Shell zauważył, iż algorytm sortowania przez wstawianie działa bardzo efektywnie w przypadku, gdy zbiór jest w dużym stopniu uporządkowany. Z kolei algorytm ten pracuje nieefektywnie w zbiorach nieuporządkowanych, ponieważ elementy są przesuwane w każdym obiegu o jedną pozycję przy wstawianiu elementu wybranego na listę uporządkowaną.

Pomysł Shella polegał na tym, że sortowany ciąg jest dzielony na podciągi, których elementy są odległe od siebie w sortowanym zbiorze o pewien odstęp h. Każdy z tych podzbiorów jest sortowany jakimś innym algorytmem; Shell używał sortowania przez wstawianie. Z każdym krokiem odstęp h jest zmniejszany, do czasu osiągnięcia wartości 1. Wraz ze zmianą h zmniejsza się liczba podciągów, lecz rośnie ich długość, jednak ciąg jest coraz bardziej uporządkowany. [wikipedia.org]

4. Sortowanie przez wybieranie

Jedna z prostszych metod sortowania o złożoności O(n2). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy. [wikipedia.org]

Osobiście uważam, że taka forma nauki algorytmów sortowania jest znacznie bardziej przyjemna niż czytanie i analizowanie:

Miłego oglądania ;-)