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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метрика на женските гърди

Почти 5 сутринта е. Ще си лягам, но дават повторение на „Вот на доверие“… И Маргото за кой ли път се фука с огромните си гърди! Лошо няма… Но страшно се учудих, че измерванията показаха обем от 3600 см! Това са си почти 4 литра, както и да го гледаш!
И тъй като съм голям фен на нови методи в обучението по математика, запишете си следната

Задача: Дадена е Марго с гръдна обиколка 103 см и подгръдна обиколка 77 см. Да се намери обемът на гърдите.

Анализ: Преди всичко е важно да се моделира правилно женското тяло. Използваме следния чертеж, конструиран от снимка:

Както можем да се досетим, червената и синята окръжности представляват елипси с приблизително съотношение на радиусите 2:1. Тоест, трябва да вземем едва 1/3 от разликата в двете обиколки.

Друг важен елемент е формата на женската гръд. Тя е нещо средно между конус и полусфера.

Решение:

Обем на полусфера се намира така:
0,5 * 0,75 * п * r^3 = 0,375 * п * r^3
Обем на конус се намира така:
0,5 * 0,33 * п * r^2 * h = 0,165 * п * r^3
Тогава средноаритметичното от двете ще бъде:
0,84 * r^3

r = 1/3 * 1/2 * (гръдна – подгръдна)

Тоест обема на двете гърди на е:

2 * 0,84 * 1/(6^3) * (гръдна – подгръдна) ^ 3

Или получаваме:

0,0078 * (гръдна-подгръдна)^3

При Маргото тази разлика е 26 см или

0,0078 * 17576 = 1371 см

Което означава, че гърдите на момичето са си с обем 1,3 литра, с което задачата е решена.

Забележка: Въпреки това, апроксимациите са много условни и най-добрият начин да се измери реалния обем е да се използва фактът, че женското тяло е трапецовидно над кръста, което в триизмерен вид на задачата води до равни обеми. Така че топвате мацката в един варел – първо едни гърди под гърдите й (замерване A1), после едни гърди надолу (замерване A2), после още едни гърди надолу (замерване A3). Обемът на гърдите се изчислява така:

(A3-A2) – (A2-A1) = A3 – 2A2 + A1

Еееех, как да не обича човек математиката…

Сватбата на Митко и Били

Ще се опитам да разкажа за нещата в хронологичен ред…

С Димитър Чолаков се познаваме от ученици в математическата гимназия, но в средата на обучението той спечели карта и отиде да живее в Канада със семейството си… За няколко години успя да постигне доста, като най-голямото му постижение е, че откри жената на живота си… И вчера решихме да направим нещата между тях официални… Всъщност, те си го решиха, а ние (гостите) само стискахме палци и пихме… И въпреки че и двамата живеят в Канада, дойдоха до Русе, за да бъдат с приятелите си… Похвално!
Всъщност, помагахме не само морално, тъй като се наложи (по стар български обичай) да откраднем булката. Отнесохме я като куцо пиле домат… Митко си беше взел пълен инструментариум от отвертка (така се пише, проверих го) до двуметрова ножица за арматурно желязо. Но само отвертката беше достатъчна – развихме две болтчета на пластината на входната врата, отворихме езика и щурмувахме – накратко, пролича си кой е живял в крайните квартали 😉
От там – в обредния дом, а после – в църквата „Св. Павел“. Страшно силно впечатление ми направи церемонията, тъй като за пръв път виждам източноправославен и католик заедно (показвам и снимка, в случай, че не вярвате). Което също заслужава похвала.
В крайна сметка, отидохме и в ресторанта, където унищожихме завидно количество храна и питиета, както подобава. Митко чете стихове, ние пяхме, други танцуваха (дори и танцов ансамбъл имаше)…
Новите традиции повеляват, младоженецът (подобно на булчинския букет) да хвърля назад жартиера на булката, който хванах аз… Тъй че скоро ще се женя, остава да открия за кого 🙂 Снимки и автобиографии знаете къде да пращате, мили дами…
Имаше и още един интересен елемент – тъй като доста хора от класа ми бяха поканени, на практика се получи и своеобразна среща на класа…
И тъй, много щастливи моменти на младото семейство, както се казва в такива случаи!
Митко, можеш да целунеш булката! 🙂