[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:06.91,0:00:09.18,Default,,0000,0000,0000,,Работите в колежанска библиотека.
Dialogue: 0,0:00:09.18,0:00:11.40,Default,,0000,0000,0000,,В средата на тих, спокоен следобед сте,
Dialogue: 0,0:00:11.40,0:00:18.01,Default,,0000,0000,0000,,когато пристига пратка от 1 280 книги.
Dialogue: 0,0:00:18.01,0:00:21.69,Default,,0000,0000,0000,,Книгите са сортирани в редица,
Dialogue: 0,0:00:21.69,0:00:23.29,Default,,0000,0000,0000,,но не са подредени,
Dialogue: 0,0:00:23.29,0:00:27.03,Default,,0000,0000,0000,,а автоматичната система\Nза подредба не работи.
Dialogue: 0,0:00:27.03,0:00:29.71,Default,,0000,0000,0000,,За да станат нещата още по-лоши,\Nзанятията започват утре,
Dialogue: 0,0:00:29.71,0:00:32.00,Default,,0000,0000,0000,,което означава, че\Nпървото нещо сутринта ще е
Dialogue: 0,0:00:32.00,0:00:36.56,Default,,0000,0000,0000,,студентите да дойдат на тълпи,\Nза да търсят тези книги.
Dialogue: 0,0:00:36.56,0:00:39.49,Default,,0000,0000,0000,,Как можеш да ги подредиш навреме?
Dialogue: 0,0:00:39.49,0:00:44.78,Default,,0000,0000,0000,,Един вариант е да започнете от единия край\Nна линията с първата двойка книги.
Dialogue: 0,0:00:44.78,0:00:48.63,Default,,0000,0000,0000,,Ако първите две книги са по азбучен ред,\Nги оставете както са.
Dialogue: 0,0:00:48.63,0:00:50.92,Default,,0000,0000,0000,,Ако ли не, ги разместете.
Dialogue: 0,0:00:50.92,0:00:53.22,Default,,0000,0000,0000,,След това, прегледайте\Nвтората и третата двойка,
Dialogue: 0,0:00:53.22,0:00:54.88,Default,,0000,0000,0000,,повторете процеса
Dialogue: 0,0:00:54.88,0:00:57.94,Default,,0000,0000,0000,,и продължавайте, докато стигнете\Nдо края на редицата.
Dialogue: 0,0:00:57.94,0:01:01.18,Default,,0000,0000,0000,,В някакъв момент ще се натъкнете\Nна книга, която трябва да е последна
Dialogue: 0,0:01:01.18,0:01:04.71,Default,,0000,0000,0000,,и ще продължавате да я разменяте с всяка\Nследваща книга,
Dialogue: 0,0:01:04.71,0:01:09.28,Default,,0000,0000,0000,,предвижвайки я към края на линията, докато\Nдостигнете мястото ѝ.
Dialogue: 0,0:01:09.28,0:01:12.22,Default,,0000,0000,0000,,След това, започнете отначало\Nи повторете процеса
Dialogue: 0,0:01:12.22,0:01:15.51,Default,,0000,0000,0000,,като подребите втората и последната\Nкнига на местата им,
Dialogue: 0,0:01:15.51,0:01:18.82,Default,,0000,0000,0000,,и продължавайте, докато подредите\Nвсички книги.
Dialogue: 0,0:01:18.82,0:01:21.86,Default,,0000,0000,0000,,Този метод се нарича\N"Сортиране на балончета".
Dialogue: 0,0:01:21.86,0:01:24.16,Default,,0000,0000,0000,,Лесен е, но бавен.
Dialogue: 0,0:01:24.16,0:01:29.33,Default,,0000,0000,0000,,Първоначално ще направите 1 279 сравнения,
Dialogue: 0,0:01:29.33,0:01:33.62,Default,,0000,0000,0000,,след това 1 278 и така нататък,
Dialogue: 0,0:01:33.62,0:01:38.54,Default,,0000,0000,0000,,стигайки до 818 560 сравнения.
Dialogue: 0,0:01:38.54,0:01:44.27,Default,,0000,0000,0000,,Ако всяко от тях отнема само 1 секунда,\Nпроцесът ще отнеме над 9 дни.
Dialogue: 0,0:01:44.27,0:01:48.57,Default,,0000,0000,0000,,Втора стратегия би била да се започне\Nчрез сортиране само на първите две книги.
Dialogue: 0,0:01:48.57,0:01:53.73,Default,,0000,0000,0000,,След това вземете третата книга и \Nя сравнете с книгата на второто място.
Dialogue: 0,0:01:53.73,0:01:57.17,Default,,0000,0000,0000,,Ако мястото ѝ е преди втората книга,\Nразменете ги,
Dialogue: 0,0:01:57.17,0:01:59.64,Default,,0000,0000,0000,,след това я сравнете\Nс книгата на първо място,
Dialogue: 0,0:01:59.64,0:02:01.68,Default,,0000,0000,0000,,и ги разменете отново, ако се налага.
Dialogue: 0,0:02:01.68,0:02:03.88,Default,,0000,0000,0000,,Сега подредихте първите три книги.
Dialogue: 0,0:02:03.88,0:02:07.73,Default,,0000,0000,0000,,Продължете да добавяте по една книга\Nкъм вече подредените книги,
Dialogue: 0,0:02:07.73,0:02:11.81,Default,,0000,0000,0000,,сравнявайки и размяйки новата книга\Nс тази преди нея,
Dialogue: 0,0:02:11.81,0:02:16.00,Default,,0000,0000,0000,,докато намерите правилното ѝ място\Nсред вече подредените книги.
Dialogue: 0,0:02:16.00,0:02:18.21,Default,,0000,0000,0000,,Това се нарича "Сортиране чрез вмъкване".
Dialogue: 0,0:02:18.21,0:02:22.94,Default,,0000,0000,0000,,За разлика от "Сортиране на балончета", \Nне е нужно да сравнявате всеки чифт книги.
Dialogue: 0,0:02:22.94,0:02:26.95,Default,,0000,0000,0000,,Средно, очаква се да е необходимо да \Nсравните всяка книга
Dialogue: 0,0:02:26.95,0:02:29.41,Default,,0000,0000,0000,,с половината книги преди нея.
Dialogue: 0,0:02:29.41,0:02:32.12,Default,,0000,0000,0000,,В този случай, общият брой сравнения
Dialogue: 0,0:02:32.12,0:02:35.98,Default,,0000,0000,0000,,ще бъде 409 280,
Dialogue: 0,0:02:35.98,0:02:38.14,Default,,0000,0000,0000,,отнемайки почти пет дни.
Dialogue: 0,0:02:38.14,0:02:40.70,Default,,0000,0000,0000,,Все още се налага да правите\Nпрекалено много сравнения.
Dialogue: 0,0:02:40.70,0:02:42.52,Default,,0000,0000,0000,,Ето по-добра идея.
Dialogue: 0,0:02:42.52,0:02:44.88,Default,,0000,0000,0000,,Първо, изберете книга на случаен принцип.
Dialogue: 0,0:02:44.88,0:02:49.61,Default,,0000,0000,0000,,Да кажем, че тя е "разделение"\Nи я сравнете с всяка друга книга.
Dialogue: 0,0:02:49.61,0:02:51.52,Default,,0000,0000,0000,,След това, разделете линията
Dialogue: 0,0:02:51.52,0:02:55.67,Default,,0000,0000,0000,,като сложите всички книги, които трябва\Nда са преди разделението отляво
Dialogue: 0,0:02:55.67,0:02:58.82,Default,,0000,0000,0000,,и тези, които са след него, отдясно.
Dialogue: 0,0:02:58.82,0:03:00.42,Default,,0000,0000,0000,,Спести доста време
Dialogue: 0,0:03:00.42,0:03:03.84,Default,,0000,0000,0000,,след като не е нужно изобщо да сравняваш\Nкнигите отляво
Dialogue: 0,0:03:03.84,0:03:07.24,Default,,0000,0000,0000,,с тези отдясно.
Dialogue: 0,0:03:07.24,0:03:09.66,Default,,0000,0000,0000,,Сега, преглеждайки книгите отляво,
Dialogue: 0,0:03:09.66,0:03:12.54,Default,,0000,0000,0000,,можеш да избереш друга разделителна книга
Dialogue: 0,0:03:12.54,0:03:17.24,Default,,0000,0000,0000,,и да сортираш тези книги, които са\Nпреди нея и тези след нея.
Dialogue: 0,0:03:17.24,0:03:19.57,Default,,0000,0000,0000,,Ако продължиш да създаваш\Nподразделения като това,
Dialogue: 0,0:03:19.57,0:03:22.39,Default,,0000,0000,0000,,докато направиш куп\Nмалки подраздели,
Dialogue: 0,0:03:22.39,0:03:27.76,Default,,0000,0000,0000,,би сортирал бързо всеки със\Nстратегия като Метода за вмъкване.
Dialogue: 0,0:03:27.76,0:03:32.89,Default,,0000,0000,0000,,Всеки кръг на разделяне\Nизисква около 1280 сравнения.
Dialogue: 0,0:03:32.89,0:03:35.17,Default,,0000,0000,0000,,Ако дяловете ви са почти еднакви,
Dialogue: 0,0:03:35.17,0:03:40.48,Default,,0000,0000,0000,,разделяйки книгите на 128 подраздели от по\N10, ще ви отнеме около 7 кръга,
Dialogue: 0,0:03:40.48,0:03:43.06,Default,,0000,0000,0000,,или\N8960 секунди.
Dialogue: 0,0:03:43.06,0:03:48.04,Default,,0000,0000,0000,,Сортирането на тези подредове ще добави\Nоколо 22 секунди на всеки.
Dialogue: 0,0:03:48.04,0:03:51.29,Default,,0000,0000,0000,,Като цяло, чрез този метод,\Nизвестен като "Бързо сортиране",
Dialogue: 0,0:03:51.29,0:03:54.16,Default,,0000,0000,0000,,можете да подредите книгите за\Nпо малко от 3 часа и половина.
Dialogue: 0,0:03:54.16,0:03:55.31,Default,,0000,0000,0000,,Но има уловка.
Dialogue: 0,0:03:55.31,0:03:58.79,Default,,0000,0000,0000,,Всички разделения могат да се окажат \Nнеравни и да не спестите време.
Dialogue: 0,0:03:58.79,0:04:01.24,Default,,0000,0000,0000,,За щастие това се случва рядко.
Dialogue: 0,0:04:01.24,0:04:04.54,Default,,0000,0000,0000,,Затова "Бързото сортиране" е една\Nот ефективните стратегии,
Dialogue: 0,0:04:04.54,0:04:06.18,Default,,0000,0000,0000,,използвани от\Nпрограмистите днес.
Dialogue: 0,0:04:06.18,0:04:10.51,Default,,0000,0000,0000,,Те я прилагат за подреждане на продукти\Nв онлайн магазин по цена,
Dialogue: 0,0:04:10.51,0:04:14.29,Default,,0000,0000,0000,,или създаване на списък с всички\Nбензиностанции близо до дадено място,
Dialogue: 0,0:04:14.29,0:04:16.07,Default,,0000,0000,0000,,подредени по разстояние.
Dialogue: 0,0:04:16.07,0:04:19.56,Default,,0000,0000,0000,,Във вашия случай, сте направили\Nбързо сортиране с остатък от време.
Dialogue: 0,0:04:19.56,0:04:22.64,Default,,0000,0000,0000,,Поредният ден с високи\Nзалози в библиотеката.