Кой е най-бързият начин да подредите библиотеката си по азбучен ред? - Чанд Джон

Вижте пълният урок: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Работите в колежанска библиотека. В средата на тих, спокоен следобед сте, когато пристига пратка от 1 280 книги. Книгите са сортирани в редица, но не са подредени, а автоматичната система за подредба не работи. Как можете да подредите книгите бързо? Чанд Гжон показва как, хвърляйки светлина върху това как алгоритмите помагат на библиотекарите и търсачките бързо да сортират информация.

Урок на Чанд Джон, анимация от Антон Трофимов.

Работите в колежанска библиотека.

В средата на тих, спокоен следобед сте,

когато пристига пратка от 1 280 книги.

Книгите са сортирани в редица,

но не са подредени,

а автоматичната система
за подредба не работи.

За да станат нещата още по-лоши,
занятията започват утре,

което означава, че
първото нещо сутринта ще е

студентите да дойдат на тълпи,
за да търсят тези книги.

Как можеш да ги подредиш навреме?

Един вариант е да започнете от единия край
на линията с първата двойка книги.

Ако първите две книги са по азбучен ред,
ги оставете както са.

Ако ли не, ги разместете.

След това, прегледайте
втората и третата двойка,

повторете процеса

и продължавайте, докато стигнете
до края на редицата.

В някакъв момент ще се натъкнете
на книга, която трябва да е последна

и ще продължавате да я разменяте с всяка
следваща книга,

предвижвайки я към края на линията, докато
достигнете мястото ѝ.

След това, започнете отначало
и повторете процеса

като подребите втората и последната
книга на местата им,

и продължавайте, докато подредите
всички книги.

Този метод се нарича
"Сортиране на балончета".

Лесен е, но бавен.

Първоначално ще направите 1 279 сравнения,

след това 1 278 и така нататък,

стигайки до 818 560 сравнения.

Ако всяко от тях отнема само 1 секунда,
процесът ще отнеме над 9 дни.

Втора стратегия би била да се започне
чрез сортиране само на първите две книги.

След това вземете третата книга и
я сравнете с книгата на второто място.

Ако мястото ѝ е преди втората книга,
разменете ги,

след това я сравнете
с книгата на първо място,

и ги разменете отново, ако се налага.

Сега подредихте първите три книги.

Продължете да добавяте по една книга
към вече подредените книги,

сравнявайки и размяйки новата книга
с тази преди нея,

докато намерите правилното ѝ място
сред вече подредените книги.

Това се нарича "Сортиране чрез вмъкване".

За разлика от "Сортиране на балончета",
не е нужно да сравнявате всеки чифт книги.

Средно, очаква се да е необходимо да
сравните всяка книга

с половината книги преди нея.

В този случай, общият брой сравнения

ще бъде 409 280,

отнемайки почти пет дни.

Все още се налага да правите
прекалено много сравнения.

Ето по-добра идея.

Първо, изберете книга на случаен принцип.

Да кажем, че тя е "разделение"
и я сравнете с всяка друга книга.

След това, разделете линията

като сложите всички книги, които трябва
да са преди разделението отляво

и тези, които са след него, отдясно.

Спести доста време

след като не е нужно изобщо да сравняваш
книгите отляво

с тези отдясно.

Сега, преглеждайки книгите отляво,

можеш да избереш друга разделителна книга

и да сортираш тези книги, които са
преди нея и тези след нея.

Ако продължиш да създаваш
подразделения като това,

докато направиш куп
малки подраздели,

би сортирал бързо всеки със
стратегия като Метода за вмъкване.

Всеки кръг на разделяне
изисква около 1280 сравнения.

Ако дяловете ви са почти еднакви,

разделяйки книгите на 128 подраздели от по
10, ще ви отнеме около 7 кръга,

или
8960 секунди.

Сортирането на тези подредове ще добави
около 22 секунди на всеки.

Като цяло, чрез този метод,
известен като "Бързо сортиране",

можете да подредите книгите за
по малко от 3 часа и половина.

Но има уловка.

Всички разделения могат да се окажат
неравни и да не спестите време.

За щастие това се случва рядко.

Затова "Бързото сортиране" е една
от ефективните стратегии,

използвани от
програмистите днес.

Те я прилагат за подреждане на продукти
в онлайн магазин по цена,

или създаване на списък с всички
бензиностанции близо до дадено място,

подредени по разстояние.

Във вашия случай, сте направили
бързо сортиране с остатък от време.

Поредният ден с високи
залози в библиотеката.