1. Оптимальність O (n log ⁡ (n)) {\ displaystyle O (n \ log (n))} [ правити | правити код ]
2. Алгоритми стійкою сортування [ правити | правити код ]
3. Непрактичні алгоритми сортування [ правити | правити код ]
4. Інші алгоритми сортування [ правити | правити код ]

open wikipedia design.

Алгоритм сортування - це алгоритм для упорядкування елементів в списку. У разі, коли елемент списку має кілька полів, поле, що служить критерієм порядку, називається ключем сортування. На практиці в якості ключа часто виступає число, а в інших полях зберігаються будь-які дані, які не впливають на роботу алгоритму.

Перші прототипи сучасних методів сортування з'явилися вже в XIX столітті. До 1890 року для прискорення обробки даних перепису населення в США американець Герман Холлерит створив перший статистичний табулятор - електромеханічну машину, призначену для автоматичної обробки інформації, записаної на перфокартах [1] . У машини Холлерита був спеціальний «сортувальний ящик» з 26 внутрішніх відділень. При роботі з машиною від оператора потрібно вставити перфокарту і опустити рукоятку. Завдяки пробитим на перфокарте отворів замикалася певна електричний ланцюг , І на одиницю збільшувалася показання пов'язаного з нею циферблата. Одночасно з цим відкривалася одна з 26 кришок сортувального ящика, і до відповідного відділення переміщалася перфокарта, після чого кришка закривалася. Дана машина дозволила обробляти близько 50 карт в хвилину, що прискорило обробку даних в 3 рази. До перепису населення 1900 року Холлерит удосконалив машину, автоматизувавши подачу карт [1] . Робота сортувальної машини Холлерита грунтувалася на методах поразрядной сортування . У патенті на машину позначена сортування «окремо для кожного стовпчика», але не визначений порядок. В іншій аналогічній машині, запатентованої в 1894 році Джоном Гором, згадується сортування зі стовпчика десятків [2] . Метод сортування, починаючи з стовпця одиниць, вперше з'являється в літературі в кінці 1930-х років [3] . До цього часу сортувальні машини вже дозволяли обробляти до 400 карт в хвилину [4] .

Надалі історія алгоритмів виявилася пов'язана з розвитком електронно-обчислювальних машин . За деякими джерелами, саме програма сортування стала першою програмою для обчислювальних машин. Деякі конструктори ЕОМ, зокрема розробники EDVAC , Називали завдання сортування даних найбільш характерною нечислової завданням для обчислювальних машин. У 1945 році Джон фон Нейман для тестування ряду команд для EDVAC розробив програми сортування методом злиття . У тому ж році німецький інженер Конрад Цузе розробив програму для сортування методом простої вставки . До цього часу вже з'явилися швидкі спеціалізовані сортувальні машини, в зіставленні з якими і оцінювалася ефективність розроблюваних ЕОМ [4] . Першим опублікованим обговоренням сортування за допомогою обчислювальних машин стала лекція Джона мокли , Прочитана ним у 1946 році. Мокли показав, що сортування може бути корисною також і для чисельних розрахунків, описав методи сортування простий вставки і бінарних вставок , а також порозрядну сортування з частковими проходами. Пізніше організована ним спільно з інженером Джоном Еккертом компанія « Eckert-Mauchly Computer Corporation »Випустила деякі з найбільш ранніх електронних обчислювальних машин BINAC і UNIVAC [5] . Поряд із зазначеними алгоритмами внутрішнього сортування , З'являлися алгоритми зовнішньої сортування , Розвитку яких сприяв обмежений обсяг пам'яті перших обчислювальних машин [4] . Зокрема, було запропоновано методи збалансованої двоколійних поразрядной сортування і збалансованого двоколійних злиття [5] .

До 1952 року на практиці вже застосовувалися багато методи внутрішнього сортування, але теорія була розвинена порівняно слабко [6] . У жовтні 1952 року Даніель Гольденберг привів п'ять методів сортування з аналізом найкращого і найгіршого випадків для кожного з них. У 1954 році Гарольд Сьюворд розвинув ідеї Гольденберга, а також проаналізував методи зовнішньої сортування. Говард Демут в 1956 році розглянув три абстрактні моделі задачі сортування: з використанням циклічної пам'яті, лінійної пам'яті і пам'яті з довільним доступом. Для кожної з цих завдань автор запропонував оптимальні або майже оптимальні методи сортування, що допомогло зв'язати теорію з практикою [7] . Через малу кількість людей, пов'язаних з обчислювальною технікою, ці доповіді не з'являлися в «відкритої літературі». Першою великою оглядової статтею про сортування, що з'явилася в пресі в 1955 році, стала робота Дж. Хоскена, в якій він описав все наявне на той момент устаткування спеціального призначення та методи сортування для ЕОМ, грунтуючись на брошурах фірм-виробників. У 1956 році Е. Френд в своїй роботі проаналізував математичні властивості великої кількості алгоритмів внутрішньої і зовнішньої сортування , Запропонувавши деякі нові методи [8] .

