Стабилност при сортиране на алгоритми - третиране на равенството

Алгоритмите са в основата на компютърните науки. Алгоритмите, използвани за сортиране, са едни от най-фундаменталните, полезни и следователно повсеместни.

Алгоритъм - краен набор от еднозначни стъпки за решаване на конкретен проблем.

Ние постоянно и често несъзнателно сортираме и разчитаме на реда на групираните обекти. Например, класираме задачите в списък според приоритета. Подреждаме книги на рафтове според височината им. Ние сортираме редове в електронна таблица или база данни или разчитаме на азбучния ред на думите в речника. Понякога дори възприемаме определен вид красота в подредени аранжименти.

Като програмисти знанието как ще сортираме е важно, защото влияе върху това как може да изглежда сортираната подредба. Не всички видове подреждат обектите по един и същи начин! Поради това резултатите от операциите по сортиране се различават в зависимост от използваните алгоритми. Ако това остане неразпознато, може да изненадаме себе си или хората, които използват нашия софтуер.

Стабилността на алгоритмите за сортиране е едно от отличителните свойства сред тях. Той се занимава с това как алгоритъмът третира сравними елементи с еднакви ключове за сортиране.

Клавиш за сортиране - Ключ, използван за определяне на подреждането на елементи в колекция, например възраст, височина, позиция в азбуката и т.н.

Стабилен алгоритъм за сортиране поддържа относителния ред на елементите с еднакви ключове за сортиране. Нестабилен алгоритъм за сортиране не. С други думи, когато дадена колекция се сортира със стабилен алгоритъм за сортиране, елементи с едни и същи ключове за сортиране запазват реда си след сортирането на колекцията.

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

Горното изображение илюстрира ефекта на стабилно сортиране. Вляво данните бяха сортирани по азбучен ред по Име. След сортиране на данните по степен, можете да видите, че азбучният ред на имената е бил запазен за всеки ред със същия клас.

При нестабилно сортиране няма гаранция, че азбучното подреждане се поддържа, както е показано на изображението по-горе.

Не винаги се нуждаете от стабилен сорт

Особено важно е да знаете дали сортът, който използвате, е стабилен или не. Особено в ситуации, когато данните ви вече имат някакъв ред, който бихте искали да поддържате, когато ги сортирате по друг ключ за сортиране. Например имате редове в електронна таблица, съдържаща данни за ученици, които по подразбиране са сортирани по име. Бихте искали също да го сортирате по степени, като същевременно запазите сортирания ред на имената.

От друга страна, стабилността на сортирането няма значение, когато ключовете за сортиране на обектите в колекция са самите обекти - масив от цели числа или низове, например - защото не можем да различим дублираните ключове.

// 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 (зависи от изпълнението на браузъра).

Ето няколко често срещани алгоритми за сортиране и тяхната стабилност:

  • Сортиране при вмъкване - стабилно
  • Сортиране на избора - Нестабилно
  • Сортиране на балончета - стабилно
  • Сливане на обединяване - стабилно
  • Сортиране на черупката - Нестабилно
  • Тимсорт - стабилен

Вижте Wikipedia за по-изчерпателен списък.

Демо време е???

Тази демонстрация показва ефекта от използването на стабилен (сортиране при вмъкване) и нестабилен алгоритъм за сортиране (сортиране по избор) за сортиране на малка таблица с данни. Имах малко забавление и практически обърнах инженерството на React, докато изграждах това. Погледнете източника.

Какво следва?

Ако сте жадни за повече знания за стабилността на други алгоритми за сортиране, Уикипедия разполага с добра таблица за сравнение и допълнителна информация за добре познатите алгоритми за сортиране.

До следващия път мир.

Научихте нещо ново или с удоволствие четете тази статия? Пляскайте го?, Споделете го, за да могат и другите да четат и следвайте още. Можете също да оставите коментар.