Сортування даних: алгоритми, структури та застосування

Дані оточують нас усюди. Ми збираємо їх, аналізуємо та перетворюємо на вирішення незліченних завдань - від ведення своїх фінансів до автоматизації найскладніших виробничих процесів. Однак для отримання з даних максимальної користі їх необхідно впорядкувати певним способом.

Основні поняття та визначення

Сортування даних - це процес упорядкування даних за певним критерієм, наприклад, за зростанням або зменшенням значень, за алфавітом і так далі. Мета сортування – полегшити подальший пошук, аналіз та обробку даних. Сортування можуть піддаватися як числові, і текстові дані, дати, логічні значення та інші типи.

Основні поняття, пов'язані з сортуванням даних:

• Ключ сортування - поле чи комбінація полів, якими виконується сортування даних.
• Порядок сортування - напрямок сортування за зростанням (від меншого до більшого) або зменшення (від більшого до меншого) значень.
• Стабільність сортування – збереження початкового порядку записів з однаковими ключами після сортування.

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

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

Пухирцеве сортування

Один із найпростіших алгоритмів. Дані проглядаються по черзі, і якщо чергове значення виявляється меншим за попереднє, вони змінюються місцями. Таким чином, найбільші значення "спливають" в кінець масиву подібно до бульбашок у воді.

Сортування вибором

На кожній ітерації алгоритму невідсортованої частини даних знаходиться мінімальний елемент і ставиться на відповідне місце у відсортованій частині.

Сортування вставками

Відсортовані елементи розміщуються на початку масиву. На кожній ітерації чергове значення вставляється у відповідну позицію серед відсортованих елементів.

Швидке сортування

Ефективний алгоритм, заснований на методі "поділяй і володарюй". Вибирається опорний елемент, дані розбиваються на частини по відношенню до нього, потім сортування викликається рекурсивно кожної частини.

Реалізація сортування в Excel

Microsoft Excel надає зручні засоби для сортування даних як у звичайних діапазонах осередків, так і таблицях. Розглянемо основні методи.

Швидке сортування

Для швидкого сортування виділіть комірку в стовпці та виберіть сортування за зростанням або зменшенням на вкладці "Дані".

Додаткові параметри

Для тонкого налаштування параметрів сортування використовуйте діалогове вікно "Сортування". Тут можна:

• Задати кілька рівнів сортування за різними стовпцями.
• Сортувати за кольором, значками чи форматом осередків.
• Використовувати списки, що настроюються.
• Враховувати чи ігнорувати регістр літер.
• Сортувати стовпці замість рядків.

Також сортування даних у таблицях можна здійснити за допомогою фільтрів.

Особливості сортування в Excel

При сортуванні даних в Excel слід враховувати низку особливостей та рекомендацій:

• Сортуйте числа, збережені у числовому форматі, а текст – у текстовому.
• Перед сортуванням тексту видаляйте всі початкові пробіли.
• Відображайте приховані рядки та стовпці.
• Враховуйте параметри мови та регіональні стандарти.

Дотримання цих правил дозволить отримати коректні результати сортування.

Застосування сортування даних практично

Впорядковані за допомогою сортування дані значно полегшують вирішення багатьох завдань.

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

Застосування сортування та пошуку даних дозволяє оптимізувати бізнес-процеси, підвищити ефективність управлінських рішень та зрештою – отримати суттєві конкурентні переваги.

Способи підвищення ефективності сортування даних

Хоча в Excel вбудовані всі необхідні інструменти для сортування, під час роботи з великими обсягами даних потрібна оптимізація цього процесу:

• Використання фільтрів. Для попереднього відбору частини даних перед сортуванням зручно використовувати фільтри. Це дозволяє суттєво скоротити обсяг сортованої інформації.
• Прискорення обчислень. Відключення непотрібних обчислень та використання опцій прискорення розрахунків (наприклад, обчислення частинами) зменшує час сортування даних з формулами.
• Структурування даних. Розбиття даних на логічні блоки та сортування кожного окремо ефективніше одного загального сортування.

Особливості сортування великих обсягів даних