Після цього було запропоновано безліч різних алгоритмів сортування: наприклад, обчислення адреси в 1956 році; злиття з вставкою, обмінна сортування за розрядами , Каскадне злиття і метод Шелла в 1959 році, багатофазна злиття і вставки в дерево в 1960 році, осцилююча сортування і швидке сортування Хоара в 1962 році, пірамідальна сортування Вільямса і обмінна сортування зі злиттям Бетчера в 1964 році. В кінці 60-х років відбулося і інтенсивний розвиток теорії сортування [9] . З'явилися пізніше алгоритми багато в чому були варіаціями вже відомих методів. Набули поширення адаптивні методи сортування, орієнтовані на більш швидке виконання у випадках, коли вхідна послідовність задовольняє заздалегідь встановленим критеріям [9] .

Нехай потрібно впорядкувати N елементів: R 1, R 2, ..., R n {\ displaystyle R_ {1}, R_ {2}, \ dots, R_ {n}} . Кожен елемент представляє з себе запис R j {\ displaystyle R_ {j}} , Що містить деяку інформацію і ключ K j {\ displaystyle K_ {j}} , Що управляє процесом сортування. На безлічі ключів визначено відношення порядку «<» Так, щоб для будь-яких трьох значень ключів a, b, c {\ displaystyle a, b, c} виконувалися наступні умови [10] :

Дані умови визначають математичне поняття лінійного або вчиненого упорядкування, а задовольняють їм безлічі піддаються сортування більшістю методів [10] .

Завданням сортування є знаходження такої перестановки записів p (1) p (2) ... p (n) {\ displaystyle p (1) p (2) \ dots p (n)} з індексами {1, 2, ..., N} {\ displaystyle \ {1,2, \ dots, N \}} , Після якої ключі розташувалися б в порядку неспадання [10] :

K p (1) ⩽ K p (2) ⩽ ⋯ ⩽ K p (n) {\ displaystyle K_ {p (1)} \ leqslant K_ {p (2)} \ leqslant \ dots \ leqslant K_ {p (n) }}

Сортування називається стійкої , Якщо не змінює взаємного розташування елементів з однаковими ключами [10] :

p (i) <p (j) {\ displaystyle p (i) <p (j)} для будь-яких K p (i) = K p (j) {\ displaystyle K_ {p (i)} = K_ {p (j)}} і i <j {\ displaystyle i <j} .

Методи сортування можна розділити на внутрішні і зовнішні . Внутрішня сортування використовується для даних, що містяться в оперативну пам'ять, за рахунок чого є більш гнучкою в плані структур даних. Зовнішня сортування застосовується, коли дані в оперативну пам'ять не поміщаються, і орієнтована на досягнення результату в умовах обмежених ресурсів [11] .

Алгоритми сортування оцінюються за швидкістю виконання та ефективності використання пам'яті:

• Час - основний параметр, що характеризує швидкодію алгоритму. називається також обчислювальною складністю . Для упорядкування важливі найгірше, середнє і краще поведінка алгоритму в термінах потужності вхідного безлічі A. Якщо на вхід алгоритму подається безліч A, то позначимо n = | A |. Для типового алгоритму хорошу поведінку - це O (N log n) і погану поведінку - це O (n 2). Ідеальну поведінку для упорядкування - O (n). Алгоритми сортування, що використовують тільки абстрактну операцію порівняння ключів завжди потребують щонайменше в порівняннях. Проте, існує алгоритм сортування Хана (Yijie Han) з обчислювальною складністю O (n log log n log log log n), який використовує той факт, що простір ключів обмежена (він надзвичайно складний, а за Про -позначення ховається вельми великий коефіцієнт, що унеможливлює його застосування в повсякденній практиці). Також існує поняття сортують мереж . Припускаючи, що можна одночасно (наприклад, при паралельному обчисленні ) Проводити кілька порівнянь, можна впорядкувати n чисел за O (log2 n) операцій. При цьому число n має бути заздалегідь відомо;
• Пам'ять - ряд алгоритмів вимагає виділення додаткової пам'яті під тимчасове зберігання даних. Як правило, ці алгоритми вимагають O (log n) пам'яті. При оцінці не враховується місце, яке займає вихідний масив і незалежні від вхідної послідовності витрати, наприклад, на зберігання коду програми (так як все це споживає O (1)). Алгоритми сортування, що не споживають додаткової пам'яті, відносять до сортувань на місці.

