Стабільність в алгоритмах сортування - лікування рівності

Алгоритми лежать в основі інформатики. Алгоритми, що використовуються для сортування, є одними з найбільш фундаментальних, корисних, а отже, і всюдисущими.

Алгоритм - кінцевий набір однозначних кроків для вирішення конкретної задачі.

Ми постійно і часто несвідомо сортуємо і покладаємось на порядок згрупованих об’єктів. Наприклад, ми класифікуємо завдання у списку за пріоритетом. Ми складаємо книги на полиці за їх висотою. Ми сортуємо рядки в електронній таблиці чи базі даних або покладаємось на алфавітний порядок слів у словнику. Іноді ми навіть сприймаємо певний вид краси в упорядкованих аранжуваннях.

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

Стійкість алгоритмів сортування - одна з відмінних властивостей серед них. Він стосується того, як алгоритм обробляє порівнянні елементи з однаковими клавішами сортування.

Клавіша сортування - ключ, який використовується для визначення впорядкування предметів у колекції, наприклад вік, зріст, положення в алфавіті тощо.

Стабільний алгоритм сортування підтримує відносний порядок елементів із однаковими клавішами сортування. Нестабільний алгоритм сортування цього не робить. Іншими словами, коли колекція сортується за допомогою стабільного алгоритму сортування, елементи з однаковими ключами сортування зберігають свій порядок після сортування колекції.

Приклад, код та демонстрація

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

При нестабільному сортуванні немає жодних гарантій збереження алфавітного впорядкування, як показано на зображенні вище.

Не завжди потрібен стабільний сорт

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

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

// JavaScript
// $5 bucks if you can correctly tell which 4 in the sorted// array was the first 4 when the array was unsorted.
var numbers = [5, 4, 3, 4, 9];numbers.sort(); // [3, 4, 4, 5, 9]
// A one second trip around the world, courtesy of the Flash, to// whomever correctly tells me which 'harry' in the sorted array was// the second 'harry' in the unsorted array.
var names = ['harry', 'barry', 'harry', 'cisco'];names.sort(); // ['barry', 'cisco', 'harry', 'harry']

Сорти є скрізь - знайте свої сорти

Досить легко з’ясувати, чи сортування за замовчуванням у вашій мові програмування чи бібліотеці стабільне. Документація повинна містити цю інформацію. Наприклад, сортування за замовчуванням стабільне у Python, нестабільне у Ruby та невизначене? в JavaScript (це залежить від реалізації браузера).

Ось декілька поширених алгоритмів сортування та їх стабільність:

  • Сортування вставки - стабільне
  • Сортування виділення - нестабільне
  • Сортування бульбашок - стабільне
  • Сортування злиття - стабільне
  • Сортування оболонки - нестабільне
  • Тимсорт - стабільний

Дивіться Вікіпедію для більш вичерпного списку.

Це демонстраційний час? ‍?

Ця демонстрація демонструє ефект використання стабільного (сортування вставки) та нестабільного алгоритму сортування (сортування за вибором) для сортування невеликої таблиці даних. Я трохи розважився і практично змінив інженерний React, будуючи це. Подивіться на джерело.

Що далі?

Якщо ви прагнете отримати більше знань про стабільність інших алгоритмів сортування, Вікіпедія має хорошу таблицю порівняння та додаткову інформацію про добре відомі алгоритми сортування.

До наступного разу мир.

Дізналися щось нове чи із задоволенням прочитали цю статтю? Поплескайте?, Поділіться цим, щоб інші могли теж читати, і слідкуйте за цим. Не соромтеся також залишати коментар.