При сортуванні даних у сотні тисяч рядків або значному навантаженні на обчислення можуть виникати труднощі. Можна застосовувати:

• Сегментація даних. Розбиття даних на частини дозволяє сортувати кожну окремо, суттєво заощаджуючи ресурси комп'ютера.
• Використання Power Query. Спеціальний інструмент Power Query для роботи з великими наборами даних прискорює сортування та агрегує результати.

Для регулярного або складного багаторівневого сортування даних зручно створити макрос на VBA, який запускає її в один клік.

Макроси дозволяють гнучко налаштовувати правила сортування, змінюючи параметри при запуску.

Запуск з інших програм

Якщо потрібно автоматично сортувати дані регулярно або за певною подією, макроси VBA для Excel можуть викликатися з інших програм.

Інтеграція сортування даних з іншими системами

Для комплексної аналітичної роботи часто потрібно інтегрувати сортування даних Excel з іншими інформаційними системами.

Сортування даних, що імпортуються

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

Експорт відсортованих даних

Результати сортування в Excel зручно експортувати до інших баз даних, CRM-системи, analytics-платформи для подальшого аналізу.

Взаємодія через ODBC

Завдяки підключенню Excel до зовнішніх даних через ODBC можна сортувати без явного імпорту та експорту, що заощаджує час.

Ризики при сортуванні даних

Незважаючи на простоту, сортування інформації може призвести до негативних наслідків при неправильному підході.

Порушення взаємозв'язків

Сортування частини взаємозалежних даних призводить до втрати зв'язків між ними, що є критичним для аналізу.

Втрата актуальності

Зміна порядку даних без синхронізації з іншими системами може призвести до прийняття застарілих рішень.

Некоректна інтерпретація

Неправильний вибір ключа сортування або його параметрів може спотворити результуючу картину та спричинити помилкові висновки.

Це основа. Алгоритми сортування для початківців

Привіт! У цій статті я розповім про два алгоритми сортування: Quick Sort та Merge Sort. Поясню, як вони працюють, як виглядають приклади коду на Python і Java, а також як вибрати відповідний алгоритм під ваші завдання. Подробиці - під катом.

Використовуйте навігацію, якщо не бажаєте читати текст повністю:

Чому сортування – це не просто перестановка елементів

Алгоритми сортування – основа програмування, без них неможливо рухатися далі. Але чому ж сортування має таке значення? Справа в тому, що впорядкування — це основа для оптимізації інших алгоритмів, покращення продуктивності та ефективнішого управління даними.

Уявіть склад величезного інтернет магазину, де мільйони товарів зберігаються на стелажах. Щоб швидко знаходити позиції, співробітники зобов'язані підтримувати суворий порядок, сортувати товари за категоріями та підкатегоріями. Тепер уявіть, що сортування порушилося. Потрібний товар доведеться шукати вручну – швидкість обслуговування знизиться, а витрати магазину зростуть.

У світі розробки програмного забезпечення, де алгоритми сортування відіграють роль «бібліотекарів» для даних, така ситуація еквівалентна збою програми або значному падінню продуктивності системи. При цьому, якщо уявити сортування просто як спосіб розмістити елементи в потрібному порядку, ми пропустимо його глибоке значення. Алгоритми сортування не просто «переставляють» елементи масиву. Вони оптимізують роботу додатків, мінімізують споживання пам'яті та можуть працювати навіть на великих наборах даних

Сортування – це перестановка заданого масиву або списку елементів відповідно до оператора порівняння елементів. Він використовується для визначення їх нового порядку у відповідній структурі даних. Сортування переупорядковує всі елементи або за зростанням або за спаданням.

Оптимальні алгоритми дозволяють знизити час виконання програм та забезпечити передбачувану поведінку системи. Без них програми страждатимуть від затяжних затримок або навіть збоїв під час роботи з великими даними.

Сортування також є основою багатьох інших алгоритмів: від пошуку до обробки графів і розпізнавання образів.При вирішенні таких завдань важливо враховувати не тільки кількість операцій, що виконуються, але і обсяг використовуваної пам'яті.

