Найшвидший спосіб сортування книг
Ви працюєте в університетській бібліотеці.
Раптово, серед спокійного дня прибула партія з 1280 різних книг.
Ці книги складені вздовж довгої прямої лінії, а система автоматичного сортування не справна.
На додачу до всього заняття розпочинаються завтра, а це означає, що вранці за цими книгами з’явиться натовп студентів.
Як же вам встигнути їх посортувати?
Користуючись першим способом, ви могли б почати з першої пари книг в кінці ряду.
Якщо вони стоять в правильному порядку, то залиште їх на тому ж місці.
В іншому випадку поміняйте їх місцями.
Далі погляньте на другу і третю книги, і повторіть процес.
Продовжуйте, доки не досягнете кінця ряду.
Рано чи пізно ви натрапите на книгу, яка повинна бути останньою, і ви продовжите міняти її місцями з кожною наступною книгою, доки вона не опиниться на своєму місці у самому кінці.
Тоді знову почніть с початку, і повторіть увесь процес, щоб перемістити передостанню книгу на її місце.
Продовжуйте, поки всі книги не будуть посортовані.
Цей метод має назву "сортування бульбашкою".
Він простий, але дуже повільний.
На першому етапі ви зробите 1279 порівнянь, потім 1278, і так далі.
У підсумку ви проведете 818560 зіставлень.
Якщо кожне з них триватиме одну секунду, весь процес розтягнеться на дев’ять днів.
Вдавшись до другої стратегії, почніть з сортування перших двох книг.
Потім візьміть третю книгу і порівняйте її з другою.
Якщо третя книга повинна стояти перед другою, поміняти їх місцями.
Тоді порівняйте її з першою книгою, і поміняйте їх місцями в разі потреби.
Тепер ви розсортували перші три книги.
Продовжуйте додавати по одній книзі за раз до відсортованого ряду, порівнюючи та обмінюючи нову книгу з тими, що стоять перед нею, доки вона не буде правильно розміщена серед книг, відсортованих раніше.
Цей метод називається "сортуванням включенням".
На відміну від сортування бульбашкою, він зазвичай не вимагає порівняння кожної пари книг.
В середньому вам доведеться порівнювати кожну книгу з половиною тих, що були перед нею.
У цьому випадку загальна кількість порівнянь складе 409280, а це майже п’ять днів.
Ви виконуєте все ще дуже багато порівнянь.
Але є краща ідея.
Спочатку оберіть випадковим чином будь-яку книгу.
Назвемо її "роздільником".
Порівняйте його з рештою книг.
Потім розділить ряд, розмістивши зліва від роздільника книги, які йдуть до нього за алфавітом, а праворуч ті, що ідуть після.
Щойно ви заощадили купу часу, тому що вам тепер не потрібно порівнювати кожну книгу зліва з кожною з книг справа взагалі.
Розглядаючи лише книги зліва, ви можете знову випадковим чином обрати книгу-роздільник, і відділити ті книги, що ідуть до роздільника за алфавітом від тих, що ідуть за ним.
Ви можете продовжувати створювати такі роздільники, доки не отримуєте багато маленьких рядів, кожен з яких ви б швидко посортували за допомогою іншого методу, наприклад сортуванням включенням.
Кожен етап розділення вимагає приблизно 1280 порівнянь, якщо ваші роздільники розподілені досить рівномірно, поділ усіх книг на 128 груп по десять груп потребуватиме близько семі етапів, або 8960 секунд.
Сортування кожної такої групи додасть ще по 22 секунди.
Загалом цей метод, відомий як "швидке сортування", може розсортувати книги менш ніж за три з половиною години.
Але є одна проблема.
Ваші роздільники можуть розташовуватися нерівномірно, і ви не заощадите час.
На щастя, це трапляється рідко.
Саме тому швидке сортування - одна з найефективніших стратегій, використаних програмістами сьогодні.
Вони використовують її для сортування товарів за ціною в інтернет-магазинах.
Або створення списку всіх автозаправок неподалік від обраного місця, відсортованого за віддаленістю.
Вид скористалися методом швидкого сортування для заощадження часу.
Просто ще один напружений день у бібліотеці.
