3. Квадратичні алгоритми сортування
Перелік алгоритмів сортування, що розглядаються
- прямого вибору;
- "бульбашки";
- шейкерне сортування.
Короткі теоретичні відомості
Питання для повторення
- Передача параметрів функцій.
- Пошук мінімального (максимального) елемента масиву.
Постановка задачі
Задано масив записів, одне поле яких виконує роль ключа. Необхідно знайти таку перестановку записів, після якої ключі розташувалися б у порядку неспадання.
Опис алгоритмів
Розглядається упорядкування масива a цілих чисел, занумерованих від 0 до N-1.
1.Сортування прямим вибором
Ідея
Знайти мінімальний елемент масиву і обміняти його місцями з нульовим елементом. Повторити процес для частин масиву, починаючи з 2, 3, ..., n-1 елемента.
Псевдокод
для і від 0 до N-2
{
k=i
для j від i+1 до N–1
{
якщо a[j]<x
то k=j
}
переставити (a[i], a[k])
}
{
k=i
для j від i+1 до N–1
{
якщо a[j]<x
то k=j
}
переставити (a[i], a[k])
}
2. "Бульбашкове" сортування
Ідея
Переглянути елементи масиву, обмінюючи у разі потреби сусідні елементи. У результаті найменший або найбільший (залежно від напрямку перегляду) елемент опиниться на своєму місці. Повторити процес, доки всі елементи не будуть упорядковані (таких повторень буде N-1).Псевдокод
для і від 1 до N-1
{
для і від N-1 до i
{
якщо a[j-1]>a[j]
то переставити (a[j], a[j-1])
}
}
{
для і від N-1 до i
{
якщо a[j-1]>a[j]
то переставити (a[j], a[j-1])
}
}
3. Шейкерне сортування
Ідея
Шейкерне сорутвання є покращенням "бульбашкового", яке досягається на основі таких ідей:
- запам’ятовувати позицію останнього обміну, тоді перегляди можна завершувати на цьому індексі, а не йти до зарані визначеної межі;
- чергувати напрямок послідовних переглядів з метою уникнення своєрідної асиметрії.
Псевдокод
L = 1; R = N - 1; k = n
повторювати
{
для j від R до L
{
якщо a[j-1]>a[j]
то {переставити (a[j], a[j-1]); k = j}
}
L = k + 1
для j від L до R
{
якщо a[j-1]>a[j]
то {переставити (a[j], a[j-1]); k = j}
}
R = k- 1
}
повторювати
{
для j від R до L
{
якщо a[j-1]>a[j]
то {переставити (a[j], a[j-1]); k = j}
}
L = k + 1
для j від L до R
{
якщо a[j-1]>a[j]
то {переставити (a[j], a[j-1]); k = j}
}
R = k- 1
}
Завдання для виконання
Постановка задачі
Скласти програми, що реалізують різні алгоритми сортування масиву, і зберегти їх у власній папці. Програми повинні забезпечувати:- автоматичну генерацію масиву цілих чисел та виведення його на екран;
- сортування масиву за певним алгоритмом;
- підрахунок кількості порівнянь і обмінів у процесі впорядкування.
Технічні умови
- кількість елементів у масиві не перевищує 100;
- елементи масиву є невід'ємними цілими числами, що не перевищують 50.
Хід роботи
- Скласти функцію, яка переставляє місцями два елементи масиву із заданими номерами.
- Скласти програму Selection.cpp, що забезпечує сортування масиву методом прямого вибору.
- Скласти програму BubleSort.cpp, що забезпечує сортування масиву за алгоритмом "бульбашки".
- Змінити програму, забезпечивши реалізацію шейкерного сортування. Збережіть під назвою ShakerSort.cpp.
- Скласти таблицю виконання вказаного викладачем алгоритму сортування для масиву 6 чисел.
Запитання для самоконтролю
- У чому полягає задача сортування масиву? За якими критеріями оцінки часу порівнюють алгоритми сортування?
- Які методи сортування масивів відносять до квадратичних? Чому ці методи називають квадратичними?
- Поясніть основну ідею сортування масиву методом прямого вибору.
- Порівняйте алгоритми прямого вибору і "бульбашки".
- Які ідеї покладено в основу шейкерного сортування?