Сортування масиву — це процес впорядкування всіх елементів масиву в певному порядку. Дуже часто це буває корисним. Наприклад, у вашій поштовій скриньці електронні листи відображаються в залежності від часу отримання; нові листи вважаються більш релевантними, ніж ті, які ви отримали півгодини, годину, дві або день назад; коли ви переходите до списку своїх контактів, імена зазвичай знаходяться в алфавітному порядку, тому що так легше щось знайти. Всі ці випадки включають в себе сортування даних перед їх фактичним виведенням.
Як працює сортування?
Сортування даних може зробити пошук всередині масиву більш ефективним не тільки для людей, а й для комп’ютерів. Наприклад, розглянемо випадок, коли нам потрібно дізнатися, чи відображається певне ім’я в списку імен. Щоб це дізнатися, потрібно перевірити кожен елемент масиву на відповідність нашому значенню. Пошук в масиві з безліччю елементів може виявитися занадто неефективним (ресурсозатратним).
Проте, припустимо, що наш масив з іменами відсортований в алфавітному порядку. Тоді наш пошук починається з першої літери нашого значення і закінчується буквою, яка йде наступною по алфавіту. У такому випадку, якщо ми дійшли до цієї букви і не знайшли ім’я, то точно знаємо, що воно не знаходиться в іншій частині масиву, тому що в алфавітному порядку нашу букву ми вже пройшли!
Не секрет, що є і кращі алгоритми пошуку всередині відсортованих масивів. Використовуючи простий алгоритм, ми можемо шукати певний елемент в відсортованому масиві, що містить 1 000 000 елементів, використовуючи всього лише 20 порівнянь! Недоліком, звичайно ж, є те, що сортування масиву з такою величезною кількістю елементів — процес досить-таки ресурсозатратний, і він точно не виконується заради одного пошукового запиту.
У деяких випадках сортування масиву робить пошук непотрібним. Наприклад, ми шукаємо найкращий результат проходження тесту серед студентів. Якщо масив не впорядкований, то нам доведеться переглянути кожен елемент масиву, щоб знайти найвищу оцінку. Якщо ж масив відсортований, то найвища оцінка перебуватиме або на першій позиції, або на останній (в залежності від методу сортування масиву: в порядку зростання чи в порядку спадання), тому нам не потрібно шукати взагалі!
Сортування зазвичай виконується шляхом повторного порівняння пар елементів масиву і заміни значень, якщо вони відповідають певним критеріям. Порядок, в якому ці елементи порівнюються, залежить від того, який алгоритм сортування використовується. Критерії визначають спосіб сортування масиву (наприклад, в порядку зростання чи в порядку спадання).
Щоб поміняти два елементи місцями, ми можемо використати функцію std::swap() зі Стандартної бібліотеки C++, яка визначена в заголовку algorithm. У C++11 функція std::swap() була перенесена в заголовок utility:
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> #include <algorithm> // для std::swap. У C++11 використовуйте заголовок <utility> int main() { int a = 3; int b = 5; std::cout << "Before swap: a = " << a << ", b = " << b << '\n'; std::swap(a, b); // міняємо місцями значення змінних a і b std::cout << "After swap: a = " << a << ", b = " << b << '\n'; } |
Результат виконання програми:
Before swap: a = 3, b = 5
After swap: a = 5, b = 3
Після виконання операції заміни, значення змінних a і b помінялися місцями.
Сортування масивів методом вибору
Існує безліч способів сортування масивів. Сортування масивів методом вибору, мабуть, найпростіше для розуміння, хоча і одне з найповільніших.
Для сортування масиву методом вибору від найменшого до найбільшого елементу виконуються наступні кроки:
Починаючи з елементу під індексом 0, шукаємо в масиві найменше значення.
Знайдене значення міняємо місцями з нульовим елементом.
Повторюємо кроки №1 і №2 уже для наступного індексу в масиві (відсортований елемент більше не чіпаємо).
Іншими словами, ми шукаємо найменший елемент в масиві і переміщуємо його на перше місце. Потім шукаємо другий найменший елемент і переміщуємо його вже на друге місце після першого найменшого елемента. Цей процес триває до тих пір, поки в масиві не закінчаться невідсортовані елементи.
Ось приклад роботи цього алгоритму в масиві з п’ятьма елементами:
{ 30, 50, 20, 10, 40 }
Спочатку шукаємо найменший елемент, починаючи з індексу 0:
{ 30, 50, 20, 10, 40 }
Потім міняємо місцями найменший елемент з елементом під індексом 0:
{ 10, 50, 20, 30, 40 }
Тепер, коли перший елемент масиву відсортований, ми його ігноруємо. Шукаємо наступний найменший елемент, але вже починаючи з індексу 1:
{ 10, 50, 20, 30, 40 }
І міняємо його місцями з елементом під індексом 1:
{ 10, 20, 50, 30, 40 }
Тепер ми можемо ігнорувати перші два елементи. Шукаємо наступний найменший елемент, починаючи з індексу 2:
{ 10, 20, 50, 30, 40 }
І міняємо його місцями з елементом під індексом 2:
{ 10, 20, 30, 50, 40 }
Шукаємо наступний найменший елемент, починаючи з індексу 3:
{ 10, 20, 30, 50, 40 }
І міняємо його місцями з елементом під індексом 3:
{ 10, 20, 30, 40, 50 }
Шукаємо наступний найменший елемент, починаючи з індексу 4:
{ 10, 20, 30, 40, 50 }
І міняємо його місцями з елементом під індексом 4 (виконується самозаміна, тобто нічого не робимо):
{ 10, 20, 30, 40 50 }
Готово!
{ 10, 20, 30, 40, 50 }
Зверніть увагу, що останнє порівняння завжди буде одиночним (тобто самозаміна), що є зайвою операцією, тому, фактично, ми можемо зупинити виконання сортування перед останнім елементом масиву.
Сортування масивів методом вибору в C++
Ось як алгоритм реалізований в мові C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <algorithm> // для std::swap. У C++11 використовуйте заголовок <utility> int main() { const int length = 5; int array[length] = { 30, 50, 20, 10, 40 }; // Перебираємо кожен елемент масиву (крім останнього, він вже буде відсортований до того часу, коли ми до нього дійдемо) for (int startIndex = 0; startIndex < length - 1; ++startIndex) { // У змінній smallestIndex зберігається індекс найменшого значення, яке ми знайшли в поточній ітерації. // Починаємо з того, що найменший елемент в цій ітерації - це перший елемент (індекс 0) int smallestIndex = startIndex; // Потім шукаємо менший елемент в іншій частині масиву for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex) { // Якщо ми знайшли елемент, який менше нашого найменшого елементу, if (array[currentIndex] < array[smallestIndex]) // то запам'ятовуємо його smallestIndex = currentIndex; } // smallestIndex тепер найменший елемент. // Міняємо місцями наше початкове найменше число з тим, яке ми виявили std::swap(array[startIndex], array[smallestIndex]); } // Тепер, коли весь масив відсортований - виводимо його на екран for (int index = 0; index < length; ++index) std::cout << array[index] << ' '; return 0; } |
Найбільш заплутаною частиною цього алгоритму є цикл всередині іншого циклу (так званий “вкладений цикл”). Зовнішній цикл (startIndex) перебирає елементи один за одним (по черзі). У кожній ітерації зовнішнього циклу внутрішній цикл (currentIndex) використовується для пошуку найменшого елементу серед елементів, які залишилися в масиві (починаючи з startIndex + 1). smallestIndex відстежує індекс найменшого елементу, знайденого внутрішнім циклом. Потім smallestIndex міняється значенням з startIndex. І, нарешті, зовнішній цикл (startIndex) переходить до наступного індексу масиву, і процес повторюється.
Підказка: Якщо у вас виникли проблеми з розумінням того, як працює вищенаведена програма, то спробуйте записати її виконання на листку паперу. Запишіть початкові (невідсортовані) елементи масиву горизонтально в рядку у верхній частині листа. Намалюйте стрілки, що вказують, які елементи є startIndex, currentIndex і smallestIndex на даний момент. Прокрутіть виконання програми вручну і перемалюйте стрілки по мірі зміни індексів. Після кожної ітерації зовнішнього циклу намалюйте новий рядок, який показує поточний стан масиву (розташування його елементів).
Сортування тексту виконується за допомогою того ж алгоритму. Просто змініть тип масиву з int на string і ініціалізуйте його за допомогою відповідних значень.
Функція std::sort()
Оскільки операція сортування масивів дуже поширена, то Стандартна бібліотека C++ надає вбудовану функцію сортування std::sort(). Вона знаходиться в заголовку algorithm і викликається наступним чином:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <algorithm> // для std::sort int main() { const int length = 5; int array[length] = { 30, 50, 20, 10, 40 }; std::sort(array, array+length); for (int i=0; i < length; ++i) std::cout << array[i] << ' '; return 0; } |
Тест
Завдання №1
Напишіть на листку паперу виконання сортування наступного масиву методом вибору (так, як ми це робили вище):
{30, 60, 20, 50, 40, 10}
Відповідь №1
30 60 20 50 40 10
10 60 20 50 40 30
10 20 60 50 40 30
10 20 30 50 40 60
10 20 30 40 50 60
10 20 30 40 50 60 (самозаміна)
10 20 30 40 50 60 (самозаміна)
Завдання №2
Перепишіть код програми з підзаголовку “Сортування масивів методом вибору в C++” так, щоб сортування виконувалося в порядку спадання (від найбільшого числа до найменшого). Хоча це може здатися складним на перший погляд, але, насправді, це дуже просто.
Відповідь №2
Просто замініть наступний рядок коду:
|
1 |
if (array[currentIndex] < array[smallestIndex]) |
на
|
1 |
if (array[currentIndex] > array[smallestIndex]) |
Також smallestIndex варто перейменувати в largestIndex:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <algorithm> // для std::swap. У C++11 використовуйте заголовок <utility> int main() { const int length= 5; int array[length] = { 30, 50, 20, 10, 40 }; // Перебираємо кожен елемент масиву, крім останнього for (int startIndex = 0; startIndex < length - 1; ++startIndex) { // largestIndex - це індекс найбільшого елемента, який ви виявили на даний момент int largestIndex = startIndex; // Перебираємо кожен елемент масиву, починаючи з startIndex + 1 for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex) { // Якщо поточний елемент більше нашого найбільшого елемента, if (array[currentIndex] > array[largestIndex]) // то це новий найбільший елемент в цій ітерації largestIndex = currentIndex; } // Міняємо місцями наше стартове число з виявленим найбільшим елементом std::swap(array[startIndex], array[largestIndex]); } // Виводимо відсортований масив на екран for (int index = 0; index < length; ++index) std::cout << array[index] << ' '; return 0; } |
Завдання №3
Це завдання вже трохи складніше.
Ще одним простим методом сортування елементів масиву є “сортування бульбашкою” (або “бульбашкове сортування”). Суть полягає в порівнянні пари значень, які знаходяться поруч, і, якщо виконуються вказані критерії, значення з цієї пари міняються місцями. І таким чином елементи «скачуть бульбашкою» до кінця масиву. Хоча є кілька способів оптимізувати сортування бульбашкою, в цьому завданні ми будемо дотримуватися неоптимізованої версії, тому що вона є простішою.
При неоптимізованій версії сортування бульбашкою виконуються наступні кроки для сортування масиву від найменшого до найбільшого значення:
Порівнюється елемент масиву з індексом 0 з елементом масиву з індексом 1. Якщо елемент з індексом 0 більше елементу з індексом 1, то значення міняються місцями.
Потім ми переміщуємося до наступної пари значень: елемент з індексом 1 і елемент з індексом 2 і так до тих пір, поки не досягнемо кінця масиву.
Повторюємо крок №1 і крок №2 до тих пір, поки весь масив не буде відсортований.
Напишіть програму, яка відсортує наступний масив бульбашковим сортуванням відповідно до вищевказаних правил:
|
1 2 |
const int length(9); int array[length] = { 7, 5, 6, 4, 9, 8, 2, 1, 3 }; |
В кінці програми виведіть відсортовані елементи масиву.
Підказка: Якщо ми можемо впорядкувати тільки один елемент за одну ітерацію, то це означає, що нам потрібно буде повторити виконання циклу стільки разів, скільки є чисел в нашому масиві (його довжина), щоб гарантувати виконання сортування всього масиву.
Відповідь №3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <algorithm> // для std::swap. У C++11 використовуйте заголовок <utility> int main() { const int length(9); int array[length] = { 7, 5, 6, 4, 9, 8, 2, 1, 3 }; for (int iteration = 0; iteration < length-1; ++iteration) { // Перебираємо кожен елемент масиву до останнього елементу (не включно). // Останній елемент не має пари для порівняння for (int currentIndex = 0; currentIndex < length - 1; ++currentIndex) { // Якщо поточний елемент більше елементу після нього, то міняємо їх місцями if (array[currentIndex] > array[currentIndex+1]) std::swap(array[currentIndex], array[currentIndex + 1]); } } // Виводимо відсортовний масив на екран for (int index = 0; index < length; ++index) std::cout << array[index] << ' '; return 0; } |
Завдання №4
Реалізуйте наступні два рішення оптимізації алгоритму сортування бульбашкою, який ви написали в попередньому завданні:
Зверніть увагу, що з кожним виконанням сортування бульбашкою найбільше значення в масиві переміщується до кінця. Після першої ітерації останній елемент масиву вже буде відсортований. Після другої ітерації вже буде відсортований передостанній елемент масиву і т.д. З кожною новою ітерацією нам не потрібно буде перевіряти елементи, які вже були відсортовані. Змініть свій цикл так, щоб не перевіряти елементи, які вже були відсортовані.
Якщо протягом всієї ітерації не виконається жодної заміни, то ми знаємо, що масив вже відсортований. Додайте перевірку того, чи були зроблені будь-які заміни в поточній ітерації, і, якщо ні — завершіть виконання циклу. Якщо цикл був завершений, то виведіть інформацію про те, на якій (по рахунку) ітерації сортування елементів завершилося.
Приклад результату виконання вашої програми:
Early termination on iteration: 8
1 2 3 4 5 6 7 8 9
Відповідь №4
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <algorithm> // для std::swap. У C++11 використовуйте заголовок <utility> int main() { const int length(9); int array[length] = { 7, 5, 6, 4, 9, 8, 2, 1, 3 }; for (int iteration = 0; iteration < length-1; ++iteration) { // Пам'ятайте про те, що останній елемент буде відсортований і в кожній наступній ітерації циклу, // тому наше сортування "закінчується" одним елементом раніше int endOfArrayIndex(length - iteration); bool swapped(false); // відслідковуємо, чи були виконані заміни в цій ітерації // Перебираємо кожен елемент масиву до останнього (не включно). // Останній елемент не має пари для порівняння for (int currentIndex = 0; currentIndex < endOfArrayIndex - 1; ++currentIndex) { // Якщо поточний елемент більше елементу після нього, то міняємо їх місцями if (array[currentIndex] > array[currentIndex + 1]) { // Виконуємо заміну std::swap(array[currentIndex], array[currentIndex + 1]); swapped = true; } } // Якщо в цій ітерації не виконалося ні однієї заміни, то цикл можна завершувати if (!swapped) { // Виконання починається з нульової ітерації, але ми звикли рахувати, починаючи з 1, тому для підрахунку кількості ітерацій додаємо одиницю std::cout << "Early termination on iteration: " << iteration+1 << '\n'; break; } } // Виводимо відсортований масив на екран for (int index = 0; index < length; ++index) std::cout << array[index] << ' '; return 0; } |
Оцінити статтю:
(8 оцінок, середня: 4,88 з 5)
Loading...