Оптимальність O (n log ⁡ (n)) {\ displaystyle O (n \ log (n))} [ правити | правити код ]

Завдання сортування в загальному випадку передбачає, що єдиною обов'язково наявної операцією для елементів є порівняння. Це унеможливлює реалізацію алгоритму Хана, який використовує арифметичні дії. Розглянемо схему алгоритму, коли єдиним можливим дією над елементами є їх порівняння.

Нехай по ходу роботи алгоритмом проводиться k {\ displaystyle k} порівнянь. Відповіддю на порівняння двох елементів a {\ displaystyle a} і b {\ displaystyle b} може бути один з двох варіантів (a <b {\ displaystyle a <b} або a> b {\ displaystyle a> b} ). Значить, все можливо 2 k {\ displaystyle 2 ^ {k}} варіантів комбінацій відповідей на k {\ displaystyle k} питань.

Кількість перестановок з n {\ displaystyle n} елементів одно n! {\ Displaystyle n!} . Для того, щоб можна було провести сюр'єкція з безлічі відповідей на порівняння на безліч перестановок, кількість порівнянь має бути не менше, ніж log 2 ⁡ n! {\ Displaystyle \ log _ {2} {n!}} (Це забезпечується тим, що порівняння - єдина дозволена операція [12] ).

Прологаріфміровав формулу Стірлінга , Можна виявити, що log 2 ⁡ n! = Log 2 ⁡ (2 π n (ne) n) = log 2 ⁡ 2 π n + n log 2 ⁡ n - n log 2 ⁡ e ~ n log 2 ⁡ n = O (n log ⁡ n) {\ displaystyle \ log _ {2} {n!} = \ log _ {2} {\ left ({\ sqrt {2 \ pi n}} \ left ({\ frac {n} {e}} \ right) ^ {n} \ right)} = \ log _ {2} {\ sqrt {2 \ pi n}} + n \ log _ {2} {n} -n \ log _ {2} {e} \ sim n \ log _ { 2} {n} = O (n \ log {n})}

Ще однією важливою властивістю алгоритму є його сфера застосування. Тут основних типів упорядкування два:

• Внутрішня сортування оперує масивами, цілком поміщається в оперативній пам'яті з довільним доступом до будь-якому осередку. Дані зазвичай упорядковуються на тому ж місці без додаткових витрат.
  • В сучасних архітектурах персональних комп'ютерів широко застосовується підкачка і кешування пам'яті. Алгоритм сортування повинен добре поєднуватися з застосовуваними алгоритмами кешування і підкачки.
• зовнішня сортування оперує запам'ятовують великого обсягу, але не з довільним доступом, а послідовним (впорядкування файлів), тобто в даний момент «видно» тільки один елемент, а витрати на перемотування в порівнянні з пам'яттю невиправдано великі. Це накладає деякі додаткові обмеження на алгоритм і призводить до спеціальних методів впорядкування, зазвичай використовують додатковий дисковий простір. Крім того, доступ до даних у зовнішній пам'яті виробляється набагато повільніше, ніж операції з оперативною пам'яттю.
  • Доступ до носія здійснюється послідовним чином: в кожен момент часу можна вважати або записати тільки елемент, наступний за поточним.
  • Обсяг даних не дозволяє їм розміститися в ОЗУ.

Також алгоритми класифікуються за:

• потреби в додатковій пам'яті або її відсутності
• потреби в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності такої

У цій таблиці n {\ displaystyle n} - це кількість записів, які необхідно впорядкувати, а k {\ displaystyle k} - це кількість унікальних ключів.

Алгоритми стійкою сортування [ правити | правити код ]

Алгоритми нестійкою сортування [ правити | правити код ]