Популярні алгоритми сортування

• Пухирцеве сортування (Bubble Sort). Найпростіший алгоритм, який порівнює пари сусідніх елементів та змінює їх місцями. Незважаючи на свою простоту, це один із найменш ефективних алгоритмів зі складністю O(n 2 ). Докладніше про складність алгоритмів ще поговоримо нижче.
• Сортування вставками (Insertion Sort). Працює шляхом вставки кожного нового елемента вже відсортований масив. Ефективний для невеликих масивів та має тимчасову складність O(n 2 ).
• Сортування вибором (Selection Sort). На кожному кроці вибирає мінімальний елемент із невідсортованої частини та поміщає його в кінець відсортованої. Підходить для масивів, де важливою є простота реалізації. Його ефективність також O(n 2).
• Пірамідальне сортування (Heap Sort). Використовує структуру даних «купа» та працює за O(n log ⁡n). Відрізняється передбачуваною продуктивністю та малими накладними витратами.
• Швидке сортування (Quick Sort). Один із найефективніших алгоритмів. Як правило, виконує сортування швидше за інших завдяки поділу масиву на менші підмасиви та подальшому рекурсивному сортуванню.
• Сортування злиттям (Merge Sort). Алгоритм, що гарантовано забезпечує O(n log ⁡n) навіть у гіршому випадку. Підходить для великих обсягів даних та збереження стабільності сортування.

У більшості випадків фахівці використовують Quick Sort та Merge Sort. Далі розберемо, із чим це пов'язано.

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

Щоб зрозуміти, чому Quick Sort та Merge Sort вважаються найкращими, важливо спочатку розібратися в основних концепціях: класифікації, складності та стабільності алгоритмів.

Ключові поняття: тимчасова та просторова складність, стабільність

• O(n) — лінійна складність, кількість операцій збільшується пропорційно до розміру вхідних даних.
• O(n 2 ) - Квадратна складність, кількість операцій зростає квадратично.
• O(n log⁡ n) — логарифмічна складність, оптимальний час для більшості сортувань, включаючи Quick Sort та Merge Sort.

Стабільність. Алгоритм сортування називається стабільним, якщо зберігає відносний порядок однакових елементів. Це особливо важливо, якщо в даних є кілька ключів для сортування, наприклад, на прізвище і потім на ім'я.

Класифікація алгоритмів сортування: де стоять Quick Sort та Merge Sort

Алгоритми сортування класифікуються за багатьма ознаками. Основні критерії - це метод виконання (внутрішній або зовнішній), стійкість, необхідність додаткової пам'яті та методика реалізації (розділяй і володарюй, вставки і т. д.).

• пухирцеве сортування,
• сортування вставками,
• сортування вибором,
• швидке сортування (Quick Sort),
• сортування злиттям (Merge Sort).

За способом реалізації Quick Sort та Merge Sort відносять до категорії «розділяй та володарюй». Вона передбачає, що масив рекурсивно ділиться кілька дрібних частин, які потім упорядковуються і об'єднуються. У цьому кожен алгоритм реалізує концепцію по-різному.

Тепер глибше розберемо особливості двох алгоритмів.

Швидке сортування, Quick Sort

Quick Sort відрізняється швидкістю виконання та ефективністю використання пам'яті. Це один із найпопулярніших алгоритмів у світі програмування.

Основна ідея базується на парадигмі «поділяй і володарюй». Алгоритм спочатку вибирає опорний елемент (pivot). Потім ділить масив на два підмасиви: в першому елементи менше або рівні pivot, а в другому - більше. Після цього кожен підмасив сортується незалежно. Потім процес рекурсивно повторюється обох підмасивів, що дозволяє ефективно впорядкувати елементи.

Quick Sort показує одну з найкращих продуктивностей серед алгоритмів сортування.

• У середньому тимчасова складність становить O(n log n). Це тим, що масив ділиться на дві рівні частини, а операції виконуються кожної з них рекурсивно.
• У найгіршому випадку складність може зрости до O(n 2 ). Це відбувається коли масив розбивається вкрай нерівномірно, наприклад, якщо елементи вже впорядковані.
• Просторова складність залежить від глибини рекурсії і становить O(log n), оскільки зберігання додаткових даних є мінімальним.

