Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
|
Дисципліна |
Відділення |
Спеціальність |
Група |
|
Інформатика |
Радіотехнічне |
5.05090101 |
221-222 |
|
Викладач Аністратенко Т.В. |
|||
|
Лабораторна робота № 16 |
Тема: Реалізація алгоритмів сортування масивів.
Мета: отримати практичні навички складання та відладки програм сортування масивів
Обладнання: Borland C++
Теоретичні відомості
Сортування обміном або сортування бульбашкою є простим алгоритмом сортування. Алгоритм працює таким чином — у поданому наборі даних (списку чи масиві) порівнюються два сусідні елементи. Якщо один з елементів, не відповідає критерію сортування (є більшим, або ж, навпаки, меншим за свого сусіда), то ці два елементи міняються місцями. Прохід по списку продовжується до тих пір, доки дані не будуть відсортованими. Алгоритм отримав свою назву від того, що процес сортування за ним нагадує поведінку бульбашок повітря у резервуарі з водою. Оскільки для роботи з елементами масиву він використовує лише порівняння, це сортування на основі порівнянь.
Позиція елементів, що підлягають сортуванню відіграє велику роль у питанні продуктивності даного алгоритму. Великі елементи на початку списку не являють проблеми, оскільки вони досить швидко зміщуються на свої місця. Однак, малі елементи у кінці списку переміщуються на його початок дуже повільно. Це призвело до того, що обидва типи елементів було названо кролями і черепахами, відповідно.
З метою підвищення швидкодії алгоритму, у свій час було здійснено чимало зусиль для зменшення кількості "черепах". Сортування перемішуванням є порівняно не поганим, однак, усе ще у своєму найгіршому випадку має складність O(n2). Сортування гребінцем спершу порівнює великі елементи один з одним, а вже тоді поступово переходить до все менших і менших. Його середньостатистична швидкість приблизно рівна такій в алгоритмі Швидке сортування.
Візьмемо масив чисел "5 1 4 2 8", і за допомогою даного алгоритму, відсортуємо його від найменшого до найбільшого елементу. На кожному кроці, елементи, виділеніжирним шрифтом будуть порівнюватись.
Перший прохід:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ) Тут, алгоритм порівнює перші два елементи, і міняє їх місцями.
( 1 5 4 2 8 ) ( 1 4 5 2 8 )
( 1 4 5 2 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 4 2 5 8 ) Тут порівнювані елементи знаходяться на своїх місцях, тож алгоритм не міняє їх місцями.
Другий прохід:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Тепер наш масив повністю відсортований, однак, алгоритм цього ще не знає. Йому потрібен ще один "пустий" прохід, під час якого він не поміняє місцями жодного елементу.
Третій прохід:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Нарешті, масив відсортовано, і алгоритм може припинити свою роботу.
Сортування вибором — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритмсортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю.
Алгоритм працює таким чином:
Фактично, таким чином ми поділили список на дві частини: перша (ліва) — повністю відсортована, а друга (права) — ні.
Ось приклад сортування масиву з п'яти елементів за даним алгоритмом:
64 25 12 22 11
11 25 12 22 64
11 12 25 22 64
11 12 22 25 64
Реалізація алгоритма
#include <algorithm> // for: std::iter_swap, std::min_element
template <typename Iterator>
void selection_sort(Iterator begin, Iterator end)
{
Iterator min;
while (begin != end)
{
min = std::min_element(begin, end);
std::iter_swap(begin, min);
++begin;
}
}
Завдання для підготовки до іспиту
Звіт повинен містити:
тему, мету, обладнання, текст програми та результати виконання, відповіді на контрольні запитання (хід роботи не друкуємо!!!).
Контрольні запитання.
1. Які методи сортування масивів ви знаєте?
2. Зобразіть схематично методи сортування простим обміном та включенням.