• Сортування вибором ( англ. Selection sort) - пошук найменшого або найбільшого елемента і приміщення його в початок або кінець впорядкованого списку. Складність алгоритму: O (n 2) {\ displaystyle O (n ^ {2})} .
• Сортування гребінцем (Comb sort) - складність алгоритму: O (n 2) {\ displaystyle O (n ^ {2})} ; поліпшення сортування бульбашкою.
• Сортування Шелла (Shell sort) - поліпшення сортування вставками. Складність алгоритму змінюється в залежності від вибору послідовності довжин проміжків; при певному виборі (див. статтю), можливо забезпечити складність O (n 4 3) {\ displaystyle O (n ^ {\ frac {4} {3}})} або O (n log 2 ⁡ n) {\ displaystyle O (n \ log ^ {2} {n})} .
• пірамідальна сортування (Сортування купи, Heapsort) - складність алгоритму: O (n log ⁡ n) {\ displaystyle O (n \ log {n})} ; перетворюємо список в купу , Беремо найбільший елемент і додаємо його в кінець списку
• Плавне сортування (Smoothsort) - складність алгоритму O (n log ⁡ n) {\ displaystyle O (n \ log {n})}
• Швидке сортування (Quicksort), у варіанті з мінімальними витратами пам'яті - складність алгоритму: O (n log ⁡ n) {\ displaystyle O (n \ log {n})} - середній час, O (n 2) {\ displaystyle O (n ^ {2})} - найгірший випадок; широко відомий як найшвидший з відомих для упорядкування великих випадкових списків; з розбивкою вихідного набору даних на дві половини так, що будь-який елемент першої половини впорядкований щодо будь-якого елементу другої половини; потім алгоритм застосовується рекурсивно до кожної половині. При використанні O (n) {\ displaystyle O (n)} додаткової пам'яті, можна зробити сортування стійкою.
• Інтроспективна сортування (Introsort) - складність алгоритму: O (n log ⁡ n) {\ displaystyle O (n \ log {n})} , Поєднання швидкої і пірамідальної сортування. Пірамідальна сортування застосовується в разі, якщо глибина рекурсії перевищує log ⁡ n {\ displaystyle \ log {n}} .
• терпляча сортування (Patience sorting) - складність алгоритму: O (n log ⁡ n) {\ displaystyle O (n \ log {n})} - найгірший випадок, вимагає додатково O (n) {\ displaystyle O (n)} пам'яті, також знаходить найдовшу збільшується підпослідовність
• Stooge sort - рекурсивний алгоритм сортування з тимчасової складністю O (n log 1, 5 ⁡ 3) ≈ O (n 2.71) {\ displaystyle O (n ^ {\ log _ {1 {,} 5} {3}}) \ approx O ( n ^ {2.71})} .

Непрактичні алгоритми сортування [ правити | правити код ]

Алгоритми, які базуються на порівняннях [ правити | правити код ]

Інші алгоритми сортування [ правити | правити код ]

Одним з найбільш частих додатків алгоритмів сортування є сортування рядків. Зазвичай вона проводиться так: спочатку безліч рядків сортується по першому символу кожного рядка, потім кожна підмножина рядків, що мають однаковий перший символ, сортується по другому символу, і так до тих пір, поки всі рядки не будуть впорядковані. При цьому відсутній символ (при порівнянні рядки довжини N з рядком довжини N + 1) вважається менше будь-якого символу.

Застосування даного методу до рядків, які представляють собою числа у природному записи, видає контрінтуітівное результати: наприклад, «9» виявляється більше, ніж «11», так як перший символ першого рядка має більше значення, ніж перший символ другої. Для виправлення цієї проблеми алгоритм сортування може перетворювати сортовані рядки в числа і сортувати їх як числа. Такий алгоритм називається «числовий сортуванням», а описаний раніше - «строкової сортуванням».

1. ↑ 1 2 Кнут, 2007 , С. 416.
2. ↑ Кнут, 2007 , С. 417.
3. ↑ Кнут, 2007 , С. 417-418.
4. ↑ 1 2 3 Кнут, 2007 , С. 418.
5. ↑ 1 2 Кнут, 2007 , С. 419.
6. ↑ Кнут, 2007 , С. 420.
7. ↑ Кнут, 2007 , С. 420-421.
8. ↑ Кнут, 2007 , С. 421.
9. ↑ 1 2 Кнут, 2007 , С. 422.
10. ↑ 1 2 3 4 Кнут, 2007 , С. 22.
11. ↑ Кнут, 2007 , С. 23.
12. ↑ Дональд Кнут. 5.3.1. Сортування з мінімальним числом порівнянь // Мистецтво програмування. - 2-е. - Вільямс, 2002.
13. ↑ Кнут, 2007 .
14. ↑ Hetland 2010 .

• Кнут Д. Е. Мистецтво програмування. Том 3. Сортування і пошук = The Art of Computer Programming. Volume 3. Sorting and Searching / під ред. В. Т. Тертишного (гл. 5) та І. В. Красикова (гл. 6). - 2-е вид. - Москва: Вільямс, 2007. - Т. 3. - 832 с. - ISBN 5-8459-0082-1 .
• Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Ривест, Кліффорд Штайн. Алгоритми: побудова й аналіз = INTRODUCTION TO ALGORITHMS. - 2-е вид. - М.: «Вільямс» , 2006. - С. 1296. - ISBN 5-8459-0857-4 .
• Роберт Седжвік. Фундаментальні алгоритми на C. Аналіз / Структури даних / Сортування / Пошук = Algorithms in C. Fundamentals / Data Structures / Sorting / Searching. - СПб. : ДиаСофтЮП, 2003. - С. 672. - ISBN 5-93772-081-4 .
• Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. - Apress, 2010. - 336 с. - ISBN 978-1-4302-3237-7 .