Де застосовувати та як оптимізувати

Quick Sort підходить для безлічі завдань - від упорядкування масивів у простих додатках до складних системних рішень, де потрібно забезпечити ефективне сортування на місці. Цей алгоритм часто використовується як вбудований метод сортування в популярних бібліотеках, наприклад, C++ і Python.

• Вибір опорного елемента (pivot selection). Як згадувалося, використання median-of-three чи випадкового елемента зменшує ймовірність гіршого сценарію.
• Tail Call Optimization (TCO). Оптимізація рекурсії шляхом відмови від рекурсивного виклику для однієї з частин масиву (наприклад, більш короткої) дозволяє уникнути глибоких стеків викликів і, як наслідок, переповнення стека.
• Гібридні алгоритми. На практиці часто використовується комбінація Quick Sort та інших алгоритмів, таких як Insertion Sort для невеликих підмасивів. Ця техніка знижує кількість рекурсивних викликів та зменшує накладні витрати.
• Паралельне сортування. Якщо потрібно працювати з великими обсягами даних, можна розподілити обчислення на кілька ядер процесора чи кластерів, реалізувавши паралельну версію Quick Sort.

Реалізація на Python:

def quick_sort(arr): if len(arr) pivot] # Масив елементів більше опорного # Рекурсивно сортуємо ліву та праву частини, об'єднуємо всі разом return quick_sort(left) + middle + quick_sort(right) # Приклад використання array = [10, 7 , 8, 9, 1, 5] sorted_array = quick_sort(array) print("Відсортований масив:", sorted_array)

public class QuickSort < public static void quickSort (int [] arr, int low, int high) < if (low < high) < int pivotIndex = partition (arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); >> private static int partition(int[] arr, int low, int high) < int pivot = arr[low]; int left = low + 1; int right = high; while (true) < while (left while (right >= left && arr[right] >= pivot) < right--; >if (right < left) < break; >else < int temp = arr[left]; arr [left] = arr[right]; arr[right] = temp; main(String[] args) < int[] array = ; quickSort(array, 0, array.length - 1); out.print(num + " ");

Quick Sort – це лише один із інструментів в арсеналі розробника. На практиці часто доводиться комбінувати його з іншими алгоритмами, такими як Merge Sort, щоб досягти максимальної продуктивності та ефективності.

Сортування злиттям, Merge Sort

Сортування злиттям (Merge Sort) - класичний алгоритм, що часто згадується у зв'язці з Quick Sort. Він також використовує підхід «поділяй та володарюй», але з акцентом на об'єднання (злиття) відсортованих підмасивів у підсумкову структуру.

Алгоритм ділить масив на дві частини, рекурсивно сортує кожну з них, а потім поєднує їх в один відсортований масив.

1. Ділимо масив на дві рівні частини, доки кожна не стане одноелементною.
2. Порівнюємо елементи кожної пари та зливаємо їх в один відсортований підмасив.
3. Повторюємо крок 2, доки отримаємо один повністю відсортований масив.

Ця структура робить алгоритм зрозумілим та легко реалізованим, особливо у мовах з підтримкою рекурсії: Python та Java. Однак операції вимагають додаткової пам'яті для зберігання тимчасових підмасивів. Це один із основних недоліків Merge Sort.

Реалізація на Python:

def merge_sort(arr): if len(arr)  

public class MergeSort < public static void mergeSort (int [] arr, int left, int right) < if (left < right) < int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); >> private static void merge (int [] arr, int left, int mid, int right) < int n1 = mid - left + 1; int n2 = right – mid; int[] L = new int[n1]; int[] R = new int[n2]; System.arraycopy(arr, left, L, 0, n1); System.arraycopy(arr, mid + 1, R, 0, n2); int i = 0, j = 0; int k = left; while (i < n1 && j < n2) < if (L[i] else < arr[k] = R[j]; j++; >k++; > while (i < n1) < arr[k] = L[i ];i++; kwh(j< n2) < r[j]; , 0, array.length - 1);

