АЛГОРИТМИ СОРТУВАННЯ

Сортування — це процес упорядкування елементів масиву таким чином, щоб їх можна було розмістити в порядку зростання або спадання. Наприклад, розглянемо масив A = {A1, A2, A3, A4, ?? An }, масив викликається у порядку зростання, якщо елементи A розташовані так: A1 > A2 > A3 > A4 > A5 > ? > An .

значення xd xd

Розглянемо масив;

int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 )

Масив, відсортований у порядку зростання, буде подано як;

A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }

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

Алгоритми сортування

Алгоритми сортування описані в наступній таблиці разом з описом.

SN	Алгоритми сортування	опис
1	Бульбашкове сортування	Це найпростіший метод сортування, який виконує сортування шляхом багаторазового переміщення найбільшого елемента до найвищого індексу масиву. Він складається з порівняння кожного елемента з сусіднім елементом і заміни їх відповідно.
2	Відро сортування	Сортування ковшів також відоме як сортування контейнерів. Він працює шляхом розподілу елемента в масиві, який також називають відрами. У цьому алгоритмі сортування сегменти сортуються окремо за допомогою іншого алгоритму сортування.
3	Сортування гребінцем	Гребінчасте сортування — це розширена форма бульбашкового сортування. Бульбашкове сортування порівнює всі суміжні значення, тоді як гребінчасте сортування видаляє всі значення черепашки або малі значення в кінці списку.
4	Підрахунок сортування	Це метод сортування, заснований на ключах, тобто об’єкти збираються відповідно до ключів, які є малими цілими числами. Підрахунок сортування обчислює кількість входжень об'єктів і зберігає його ключові значення. Новий масив формується шляхом додавання попередніх ключових елементів і присвоєння об’єктам.
5	Сортування купи	У сортуванні купи мінімальна купа або максимальна купа зберігаються з елементів масиву залежно від вибору, а елементи сортуються шляхом видалення кореневого елемента купи.
6	Сортування вставкою	Як випливає з назви, сортування вставкою вставляє кожен елемент масиву на належне місце. Це дуже простий метод сортування, який використовується для розташування колоди карт під час гри в бридж.
7	Сортування злиттям	Сортування злиттям відповідає підходу «розділяй і володарюй», згідно з яким список спочатку ділиться на набори рівних елементів, а потім кожна половина списку сортується за допомогою сортування злиттям. Відсортований список знову об’єднується, щоб сформувати елементарний відсортований масив.
8	Швидке сортування	Швидке сортування – це найбільш оптимізований алгоритм сортування, який виконує сортування за O(n log n) порівнянь. Подібно до сортування злиттям, швидке сортування також працює за допомогою підходу «розділяй і володарюй».
9	Сортування Radix	У сортуванні Radix сортування виконується так само, як ми сортуємо імена відповідно до їхнього алфавітного порядку. Це простий алгоритм сортування, який використовується для Inegers.
10	Сортування вибору	Сортування вибором знаходить найменший елемент у масиві та розміщує його на першому місці в списку, потім знаходить другий найменший елемент у масиві та розміщує його на другому місці. Цей процес триває, доки всі елементи не будуть переміщені в правильний порядок. Він несе час виконання O(n2), що є гіршим, ніж сортування вставкою.
одинадцять	Сортування оболонки	Сортування оболонкою — це узагальнення сортування вставкою, яке усуває недоліки сортування вставкою шляхом порівняння елементів, розділених проміжком у кілька позицій.