Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи сортування. Алгоритм бульбашки.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Методичні вказівки
Предмет:
Алгоритми і структури даних
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти України
Національний університет "Львівська політехніка"
М Е Т О Д И Ч Н А В К А З І В К А
До лабораторної роботи № 2
На тему: “ Методи сортування. Алгоритм бульбашки.”
з дисципліни
" Алгоритми і структури даних"
Для базового напрямку 6.0804 "Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2007 р.
Львів – 2007
Методичні вказівки до лабораторних робіти з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки"
Укладач: Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Ознайомлення із методами сортування. Алгоритм бульбашки.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із Бульбашковим методом сортування. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема метод бульбашки.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Розташуємо масив зверху вниз, від нульового елементу - до останнього.
Ідея методу: крок сортування полягає в проході від низу до верху по масиву. По дорозі є видимими пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями.
Після нульового проходу по масиву "вгорі" виявляється "найлегший" елемент - звідси аналогія з бульбашкою. Наступний прохід робиться до другого зверху елементу, таким чином другий за величиною елемент піднімається на правильну позицію...
Робимо проходи по нижній частині масиву, що все зменшується, до тих пір, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, оскільки послідовність впорядкована за збільшенням.
template<class T>
void bubbleSort(T a[], long size){
long i, j;
T x;
for( i=0; i < size; i++){ // i - номер проходу
for( j = size-1; j > i; j-- ){ // внутрішній цикл проходу
if ( а[j-1]> а[j]) {
x=a[j-1]; а[j-1]=a[j]; а[j]=x;
}
}
}
}
Середнє число порівнянь і обмінів мають квадратичний порядок зростання: Theta(n2), звідси і слідує, що алгоритм бульбашки дуже повільний і малоефективний.
Проте, у нього є величезний плюс: він простий і його можна по-всякому покращувати. Чим ми зараз і займемося.
По-перше, розглянемо ситуацію, коли на якому-небудь з проходів не відбулося жодного обміну. Що це означає ?
Це означає, що всі пари розташовані в правильному порядку, так що масив вже відсортований. І продовжувати процес не має сенсу(особливо, якщо масив був відсортований із самого початку !).
Отже, перше поліпшення алгоритму полягає в запам'ятовуванні, чи проводився на даному проході який-небудь обмін. Якщо немає - алгоритм закінчує роботу.
Процес поліпшення можна продовжити, якщо запам'ятовувати не тільки сам факт обміну, але і індекс останнього обміну. Дійсно: всі пари сосідніх елементів з індексами, меншими до, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі до, замість того щоб рухатися до встановленої заздалегідь верхньої межі i.
Інше покращення алгоритму можна отримати з наступного спостереження. Хоча легка бульбашка знизу підніметься вгору за один прохід, важкі бульбашки опускаються з мінімальною швидкістю: один крок за ітерацію. Отже масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 вимагає 5 проходів.
Щоб уникнути подібного ефекту, можна міняти напрям наступних один за іншим проходів. Алгоритм, що вийшов, іноді називають "шейкер-сортування".
template<class T>
void shakerSort(T a[], long size){
long j, до = size-1;
long lb=1, ub = size-1; // межі невідсортованої частини масиву
T x;
do {
// прохід від низу до верху
for( j=ub; j>0; j-- ){
if ( а[j-1]> а[j]) {
x=a[j-1]; а[j-1]=a[j]; а[j]=x;
k=j;
}
}
lb = k+1;
// прохід зверху вниз
for (j=1; j<=ub; j++) {
if ( а[j-1]> а[j]) {
x=a[j-1]; а[j-1]=a[j]; а[j]=x;
k=j;
}
}
ub = k-1;
} while ( lb < ub );
}
Наскільки описані зміни вплинули на ефективність методу ? Середня кількість порівнянь, хоч і зменшилося, але залишається O(n2), тоді як число обмінів не помінялося взагалі ніяк. Середня(воно ж гірше) кількість операцій залишається квадратичною.
Додаткова пам'ять, очевидно, не потрібна. Поведінка вдосконаленого (але не початкового) методу задоволена природне, майже відсортований масив буде відсортований набагато швидше випадкового. Сортування бульбашкою стійке, проте шейкер-сортування втрачає цю якість.
На практиці метод бульбашки, навіть з поліпшеннями, працює, на жаль, дуже поволі. А тому - майже не застосовується.
2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ
При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм вибірки.
Використовувати мову програмування C/C++.
Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи.
3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ
Отримати індивідуальне завдання у викладача;
Уточнити завдання(можливі різні трактування завдання);
Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу(алгоритму) на даній лабораторній роботі;
Протестувати на наявність логічних помилок програми;
Оформити звіт відповідно до стандарту;
Захистити виконану роботу.
4. КОНТРОЛЬНІ ПИТАННЯ
Які ви знаєте методи сортування?
Який метод сортування був розглянений на даній лабораторній роботі?
Від чого прямо – залежним являється швидкість сортування?
Опишіть характеристики даного методу.
Порівняєте даний метод із іншими методами сортування вам відомими.
Наскільки являється ефективним даний метод сортування?
Чи використовують даний метод на практиці, і наскільки часто?
Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах?
Чим оригінальним виділяється даний метод від інших?
5. ІНДИВІДУАЛЬНЕ ЗАВДАНЯ
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора