Return to Video

Самый быстрый способ расставить книги в алфавитном порядке — Чанд Джон

  • 0:07 - 0:09
    Вы работаете в университетской библиотеке.
  • 0:09 - 0:11
    Внезапно посреди спокойного рабочего дня
  • 0:11 - 0:17
    привозят партию из 1 280 книг.
  • 0:18 - 0:23
    Они выстроены в длинный ряд вразнобой,
  • 0:23 - 0:26
    а система автоматической
    сортировки сломана.
  • 0:27 - 0:29
    В довершение всего,
    уроки начинаются завтра,
  • 0:30 - 0:32
    а это значит, что первым делом утром
  • 0:32 - 0:36
    за этими книгами явится толпа студентов.
  • 0:36 - 0:38
    Как же успеть их рассортировать?
  • 0:39 - 0:44
    Во-первых, можно начать
    с первых двух книг на любом конце ряда.
  • 0:45 - 0:48
    Если они стоят по порядку,
    то оставьте их на том же месте.
  • 0:48 - 0:51
    В противном случае поменяйте их местами.
  • 0:51 - 0:53
    Далее, взгляните на вторую и третью книги
  • 0:53 - 0:55
    и повторите процедуру.
  • 0:55 - 0:57
    Продолжайте,
    пока не достигнете конца ряда.
  • 0:58 - 1:01
    Рано или поздно вы натолкнётесь на книгу,
    которая должна стоять последней,
  • 1:01 - 1:05
    и продолжите менять её местами
    с последующими книгами,
  • 1:05 - 1:08
    пока она не окажется
    на своём месте в самом конце.
  • 1:09 - 1:12
    Затем начните с самого начала
    и повторите процедуру,
  • 1:12 - 1:15
    чтобы переместить
    предпоследнюю книгу на место.
  • 1:15 - 1:18
    Продолжайте,
    пока не рассортируете все книги.
  • 1:19 - 1:21
    Этот подход называется
    «сортировка простыми обменами».
  • 1:22 - 1:24
    Он не сложный, но занимает много времени.
  • 1:24 - 1:29
    На первом этапе вы осуществите
    1 279 сопоставлений,
  • 1:29 - 1:33
    затем 1 278 на следующем и так далее.
  • 1:33 - 1:38
    В итоге вы проведёте
    818 560 сопоставлений.
  • 1:39 - 1:44
    Если каждое из них займёт секунду,
    весь процесс растянется на 9 дней.
  • 1:44 - 1:48
    Прибегнув ко второй стратегии,
    начните с сортировки первых двух книг.
  • 1:49 - 1:53
    Затем сравните третью и вторую книги.
  • 1:54 - 1:57
    Если третья должна стоять перед второй,
    поменяйте их местами,
  • 1:57 - 1:59
    затем сравните её с первой книгой
  • 2:00 - 2:01
    и поменяйте местами при необходимости.
  • 2:01 - 2:04
    Теперь вы расставили по местам
    первые три книги.
  • 2:04 - 2:08
    Продолжайте добавлять по одной книге
    за раз в отсортированный ряд,
  • 2:08 - 2:12
    сравнивать новую книгу с предыдущей
    и менять их местами,
  • 2:12 - 2:15
    пока она не займёт своё место.
  • 2:16 - 2:18
    Этот метод называется
    «сортировка вставками».
  • 2:18 - 2:23
    В отличие от сортировки простыми обменами,
    он не требует сравнения каждой пары книг.
  • 2:23 - 2:27
    В среднем придётся сравнивать каждую книгу
  • 2:27 - 2:29
    с половиной из тех, что шли до неё.
  • 2:29 - 2:32
    В этом случае общее количество сравнений
  • 2:32 - 2:37
    составит 409 280 и займёт почти пять дней.
  • 2:38 - 2:40
    Вам всё ещё придётся сделать
    слишком много сравнений.
  • 2:41 - 2:42
    Но есть другой выход.
  • 2:43 - 2:44
    Вначале возьмите любую книгу.
  • 2:45 - 2:46
    Она будет разделителем,
  • 2:47 - 2:49
    с которым вы будете сравнивать
    остальные книги.
  • 2:49 - 2:52
    Затем разделите ряд,
  • 2:52 - 2:56
    разместив слева от разделителя книги,
    которые идут до него по алфавиту,
  • 2:56 - 2:59
    а справа те, что идут после.
  • 2:59 - 3:01
    Вы только что сохранили уйму времени,
  • 3:01 - 3:04
    потому что избежали необходимости
    сравнивать каждую книгу слева
  • 3:04 - 3:07
    с книгами справа.
  • 3:07 - 3:10
    Теперь взгляните на книги слева.
  • 3:10 - 3:13
    Вы снова можете выбрать любую книгу
  • 3:13 - 3:17
    в качестве разделителя между книгами,
    которые идут до и после неё.
  • 3:17 - 3:20
    Вы можете делать это снова и снова,
  • 3:20 - 3:22
    пока не получите множество
    небольших групп,
  • 3:22 - 3:27
    каждая из которых рассортирована
    с помощью метода сортировки вставками.
  • 3:28 - 3:33
    Каждый этап разделения
    требует примерно 1 280 сравнений.
  • 3:33 - 3:35
    Если ряд разделён
    более-менее равномерно —
  • 3:35 - 3:41
    на 128 групп по 10 книг, —
    то вы справитесь за 7 этапов,
  • 3:41 - 3:44
    или 8 960 секунд.
  • 3:44 - 3:48
    Для сортировки каждой группы
    потребуется около 22 секунд.
  • 3:49 - 3:52
    В общем, этот метод под названием
    «быстрая сортировка»
  • 3:52 - 3:55
    поможет рассортировать книги
    за три с половиной часа.
  • 3:55 - 3:56
    Но подвох в том,
  • 3:56 - 3:59
    что выбранные разделители могут
    стоять в конце, и вы не сэкономите время.
  • 4:00 - 4:01
    К счастью, такое происходит редко.
  • 4:01 - 4:05
    Именно поэтому быстрая сортировка
    является самым эффективным методом,
  • 4:05 - 4:07
    используемым программистами
    на сегодняшний день.
  • 4:07 - 4:11
    Они используют его для сортировки товаров
    по цене в интернет-магазинах
  • 4:11 - 4:15
    или создания списка всех автозаправок
    неподалёку от выбранного места
  • 4:15 - 4:16
    и сортировки их по удалённости.
  • 4:16 - 4:20
    В вашем случае вы быстро
    рассортировали книги и сберегли время.
  • 4:20 - 4:23
    Всего лишь ещё один
    напряжённый день в библиотеке.
Title:
Самый быстрый способ расставить книги в алфавитном порядке — Чанд Джон
Speaker:
Chand John
Description:

Смотри урок полностью на: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Вы работаете в университетской библиотеке. Вдруг посреди спокойного рабочего дня привозят 1 280 книг. Они расставлены не в алфавитном порядке, а система автоматической сортировки сломана. Как быстро рассортировать книги? Чанд Джон покажет нам, как алгоритмы помогают библиотекарям и ускоряют процесс сортировки информации.

Урок — Чанд Джон, анимация — Антон Трофимов.
more » « less
Video Language:
English
Team:
closed TED
Project:
TED-Ed
Duration:
04:39

Russian subtitles

Revisions

Our website uses cookies for analysis purposes.