9 miesięcy temu

Sortowanie – algorytmy przedstawione jako taniec ludowy

Takiego podejścia do sortowania jeszcze nie widzieliście!

Sortowanie to jeden z podstawowych problemów informatyki, polegający na uporządkowaniu zbioru danych względem pewnych cech. Najczęściej spotykanym przypadkiem jest oczywiście sortowanie liczb w odpowiedniej kolejności.

Kto z was spotkał się z algorytmami, na pewno wie, że metod sortowania jest całkiem sporo. Różnią się od siebie między innymi złożonością (zależnością liczby wykonanych operacji w stosunku od liczebności sortowanego zbioru) i sposobem działania. Algorytmy sortowania można zapisywać w różnych językach programowania, ale z własnego doświadczenia wiemy, że nie jest to zbyt fascynujące (dla większości osób…).

O wiele ciekawszy jest pomysł węgierskiego zespołu ludowego, którego członkowie pokazują jak realizowany jest algorytm tańcząc. Zobaczcie sami.

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.

Sortowanie bąbelkowe (Bubble Sort)

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.

Sortowanie szybkie (QuickSort)

Jeden z popularnych algorytmów. Z tablicy wybiera się element rozdzielający, po czym tablica jest dzielona na dwa fragmenty: do początkowego przenoszone są wszystkie elementy nie większe od rozdzielającego, do końcowego wszystkie większe. Potem sortuje się osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa tablica nie wymaga sortowania.

Więcej przykładów na kanale youtube AlgoRythmics

Źródło: wikipedia