Merge Sort - один з небагатьох алгоритмів, які гарантують тимчасову складність O(n log n) у гіршому, середньому та кращому випадку. Все це завдяки рекурсивному поділу масиву і впорядкуванню вже відсортованих підмасивів.

Просторова складність Merge Sort складає O(n). Потрібна додаткова пам'ять для зберігання тимчасових масивів, які використовуються кожному етапі рекурсії.

Таким чином, у ситуаціях, де важлива постійна швидкість виконання незалежно від розподілу даних, краще вибирати Merge Sort. Quick Sort може страждати від квадратичної складності у найгірших випадках.

Приклади та порівняння з іншими алгоритмами

Незважаючи на великі вимоги до пам'яті, Merge Sort знаходить своє застосування у різних сценаріях. Ось деякі з них.

Зовнішнє сортування. При сортуванні даних, які не містяться в оперативну пам'ять, алгоритм може обробляти їх частинами, зберігаючи проміжні результати на диску.

Сортування пов'язаних списків. Завдяки своїй здатності легко працювати з рекурсивними структурами, Merge Sort підходить для сортування зв'язаних списків, де вставка та видалення елементів із середини можуть бути виконані за константний час.

Оптимізація у багатоядерних системах. Процес рекурсивного поділу масиву на підмасиви можна розпаралелити, що робить Merge Sort гарним вибором для багатопотокових систем та обробки даних на кластерах.

Порівняння алгоритмів Quick Sort та Merge Sort

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

Тимчасова та просторова складність

Quick Sort показує відмінну продуктивність в середньому, з тимчасовою складністю O(n log n), але в гіршому випадку падає до O(n 2 ). Це робить його менш передбачуваним. Однак через те, що алгоритм працює «на місці», його просторова складність — O(log⁡n), що мінімізує витрати пам'яті та забезпечує відмінну роботу з кешем.

Merge Sort зберігає стабільну складність O(n log n) незалежно від вхідних даних. Це робить його добрим вибором для завдань, де важлива передбачуваність, але його просторова складність O(n) потребує більше пам'яті, оскільки потрібне додаткове сховище для злиття.

Практична ефективність

Quick Sort завдяки меншій кількості операцій та інтуїтивній роботі з кеш-пам'яттю показує високу продуктивність на більшості реальних даних. Він добре працює з масивами в оперативній пам'яті.У стандартних бібліотеках, як-от C++ STL або Java Collections, використовується саме цей алгоритм.

Merge Sort застосовується у сценаріях, де дані не поміщаються в оперативну пам'ять, наприклад для зовнішнього сортування на жорстких дисках. Це пояснює його застосування у файлових системах та базах даних.

Стабільність та адаптивність

Merge Sort – стійкий алгоритм, він зберігає порядок однакових елементів. Така здатність робить його кращим для роботи з даними, де це важливо, наприклад, при сортуванні транзакцій. Quick Sort у базовій реалізації такої стабільності не має.

Що вибрати

Вибирайте Quick Sort, коли працюєте з масивами в оперативній пам'яті та хочете оптимізувати роботу програми за рахунок низької просторової складності та гарної роботи з кешем. Merge Sort залиште для завдань, пов'язаних із зовнішнім сортуванням або якщо важлива стабільність алгоритму.

Оптимізація з використанням специфічних реалізацій чи адаптацій алгоритмів

Обидва алгоритми можна додатково оптимізувати під конкретні вимоги. Quick Sort можна адаптувати, комбінуючи його з Insertion Sort для невеликих підмасивів, щоб покращити продуктивність на дрібних даних. Merge Sort може бути реалізований з багатопоточністю для більш ефективного розподілу навантаження під час сортування на багатопроцесорних системах.

Приклади застосування алгоритмів сортування, з якими ви стикалися.

Google, YouTube, Netflix та інші медіакомпанії використовують Quick Sort, щоб систематизувати контент перед тим, як запропонувати його користувачам. Цей алгоритм найчастіше є основою формування стрічки рекомендацій.

