Теоретичні відомості

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

Алгоритм сортування бульбашкою, як і сортування вибором порівняно неефективний. Його приблизний час роботи О(n^2), де n - кількість елементів масиву.

Цей метод сортування характеризується дуже простим кодом і алгоритмом. Наведу по-кроково роботу сортування бульбашкою:

5 4 3 2 1 // початкова послідовність елементів

4 5 3 2 1

4 3 5 2 1

4 3 2 5 1

4 3 2 1 5

3 4 2 1 5

3 2 4 1 5

3 2 1 4 5

2 3 1 4 5

2 1 3 4 5

1 2 3 4 5 // результат

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

Ми порівнюємо 1 і 2 елементи масиву і якщо 1 більше 2 то міняємо їх місцями; потім порівнюємо 2 і 3 елементи... і так до кінця, поки не завершимо перший прохід.

Якщо зробити n-1 проходів то ми повністю відсортуємо всі n елементів.

В наступному прикладі вже після переходу i=7 буде видно кінцевий результат (і вже можна припиняти роботу miniaty = false)

Рисунок 15 – Схема сортування масива методом бульбашки

Білі клітинки - це клітинки з вже відсортованими найбільшими елементами, які вже не треба порівнювати.

C++ функція що сортує масив чисел arr[ ] і складається з n елементів має наступний вигляд: 1. Суть.

for(j= 0; j < n - 1; j++)

{ for(i = 0; i < n - 1; i++)

{

if (arr[i] > arr[i + 1])

{// перевірка, якщо так, то міняти місцями

tmp = arr[i]; // зберігаємо і

arr[i] = arr[i + 1]; // в і кладемо і+1

arr[i + 1] = tmp; // в і+1 кладемо і

}

}

}

Аналогічне сортування можна виконати, коли найбільший елемент буде «спливати», а найменший «тонути», тобто навпаки.

Реалізація алгоритму:

#include <iostream>#include <cstdlib>using namespace std;const int SIZE = 25;int array[SIZE];// заповнення масиву випадковими числамиvoid GenerationArray(){ // прив'язка до часу для генерації чисел без повторень srand(time(0)); for (int i=0; i<SIZE; i++) { // заповнення масиву числами <100 array[i] = rand()%100; }}// виведення масиву на екранvoid ShowArray(){ for (int i=0; i<SIZE; i++) { cout << array[i] << " "; } cout << endl;}int main(){ int temp; GenerationArray(); ShowArray(); // сортування бульбашкою for (int x=SIZE; x>0; x--) { for (int i=0; i<SIZE-1; i++) { // якщо число більше за попереднє if (array[i] > array[i+1]) { // міняємо їх місцями temp = array[i]; array[i] = array[i+1]; array[i+1] = temp; } } } ShowArray(); return 0;}

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

Головною проблемою сортування бульбашкою є велика кількість перестановок елементів. В сортуванні вибором ця проблема вирішена. Тут елемент відразу займає свою кінцеву позицію.

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

Рисунок 16 – Перший крок

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

Потім операція повторюється для підмасиву a[2..n]:

Рисунок 17 – Повторення операції

і т.д.

Покрокова робота сортування:

5 4 6 9 3 2 1 7 8 // початкова послідовність

1 4 6 9 3 2 5 7 8

1 2 6 9 3 4 5 7 8

1 2 3 9 6 4 5 7 8

1 2 3 4 6 9 5 7 8

1 2 3 4 5 9 6 7 8

1 2 3 4 5 6 9 7 8

1 2 3 4 5 6 7 9 8

1 2 3 4 5 6 7 8 9 // результат

Принцип сортування: масив також поділяється на відсортовану та невідсортовану частини. На першому кроці весь масив - невідсортований. У невідсортованій частині знаходиться мінімальний (або максимальний) елемент та міняється місцями з першим елементом невідсортованої частини. Межа відсортованої частини зсувається вправо на 1. Процедура виконується ціклічно, n-1 раз (останній елемент пересувати не треба).

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

Приклад.Візьмемо кілька випадкових чисел:

Рисунок 18 – Схема сортування масиву вибором

Весь масив відсортовано.

На і-му кроці вважається масив a[1]…a[i], а вставляємо елемент a[i+1]. Вставляти можна, послідовно порівнюючи a[i+1] з a[1], a[2],…, поки не знайдеться «дірка» j.

Тоді слід зсунути елементи a[j+1].. a[i] вправо на один елемент, а a[i+1] записати на місце a[j+1].

Може статися, що a[i+1] більше за будь-який з членів відсортованої частини. Тоді дірку не буде знайдено. Тому слід контролювати номер j, щоб не вийти за межі відсортованої частини.

Реалізація алгоритму:

#include <iostream>#include <cstdlib>using namespace std;const int SIZE = 25;int array[SIZE];// заповнення масиву випадковими числамиvoid GenerationArray(){ // прив'язка до часу для генерації чисел без повторень srand(time(0)); for (int i=0; i<SIZE; i++) { // заповнення масиву числами <100 array[i] = rand()%100; }}// виведення масиву на екранvoid ShowArray(){ for (int i=0; i<SIZE; i++) { cout << array[i] << " "; } cout << endl;}int main(){ int temp, start = 0, min_position, min_element; GenerationArray(); ShowArray(); // сортування вибором while (start!= SIZE-1) { // припустимо, що елемент з індексом лівої межі мінімальний min_element = array[start]; // запам'ятовуємо індекс цього елемента min_position = start; // шукаємо мінімальний елемент у підмасиві for (int i=start; i<SIZE; i++) { if (array[i] < min_element) { min_element = array[i]; min_position = i; } } // якщо елемент з індексом лівої межі не мінімальний, // міняємо його місцями з знайденим мінімальним числом if (min_position!= start) { temp = array[start]; array[start] = array[min_position]; array[min_position] = temp; } start++; } ShowArray(); return 0;}

Час сортування 100 тисяч елементів сортуванням бульбашкою склав 1 хвилину 38.731 секунд, у той час як алгоритм сортування вибором виконав це завдання за 28.313 секунд. Але все одно обидва алгоритми не підходять для сортування великих масивів чисел. При збільшенні числа елементів у 10 разів, кількість циклів буде зростати в 100(!) разів. Для таких обсягів чисел існують інші алгоритми сортування, про які ми дізнаємося у наступній серії нашої передачі;)