Зміст
Сортування набору елементів у списку є частим завданням у програмуванні. Часто людина може виконати це завдання інтуїтивно. Однак для завершення комп'ютерної програми необхідно виконати точну послідовність інструкцій, і цю послідовність називають алгоритмом. Алгоритм сортування - це метод, який використовується для розміщення списку неорганізованих елементів у певному порядку. Послідовність впорядкування визначається ключем. Існує декілька алгоритмів сортування, які відрізняються ефективністю та продуктивністю. Деякі відомі і важливі з цього типу: сортування бульбашок, сортування вибору, сортування вставки та швидкий сортування.
Сортування бульбашок
Сортування бульбашок неодноразово змінює суміжні елементи, які не впорядковані, поки кожен список елементів не знаходиться в послідовності. Таким чином, елементи змінюються у списку відповідно до їх значень, найбільшим (у разі зростання порядку), що закінчується в кінці кожної ітерації.
Головною перевагою цього алгоритму є те, що його реалізація легка і знайома. Крім того, в сортуванні міхура елементи замінюються без використання тимчасового сховища, що робить мінімальні вимоги до простору. Основним недоліком є те, що він не показує хороших результатів, коли список містить багато елементів. Це пояснюється тим, що для такого роду упорядкування потрібні кроки обробки n2 для кожного числа n елементів, які будуть відсортовані. Таким чином, сорт міхура вказаний для академічного викладання, але не для реальних додатків.
Виділення сортування
Виділення сортування повторює список елементів, вибираючи один елемент за один раз і розміщуючи його у правильному положенні послідовності.
Головною перевагою сорту вибору є те, що він добре працює в невеликому списку. Крім того, оскільки він є алгоритмом упорядкування місця, він не потребує тимчасового зберігання, окрім того, що потрібно для зберігання вихідного списку. Основним недоліком є низька ефективність у великих списках. Як і сорт міхура, для кожного n елементів потрібно n2 кількість кроків. Крім того, на його продуктивність легко впливати початковий порядок елементів перед процесом відбору. Через це цей вибір типу підходить тільки для списку, де кілька елементів знаходяться у випадковому порядку.
Сортування вставки
Сортувати сортування сортує список неодноразово і кожен раз вставляє елемент невпорядкованої послідовності в правильне положення.
Головною перевагою впорядкування вставки є її простота, а також хороша робота на невеликих списках. Це алгоритм упорядкування місця, тому вимоги до простору мінімальні. Недоліком є те, що він не працює так само, як і інші алгоритми сортування. З n2 кроками, необхідними для роботи, вставити сортування не працює добре з великими списками. Однак це особливо корисно з переліком декількох пунктів.
Швидкий сортування
Швидкий сортування працює за принципом поділу і завоювання. По-перше, він розділяє список елементів на два підсписки на основі опорного елемента. Всі елементи в першому підпункті розташовані так, щоб вони були меншими, ніж поворот, тоді як всі елементи у другому підпункті розташовані більше, ніж поворот. Один і той же процес розбиття і організації повторно виконується в підсумках, що утворюються, доки не буде організовано весь список.
Деякі вважають, що швидкий сортування є найкращим алгоритмом сортування через його значну перевагу з точки зору ефективності, оскільки він добре працює з великим списком елементів. При замовленні на місці, також немає необхідності в додатковому приміщенні для зберігання. Невеликий недолік, який він представляє, полягає в тому, що його найгірша продуктивність схожа на середню продуктивність інших алгоритмів, описаних вище. Однак важливо відзначити, що цей найгірший випадок є дуже рідкісним. Взагалі, швидкий сорт створює найбільш ефективний і широко використовуваний метод організації списку будь-якого розміру.