PostgreSQL використовує Merge Sort під час виконання зовнішнього сортування. Це дозволяє обробляти великі таблиці даних. А Bloomberg Terminal за допомогою цього ж алгоритму сортує часові ряди та аналізує фінансові дані в реальному часі.

Висновок

І насамкінець пару слів про штучний інтелект (куди ж без нього). Нещодавні прориви в цій галузі призвели до відкриття нових алгоритмів сортування, які були інтегровані в усталені бібліотеки, такі як libc++ LLVM. Ці досягнення можуть покращити продуктивність до 70% для коротких послідовностей та приблизно до 1,7% для великих наборів даних, що перевищують 250 000 елементів.

Але навіть із такими інноваціями класичні алгоритми Quick Sort та Merge Sort все ще використовуються. Інтеграція ІІ у класичні підходи відкриває нові горизонти для оптимізації, дозволяючи, наприклад, ефективніше вибирати опорні елементи та прогнозувати оптимальні точки розбиття.

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

Основні види сортувань та приклади їх реалізації

На співбесідах майбутнім стажерам-розробникам дають завдання на знання структур даних та алгоритмів, зокрема сортувань. Академія Яндекса та співавтор спеціалізації «Мистецтво розробки на сучасному C++» Ілля Шишков склали список для підготовки з методами сортування, прикладами їх реалізації та гіфками, щоб краще зрозуміти, як вони працюють.

Пухирцеве сортування та його поліпшення

Сортування бульбашкою

Сортування бульбашкою - один із найвідоміших алгоритмів сортування. Тут потрібно послідовно порівнювати значення сусідніх елементів та змінювати числа місцями, якщо попереднє виявляється більшим за наступне. Таким чином, елементи з великими значеннями виявляються в кінці списку, а з меншими залишаються на початку.

Цей алгоритм вважається навчальним і майже застосовується практично через низьку ефективність: він повільно працює на тестах, у яких маленькі елементи (їх називають «черепахами») стоять наприкінці масиву.Однак на ньому засновані багато інших методів, наприклад, шейкерне сортування та сортування гребінцем.

void
BubbleSort(vectorint>& values)
< for (size_t idx_i = 0; idx_i + 1 < values.size(); ++idx_i) < for (size_t idx_j = 0; idx_j + 1 < values.size() - idx_i; ++idx_j) < if (values[idx_j + 1] < values[idx_j]) < swap(values[idx_j], values[idx_j + 1]); > > > >

Сортування перемішуванням (шейкерне сортування)

Шейкерне сортування відрізняється від бульбашкового тим, що воно двонаправлене: алгоритм переміщається не строго зліва направо, а спочатку зліва направо, потім праворуч наліво.

