Опис предметної області - ESEI-ZNU/SortingAlgorithms GitHub Wiki
Сортування
Сортування - це процес упорядкування елементів у певному наборі даних відповідно до певного критерію. У мові C++ існує кілька методів сортування, кожен з яких має свої переваги та недоліки в залежності від особливостей задачі та кількості даних, які потрібно відсортувати.
Деякі з найбільш поширених методів сортування:
Сортування бульбашкою – цей метод сортування перебирає сусідні елементи та змінює їх місцями, якщо вони стоять у неправильному порядку, проходячи за списком кілька разів, доки всі елементи не будуть відсортовані.
Сортування вибором - цей метод сортування вибирає найменший елемент із набору та поміщає його на початок списку, потім вибирає наступний найменший елемент і поміщає його на друге місце тощо, доки всі елементи не будуть відсортовані.
Сортування вставками – цей метод сортування по черзі перебирає елементи списку та вставляє їх у правильне місце у вже відсортованій частині списку.
Швидке сортування - цей метод сортування розбиває список на дві частини, де одна містить елементи менше за певне значення, а інша містить елементи більше. Потім цей процес повторюється для кожної з цих частин, поки весь список не буде відсортований.
Сортування потрібне для упорядкування даних, що дозволяє ефективніше та швидко працювати з ними. Відсортовані дані легше шукати, витягувати та використовувати, ніж невідсортовані. Крім того, у деяких випадках відсортовані дані можуть прискорювати виконання алгоритмів, які використовують ці дані.
Масив
Масив - сукупність елементів одного типу даних, впорядкованих за індексами, які зазвичай репрезентовані натуральними числами, що визначають положення елемента в масиві. Ітератор - це об'єкт, що дозволяє перебирати всі елементи массиву.
"Бульбашковий" та шейкерний методи сортування
Метод сортування за допомогою бульбашки - один з найпростіших алгоритмів сортування. Він отримав своє ім'я завдяки своїй здатності «спливати» (вгору) найбільші або найменші елементи масиву, подібні до бульбашки у воді.
Алгоритм сортування бульбашки складається з повторних уривків вздовж відсортованого масиву. Для кожного уривку елементи послідовно порівнюються парами і, якщо порядок сортування порушується, вони змінюють місця. Прохід вздовж масиву триває, поки в наступному уривку більше не потрібно, що обміни більше не потрібні, а це означає, що масив вже був відсортований.
Ось приклад сортування масиву з п'яти елементів за даним алгоритмом:
Вихідний масив: 64 25 12 22 11
1 прохід: 25 12 22 11 64
2 прохід: 12 22 11 25 64
3 прохід: 12 11 22 25 64
4 прохід: 11 12 22 25 64
Відсортований масив: 11 12 22 25 64
Метод сортування шейкера (або коктейлю) - це алгоритм сортування, який виглядає як "бульбашкове" сортування, але рух елементів відбувається не лише в одному напрямку, але в обох напрямках.
Сортування шейкера починається з порівняння першого та другого елементів масиву та їх обміну, якщо перший елемент більше, ніж другий. Тоді відбувається порівняння другого та третього елементів та їх обміну, якщо другий елемент більше третього. Цей процес триває до кінця масиву. Потім уривок відбувається у зворотному напрямку, де порівнюються та обмінюються пари елементів від кінця масиву до початку.
Процес повторюється до тих пір, поки всі елементи не будуть сортовані. У кожній ітерації сортування шейкера мінімальний елемент масиву рухається до початку, а максимальний елемент до кінця.
Кроки сортування:
Вихідний масив: {64, 25, 12, 22, 11}
1 прохід: {25, 12, 22, 11, 64}
2 прохід: {12, 22, 25, 11, 64}
3 прохід: {12, 22, 11, 25, 64}
4 прохід: {12, 22, 11, 25, 64}
5 прохід: {11, 22, 12, 25, 64}
Кінцевий відсортований масив: {11, 12, 22, 25, 64}
Метод сортування вставками та вибором
**Сортування включенням (сортування вставкою), або сортування вставками **- це алгоритм сортування, в якому всі елементи масиву почергово переглядаються, при цьому кожен елемент переміщується у відповідне місце серед раніше впорядкованих значень. Сортування включенням або сортування вставленням На великих масивах є значно менш ефективним для таких алгоритмів, як швидке сортування. Проте, має цілу низьку перевагу:
простота у реалізації ефективний (зазвичай) на маленьких масивах ефективний при сортуванні масивів, дані в яких уже непогано відсортовані: рівень продуктивності O(n + d), де d — кількість інверсій на практиці, ефективнішій за більшість інших квадратичних алгоритмів (O(n2)) .
Опис
На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку доти, доки набір вхідних даних не буде вичерпано. Метод вибору чергового елемента з початкового масиву довільний; можна використовувати практично будь-який алгоритм вибору. Зазвичай (і з використанням стійкого алгоритму сортування), елементи встановлюються за порядком їх появи у вхідному масиві. Приклад сортування вставками:
12 3 1 5 8
3 12 1 5 8
1 3 12 5 8
1 3 5 12 8
0 1 8 3 12
Метод сортування вибором
Сортування вибором — простий алгоритм сортування лінійного масиву , на основі вставок має ефективність n2, що робить його неефективним при сортуванні великих масивів, і в цілому менш ефективним за подібний алгоритм сортування включенням . Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю. Метод
Алгоритм працює таким чином:
Знайти в списку найменше значення Міняє його місцем із першим значенням у списку Повторює два попередніх кроки, доки список не завершується (починаючи з наступної позиції) Фактично, таким чином ми розділили список на дві частини: перша (ліва) — повністю відсортована, а друга ( права) — ні.
Ось приклад сортування масиву з п'яти елементів за даним алгоритмом:
64 25 12 22 11
11 25 12 22 64
11 12 25 22 64
11 12 22 25 64 Сортування вставок також може працювати зі списками, які підтримують операції додавання та видалення, як і зв'язаний список. У такому випадку, більш зручно видаляти зі списку найменший елемент, і вставляти його в кінець відсортованої частини масиву. Наприклад: 64 25 12 22 11
11 64 25 12 22
11 12 64 25 22
11 12 22 64 25
11 12 22 25 64
Метод швидкого сортування та сортування злиттям
Метод швидкого сортування - ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно
Робота Алгоритму:
Крок 1
Для початку оберемо опорний елемент — візьмемо останній елемент масиву, він дорівнює 4. Також вводимо два лічильники — i та j. Будемо вважати, що індексація в масиві починається з 0. Тоді i = -1, а j = 0.
Крок 2
Порівнюємо j-й елемент масиву [7] з опорним елементом [4]. Якщо j-й елемент більший за опорний, то просто інкрементуємо лічильник j. У нашому випадку на першому кроці ми так і зробимо.
Тепер j = 1, порівнюємо j-й елемент масиву [2] з опорним елементом [4]. Якщо він менший за опорний, то інкрементуємо лічильник i. Тепер i = 0, міняємо місцями i-й та j-й елементи масиву. У нашому випадку міняємо місцями нульовий і перший елементи масиву, отримуємо масив [2, 7, 1, 8, 6, 3, 5], опорний елемент [4] та інкрементуємо лічильник j.
Крок 3
Лічильник j = 3, порівнюємо [8] і [4]. У цьому випадку інкрементуємо тільки лічильник j.
Крок 4
Лічильник j = 4, порівнюємо [6] і [4]. У цьому випадку інкрементуємо тільки лічильник j.
Крок 5
Лічильник j = 5, порівнюємо [3] і [4]. У цьому випадку інкрементуємо i, i = 2 і міняємо місцями i-й та j-й елементи масиву [7] і [3], отримуємо масив [2, 1, 3, 8, 6, 7, 5], опорний елемент [4] і збільшіємо лічильник j.
Крок 6
Лічильник j = 6, порівнюємо [5] і [4]. Лічильник j можна не збільшувати, оскільки ми досягли кінця масиву.
Крок 7
Тепер залишилося знайти місцинку в масиві для нашого опорного елемента. Вона знаходиться на i+1 позиції в масиві. Отримуємо [2, 1, 3] ≤ [4] < [8, 6, 7, 5]. Але так як у підмасивах знаходиться більше двох елементів, необхідно виконати аналогічне сортування для підмасиву елементів, які менше або дорівнюють опорному [2, 1, 3], та елементів, які більші за опорний [8, 6, 7, 5].
Сортування злиттям [англ.] (merge sort) — алгоритм сортування, в основі якого лежить принцип [«Розділяй та володарюй»]
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.
Робота алгоритму Схема алгоритму для конкретного прикладу послідовності
Проілюструємо алгоритм сортування на такій послідовності: 42 5 30 36 25 10 37 49 0 0 На початку сортування відсортовані підпослідовності містять в собі по одному елементу.
Крок 1: 5 42 | 30 36 | 10 25 | 37 49 | 0 0
Крок 2: 5 30 36 42 | 10 25 37 49 | 0 0
Крок 3: 5 10 25 30 36 37 42 49 | 0 0
Крок 4: 0 0 5 10 25 30 36 37 42 49