Сортування — це процес упорядкування елементів масиву таким чином, щоб їх можна було розмістити в порядку зростання або спадання. Наприклад, розглянемо масив 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), що є гіршим, ніж сортування вставкою. |
| одинадцять | Сортування оболонки | Сортування оболонкою — це узагальнення сортування вставкою, яке усуває недоліки сортування вставкою шляхом порівняння елементів, розділених проміжком у кілька позицій. |