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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Генезис (Inception)

Определено най-добрият трилър за 2010 г.

Жанр: научно-фантастичен трилър

Официален сайт: http://inceptionmovie.warnerbros.com/

IMDB: http://www.imdb.com/title/tt1375666/

Режисьор и сценарист:

Кристофър Нолан

Участват:

Леонардо Ди Каприо, Марион Котияр, Джоузеф Гордън-Левит, Кен Уатанабе, Елън Пейдж, Майкъл Кейн, Килиън Мърфи, Том Беринджър, Лукас Хаас, Дилийп Рао, Том Харди, Пийт Постълуейт

Трейлър:

Оценка: 9 / 10

И малко коментари от нас:

Вървял един ден Конфуций из гората с учениците си много умислен и мълчалив. Те никога не го били виждали такъв, чудели се и накрая попитали какво има.

-Тази нощ сънувах, че съм пеперуда -отвърнал Конфуций.

-Какво толкова странно имало в това? – попитали те.

-И сега вървя и си мисля дали пък в момента пеперудата не спи и не сънува, че е Конфуций…

* * *

Човешките сънища винаги са били в голяма степен нещо необяснимо, интересно, загадъчно и тайно. Може би ви се е случвало (а може би не) да сънувате, че сънувате… или че ви убиват насън? След като се събудите, се чувствате по-странно от всякога.

Ако обичате филми от типа на „Матрицата“ и „Ефектът на пеперудата“, няма начин „Генезис“ да не ви размаже. Това не е филм, който можете да гледате, докато сте на маса с голяма компания или пък нещо леко преди да заспите. Това е от филмите, в които дори една изпусната реплика може да означава да не разберете нищо от филма (всъщност, доста хора казват, че не са го разбрали)…

Леонардо Ди Каприо играе Коб, крадец на информация от човешки сънища. Подготовката и осъществяването на подобен „обир“ се оказват много по-сложни от това да обереш банка в реалния живот. Само че на Коб му се налага да направи нещо още по-сложно, за да види децата си… Със сценария – до тук.

Ето и няколко причини, поради които си струва да се гледа:

  • Идеята. Идеята да се нахлуе в нечие подсъзнание, да сънуваш, че сънуваш, че сънуваш и т. н. на няколко нива, да вкараш екшън, семейна драма, трилър и картини от алпийски снегове до изгарящо горещ морски плаж е невероятна, затова няма да ви я разкриваме изцяло.
  • Отново идеята. Защото някои неща просто кефят. Например, ако докато спите в реалността ви стане студено, нищо чудно в съня ви също да се появят ледени преживявания. Подобни неща са направени доста правдоподобно. Естествено, поне десетина въпроса остават необяснени и нелогични, но нима не беше така и в „Матрицата“, и в „Ефектът на пеперудата“… Личи си, че сценаристът е гледал да изпипа възможно най-голяма част от тези моменти.
  • Атмосферата. Уникално добър баланс, на ръба между психо-трилър и филм на ужасите от една страна и научна фантастика с елементи на драма от друга страна, като балансът е направен в реалността. Пишем глупости, но няма как да ви обясним повече, без да разкрием от филма…
  • Ефектите. Уникални ефекти! Технологиите на 2010 г. наистина са използвани на максимум.
  • Актьорите. Лео отново е блестящ, но тук прави добро впечатление и играта на актрисите Марион Котияр и Елън Пейдж.

Накратко – гледайте „Генезис“, ако още не сте! От „задължителните“ е.

Фестивалът Merce’09 в Барселона

Всяка година в края на септември хората от Барселона провеждат най-големия уличен фестивал – La Merce. По чиста случайност се озовахме точно в Барселона, точно в края на септември и успяхме да се насладим на много изяви по улиците на каталунската столица (дегустацията на вино и кава, стотици концерти, представления и… четете по-надолу). Фестивалът продължава около 5 дни и се провежда от 1902 г. насам. Той е едно символично каталунско „довиждане“ към отминалото лято и се провежда в чест на Mare de Deu de la Merce, светецът-патрон на Барселона. Ето и „Топ 5“ на събитията, които видяхме с очите си:

Кастелиерите

Castelliers

Барселонските кастелиери (приблизителен превод: създатели на замъци) вече 40 години поддържат традицията да се строят „замъци от хора“. Изглежда лесно отстрани, но се иска много работа в екип, усилени тренировки и невероятна концентрация. Барселонските кастелиери са достигали рекордните 9 етажа! Задължително ги посетете, докато сте в Барселона. Тренират близо до метростанция Clot от февруари до ноември. Тренировките са:

  • Вторник, от 19:30 ч.
  • Четвъртък, от 19:30 ч.
  • Събота, от 19:00 ч.

Кастелиерите имат няколко важни представления, като най-голямото е в най-близката до 24 септември неделя, пред сградата на общината (Placa de Jaume). Повече за кастелиерите и техните изяви може да научите тук.

Парадът на гигантите

Giants

Парадът на гигантите (Gigantes) е традиционно семейно събитие, което се провежда в Барселона по време на La Merce. Огромни статуи между 3 и 5 метра „тръгват“ по улиците под звуците на типичните за Испания акустични инструменти. Често са съпровождани от цели групи танцьори и музиканти. Статуите са на крале, кралици, зверове, известни личности и др.

Светлинни ефекти

LightShow

Сградата на общината се превърна в сцена на невероятно светлинно шоу. Мощни прожектори променяха изцяло вида на общинската сграда, при това синхронизирано с приятна музика…

Фестивал на запалениге зверове

Beasts

Correfoc е традиция, разпространена в цяла Каталуния. Зверовете (наричани от местните „дяволи“) се украсяват със запалени факли и фойерверки, след което отново с музика и танци тръгват по улиците на града, разпръсквайки огън наоколо… Част от хората се включват в символична „борба“ със зверовете и огъня им, преминавайки през образувалата се „огнена улица“.

Магическата заря край фонтана Монтжуик

fountains

Фестивалът завършва пред фонтана Монтжуик („Мontjuic“ означава „планината на съкровищата“), на площад Espanya. Фонтанът е създаден от над 3000 работници и е една от „задължителните“ забележителности в Барселона, съчетаваща вода, светлина и музика по неповторим начин. Повече за фонтана, както и невероятни снимки можете да видите тук, а за да го гледате наживо, трябва да отидете:

  • През лятото (май до септември) – четвъртък, петък, събота и неделя между 21 и 23 ч.
  • През зимата (октомври до април) – петък и събота между 19 и 20:30 ч.

Освен с невероятното шоу на фонтана, закриването на La Merce 2009 завърши с невероятна заря (вие виждали ли сте фойерверки с формата на сърце, маргаритка, планета с пръстен…?), съчетана с музиката, а накрая всички запалиха бенгалски огън, предоставен от община Барселона на всеки от над 80 000-те присъстващи…

И понеже нищо от тези неща не може да се опише с думи, че и със снимки, решихме да ви отведем виртуално за 14 минути сред тълпата в Барселона чрез това видеоклипче: