Анімована ілюстрація "сортування бульбашкою" (bubble sort)



"Сортування бульбашкою" (bubble sort)

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

a0 < a1 < a2 < ... < an-1

(зазвичай за замовчуванням розглядають саме задачу про впорядкування елементів за зростанням)

Алгоритм "Сортування бульбашкою" (bubble sort) працює наспутним чином:

    a -- вхідний масив із n елементів (що мають індекси від 0 до n-1)

    was_swapped = 1; // цілочисельна змінна, що показуватиме, чи вдалося вже досягти впорядкованості масиву
    
    Повторюємо допоки не виявиться, що was_swapped == 0 {
            was_swapped = 0; // робимо припущення, що наш масив вже впорядковано
            
            повторюємо для всіх j = 0, 1, 2, 3, ..., n-2 {
            
                    порівнюємо aj та aj+1: у впорядкованого масиву мало би бути aj < aj+1 
                    Отже, аналізу потребує лише випадок, якщо ця нерівність порушується.
                    Якщо aj > aj+1 {
                            Міняємо місцями значення j-го та j+1-го елементів (наприклад,
                             використавши для цього "проміжну" змінну: tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; )
                            was_swapped = 1; // показуємо, що в масиві було виявлено невпорядкованість
                    }
            
            }
                
    }
    
Можна збагнути, що після першого повного виконання циклу по j останнім у масиві виявиться елемент, що мав найбільше значення.

Для цього розглянемо два приклади:

Приклад 1
          a:    7 5 1 2 3 4

після j = 0:    5 7 1 2 3 4
після j = 1:    5 1 7 2 3 4
після j = 2:    5 1 2 7 3 4
після j = 3:    5 1 2 3 7 4
після j = 4:    5 1 2 3 4 7
(цикл по j завершено)

Приклад 2
          a:    5 2 1 7 3 4

після j = 0:    2 5 1 7 3 4
після j = 1:    2 1 5 7 3 4
після j = 2:    2 1 5 7 3 4  -- 1)зауважте, що змін  в масиві не відбулося ! (проте was_swapped залишилося рівним 1 і не стало 0)
                                    2) зауважте також, що до цього часу "спливало" число 5, а тепер його "спливання" зупинилося, адже 
                                     праворуч знайшлося число, більше за 5. Однак, на наступній ітерації почне "спливати" уже це, більше, число!
після j = 3:    2 1 5 3 7 4  
після j = 4:    2 1 5 3 4 7
(цикл по j завершено)

(жирним шрифтом виділено пари сусідніх елементів, що порівнюються на відповідному кроці)

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

Якщо ж тепер повторити такий же цикл по j, то передостаннім опиниться елемент, який мав "перед-найбільше" значення, і так далі.

Зрештою, повторюючи такі цикли "спливання" елементів, ми врешті-решт відсортуємо увесь масив!

 

Але можна також помітити, що при другому виконанні циклу по j достатньо, щоб j пробігав уже не всі елементи, а всі, окрім останнього, адже ми точно знаємо, що останнім в масиві вжеопинився той (максимальний) елемент, який і мав там опинитися!

Аналогічно: кожного наступного повторення цикл по j можна робити "на один крок коротшим":

    a -- вхідний масив із n елементів

    was_swapped = 1; // цілочисельна змінна, що показуватиме, чи вдалося вже досягти впорядкованості масиву
        
    Повторюємо для всіх i = n-1, n-2, n-3, ..., 1 , або поки не виявиться, що was_swapped == 0 {
            was_swapped = 0; // робимо припущення, що наш масив вже впорядковано
            
            повторюємо для всіх j = 0, 1, 2, 3, ..., i-1 {
            
                    Якщо aj > aj+1 {
                            Міняємо місцями значення j-го та j+1-го елементів
                            was_swapped = 1; // показуємо, що в масиві було виявлено невпорядкованість
                    }
            
            }
                
    }
    

У цій дещо вдосконаленій версії сортування додаткова умова "або поки не виявиться, що was_swapped == 0" дозволяє достроково зупинити програму, якщо виявиться, що заданий на вході масив уже був частково відсортованим і для його повного сортування потрібно було поміняти місцями лише декілька елементів.

Перевірку такого роду умови в C++ можна виконати як

    for(int i = n-1; i>0 && was_swapped; i--) {
	
    }

Завдання:

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

2) змінити програму так, щоб вона впорядковувала елементи масиву за спаданням.

3) змінити програму так, щоб сортування масиву відбувалося у окремій функції, в яку масив, який потрібно відсортувати, передавався б як один з параметрів.

4*) підрахувати кількість кожної з маленьких літер англійської абетки у файлі txt.txt, після чого -- відсортувати літери за "популярністю" їх уживання.

Увага! до цього часу ми сортували елементи масиву і не цікавилися тим, на якій позиції знаходився елемент, що виявився найменшим або найбільшим; одержання "рейтингу" літер потребуватиме деякої модифікації коду функції, що виконувала сортування, аби в ній не втрачалася інформація про те, який номер мав кожен із елементів відсортованого масиву у вхідному, невідсортованому масиві).

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

Вказівка до задач: в нагоді можуть стати фрагменти наступної невеличкої програми, яка друкує на екран 10 випадкових чисел в межах від -100 до +100 кожне:

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main(int argc, char** argv) { srand (time(NULL)); for(int i = 0; i < 10; i++) { cout << rand() % 200 - 100 << endl; } return 0; }
У ній використано функцію rand() з бібліотеки cstdlib та функцію time() (з аргументом NULL) з бібліотеки ctime, але яка повертає кількість секунд, що минули від 00:00 1-го січня 1970 року (звична точка відліку для дат у комп'ютері) до мементу виклику цієї функції. Остання потрібна для ініціалізації генератора випадкових чисел (див. рядок srand (time(NULL));). Без такої ініціалізації програма працюватиме, але послідовність випадкових чисел, які будуть генеруватися, буде одна і та ж сама при кожному запуску програми (утім, цей недолік може стати перевагою, якщо доводиться "відлагоджувати" (debug) програму і досягати відтворюваності всіх вхідних параметрів). Варто поексперементувати і виявити, який ефект справляє наявність/відсутність викливу функції srand.

Метод бульбашки - один з найпростіших методів сортування. Він є досить "повільним" (далеко не найбільш ефективним) і на практиці для вирішення задачі сортування як такої майже не застосовується.

Кількісна характеристика складності алгоритму - кількість операцій, яку виконає процесор комп'ютера, виконуючи алгоритм.

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

У випадку алгоритму сортування бульбашкою ця залежність є ~ n2, де n - довжина масиву.

Це записують як твердження про те, що алгоритм має складність за часом O(n2).

 

Існують більш швидкі алгоритми сортування, для який складність за часом є O(n*log(n)), а оскільки n*log(n) << n2, то що більшим є n, то більш відчутною за "швидкістю" роботи програми буде перевага кращого алгоритму.



Сортування злиттям (merge sort)

wiki (ua) (будь ласка, не копіюйте звідки код програми -- написати власний буде реально простіше!)

Сортування злиттям засноване на операції сполученням ("злиттям") двох вже впорядкованих масивів меншої довжини у новий впорядкований масив більшої довжини. Наспутний приклад ілюструє, як відбувалось би таке злиття

        масив 1         масив 2      новий масив
       2 3 5 7 9       1 4 6 8
  
Крок
1.     2 3 5 7 9       1 4 6 8        1
       ^               ^

2.     2 3 5 7 9       1 4 6 8        1 2
       ^                 ^

3.     2 3 5 7 9       1 4 6 8        1 2 3
         ^               ^

4.     2 3 5 7 9       1 4 6 8        1 2 3 4
           ^             ^

5.     2 3 5 7 9       1 4 6 8        1 2 3 4 5
           ^               ^

6.     2 3 5 7 9       1 4 6 8        1 2 3 4 5 6
             ^             ^

7.     2 3 5 7 9       1 4 6 8        1 2 3 4 5 6 7
             ^               ^

8.     2 3 5 7 9       1 4 6 8        1 2 3 4 5 6 7 8
               ^             ^

9.     2 3 5 7 9       1 4 6 8        1 2 3 4 5 6 7 8 9
               ^               ^

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

В алгоритмі сортування злиттям масив, що підлягає сортуванню ділять навпіл, половинки - знову навпіл і так далі, аж поки довжина "фрагментів" не стане рівною всього двом елементам. Після цього двоелементні фрагменти сортують і починають сполучати ("зливати") між собою у згаданий вище спосіб. Далі сполучають між собою утворені (відсортовані!) 4-елементні фрагменти, потім - 8-елементні і так далі. Врешті-решт отримують відсортований масив.

Можна показати, що складність за часом для сортування злиттям є O(n*log(n)).

Приклад, що ілюструє основну ідею алгоритма

Завдання:

1) модифікувати попередню програму так, щоб сортування масиву в ній виконувалося матодом злиття

2) змінити програму так, щоб сортування масиву відбувалося у окремій функції, в яку масив, який потрібно відсортувати, передавався б як один з параметрів.

3*) порівняти швидкодію алгоритмів сортування методом будьбашки та методом злиття для вхідних масивів різної довжини.

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

Примітка 2: для визначення поточного часу вбудованого годинника комп'ютера можна скористатися функцією clock() з бібліотеки ctime (зауважте, що функція повертає результат типу clock_t , а для перетворення цих величин у секунди потрібно скористатися константою CLOCKS_PER_SEC , оголошеною в ctime).



насправді, алгоритмів сортування досить багато!