void
ShakerSort(vectorint>& values)
< if (Values.empty()) < return; >
int left = 0; int right = values.size() - 1; while (Left for (int i = right; i > left; --i) < if (values[i - 1] > values[i]) < swap(values[i - 1], values[i]); > > ++left; for (int i = left; i <right; ++i) < if (values[i] > values[i + 1]) < swap(values[i], values[i + 1]); > > --right; > >

Сортування гребінцем

Сортування гребінцем - поліпшення сортування бульбашкою. Її ідея полягає в тому, щоб «усунути» елементи з невеликими значеннями в кінці масиву, які уповільнюють роботу алгоритму. Якщо при бульбашковому та шейкерному сортуваннях при переборі масиву порівнюються сусідні елементи, то при «розчісуванні» спочатку береться досить велика відстань між порівнюваними значеннями, а потім вона звужується аж до мінімального.

Початковий розрив потрібно вибирати не випадковим чином, а з урахуванням спеціальної величини - фактора зменшення, оптимальне значення якого дорівнює 1,247. Спочатку відстань між елементами дорівнюватиме розміру масиву, поділеному на 1,247; на кожному наступному етапі відстань буде знову ділитися на фактор зменшення - і так до закінчення роботи алгоритму.

void
CombSort(vectorint>& values)
< const
double factor = 1.247; // Фактор зменшення
double step=values.size() - 1; while (step >= 1) < for (int i = 0; i + step < values.size(); ++i) < if (values[i] > values[i + step]) < swap(values[i], values[i + step]); > > step /= factor; > // сортування бульбашкою
for (size_t idx_i = 0; idx_i + 1 < values.size(); ++idx_i) < for (size_t idx_j = 0; idx_j + 1 < values.size() - idx_i; ++idx_j) < if (values[idx_j + 1] < values[idx_j]) < swap(values[idx_j], values[idx_j + 1]); > > > >

Прості сортування

Сортування вставками

При сортуванні вставками масив поступово перебирається зліва направо. При цьому кожен наступний елемент розміщується так, щоб він опинився між найближчими елементами з мінімальним та максимальним значенням.

void
InsertionSort(vectorint>& values)
< for (size_t i = 1; i < values.size(); ++i) < int x = values[i]; size_t j = i; while (j > 0 && values[j - 1] > x) < values[j] = values[j - 1]; --j; > values[j] = x; > >

Сортування вибором

Спочатку потрібно розглянути підмножину масиву та знайти в ньому максимум (або мінімум). Потім вибране значення змінюють місцями зі значенням першого елемента, що не відсортував. Цей крок потрібно повторювати доти, доки в масиві не закінчаться невідсортовані підмасиви.

void
SelectionSort(vectorint>& values)
< for (auto i = значення.begin(); i != values.end(); ++i) < auto j = std::min_element(I, values.end()); swap(*i, *j); > >

Ефективні сортування

Швидке сортування

Цей алгоритм складається із трьох кроків. Спочатку з масиву потрібно вибрати один елемент його зазвичай називають опорним. Потім інші елементи в масиві перерозподіляють так, щоб елементи менше опорного виявилися до нього, а великі або рівні після. А далі рекурсивно застосовують перші два кроки до підмасивів праворуч та ліворуч від опорного значення.

Швидке сортування винайшли в 1960 для машинного перекладу: тоді словники зберігалися на магнітних стрічках, а сортування слів оброблюваного тексту дозволяло отримати переклади за один прогін стрічки, без перемотування назад.

int
Partition(vectorint>& values, int l, int r)
< int x = values[r]; int less = l; for (int i = l; i<r; ++i) < if (values[i] swap(values[i], values[less]); ++less; > > swap(values[less], values[r]); return less; > void
QuickSortImpl(vectorint>& values, int l, int r)
< if (l < r) < int q = Partition(values, l, r); QuickSortImpl(values, l, q - 1); QuickSortImpl(Values, q + 1, r); > > void
QuickSort(vectorint>& values)
< if (! Values.empty()) < QuickSortImpl(values, 0, values.size() - 1); > >

Сортування злиттям

Сортування злиттям стане в нагоді для таких структур даних, в яких доступ до елементів здійснюється послідовно (наприклад, для потоків). Тут масив розбивається на приблизно дві рівні частини і кожна з них сортується окремо. Потім два відсортовані підмасиви зливаються в один.

void
MergeSortImpl(vectorint>& values, vectorint>& buffer, int l, int r) < if (l < r) < int m = (l + r) / 2; MergeSortImpl(Values, buffer, l, m); MergeSortImpl(values, buffer, m + 1, r); int k = l; for (int i = l, j = m + 1; i if (j > r || (i else
< buffer[k] = values[j]; ++j; >++k; >
for (int i = l; i > > void
MergeSort(vectorint>& values)
< if (! Values.empty()) < vectorint>
buffer(values.size()); MergeSortImpl(values, buffer, 0, values.size() - 1); > >

Пірамідальне сортування

При цьому сортуванні спочатку будується піраміда із елементів вихідного масиву. Піраміда (або двійкова купа) - це спосіб представлення елементів, при якому від кожного вузла може відходити не більше двох відгалужень. А значення у батьківському вузлі має бути більше значень у його двох дочірніх вузлах.

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

void
HeapSort(vectorint>& values) < std::make_heap(Values.begin(), значення.end()); for (auto i = значення.end(); i != values.begin(); --i) < std::pop_heap(Values.begin(), i); > >