Алгоритми за сортиране, обяснени с танци

Винаги съм се радвал на нетрадиционни методи за обясняване на нещата… но алгоритъм за сортиране с традиционен танц?! Защо не!!! Поредното доказателство, че математиците и информатиците не са задръстеняци. Поздравления за хората от Трансилванския унгарски университет Сапиентия за чудесната идея! Enjoy!

Метод на мехурчето

Обяснение с текст и дефиниции: Методът на мехурчето е метод на сортиране, при който цикълът се повтаря n² пъти, където n е броя на елементите на масива. При този метод в рамките на един цикъл се сравняват последователно всички двойки съседни елементи ai-1 и аi, и ако ai-1>ai местата им биват разменени.
Обяснение с танц:

Метод на пряката селекция

Обяснение с текст и дефиниции: Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.Намира се най-малкият елемент в списъка, разменя се с елемента на първа позиция и тези две стъпки се повтарят за остатъка от списъка, докато той свърши.

Обяснение с танц:

Метод на прякото вмъкване

Обяснение с текст и дефиниции:При сортирането по метода на прякото вмъкване масивът се обхожда от ляво на дясно, като се започне от втория елемент. Всеки елемент се сравнява с елементите, разположени вляво от него  (т.е. елементите с по-малки индекси) и се търси подходящото му място. Елементът се записва на това място в масива, а останалите се изместват с един индекс надясно. Този метод се използва широко от картоиграчите. Преглеждат се картите една по една. Всяка карта, която не си е на мястото се вади и се вмъква на подходящото място. Останалите карти се изместват.

Обяснение с танц:

Алгоритъм на Шел

Обяснение с текст и дефиниции: Подобрение на сортирането чрез пряко вмъкване е предложено от Д. Л. Шел през 1959 г. В този алгоритъм няколко пъти се изпълнява прякото вмъкване като се преминава през елементите с различна и намаляваща стъпка. В пример с 10 елемента всяка група съдържа точно по два елемента. След това елементите се прегрупират така, че във всяка група те да са през три позиции и се сортират отново – сортиране със стъпка 3. Най-после при третото преминаване елементите се сортират чрез обикновено сортиране или сортиране със стъпка 1.
Обяснение с танц:

Метод на бързото сортиране (Quicksort)

Обяснение с текст и дефиниции: Бързо сортиране (от английското quick sort) е добре известен сортиращ алгоритъм, разработен от Ч. А. Р. Хоор през 1960 година. Избира се „главен“ елемент от списъка с елементи, които ще бъдат сортирани. Списъкът се пренарежда така, че всички елементи, които са по-малки от „главния“ се поставят вляво от него, а всички, които са по-големи – вдясно от него. Рекурсивно се повтарят предишните стъпки върху списъка с по-малките и списъка с по-големите елементи. Получените списъци се сливат с конкатенация и се получава сортираният списък.
Обяснение с танц: Няма. И тук едно хубаво раздвижено българско хоро би свършило чудесна работа, стига да има ентусиасти да го направят (аз с танците съм много, ама много скаран). Иначе Quicksort е един от най-ефективните алгоритми, при това колкото по-разбъркан е масивът, толкова по-добре работи и си струва да бъде илюстриран с танц. Засега обаче мога да ви предложа само едно сравнение с метода на мехурчето:

И вече да не чувам оправдания от „днешната младеж“, че алгоритмите за сортиране били сложни…

Математика и стриптийз

Както знаете, преди 5 години завърших Математическа гимназия „Баба Тонка“ в Русе. Класната ми, изключително къдърна учителка по математика се казва Мирослава Костадинова и на срещата на класа ми разказа за един нов подход за обучение.
Ситуацията е следната: понеже хлапетата й (петокласници) са гениални и всичко им се струва естествено, не си разписват задачите.
Например, ако задачата им е следната:
Колко е 2.3+(4-2).(7+5) ?
те направо си пишат 30, вместо да си я разпишат подробно:
2.3+(4-2).(7+5) = 6 + 2.12 = 6+24 = 30.
Това, естествено, не е добре, особено за състезания и изпити, където те режат…
Съответно класната казала:
Вижте, сега… Като ходите в стриптийз бар, нима стриптийзьорката излиза, съблича се гола за 2 секунди и се прибира? Много по-готино е, ако излезе, свали си връхната дреха, после потанцува, свали си потничето, после сутиена и т. н. Е, със задачите е същото!
После как да не си разписваш подробно задачките 🙂