Порівняння загальних характеристик роботи різних методів сортування - Курсовая работа

СОРТУВАННЯ МЕТОДОМ БУЛЬБАШКИ, СОРТУВАННЯ МЕТОДОМ ШЕЛЛА, ШВИДКЕ СОРТУВАННЯ, СОРТУВАННЯ ВСТАВКАМИ, СОРТУВАННЯ ВИБОРОМ, СОРТУВАННЯ МЕТОДОМ ЗНАХОДЖЕННЯ МІНІМАЛЬНОГО ЕЛЕМЕНТААле для того, щоб вирішити поставлену задачу, необхідно вказати послідовність дій, виконання яких приведе до необхідного результату, - скласти програму. На даний час однієї з найпоширеніших його версій є Microsoft Visual C , і середовище програмування Visual studio.Середовище програмування Visual studio дозволяє створювати тексти програм, компілювати їх, знаходити помилки і оперативно їх виправляти; компонувати програми з окремих частин, включаючи стандартні модулі, налагоджувати і виконувати налагоджену програму.Для вирішення багатьох завдань зручно спочатку упорядкувати дані за певною ознакою, так можна прискорити пошук деякого обєкту. Перегруповування заданої множини обєктів в певному порядку називають сортуванням. "Навіть якщо б сортування була майже марна, знайшлася б маса причин зайнятися нею! Сортування і пошук належать до числа найбільш поширених і добре вивчених задач. Алгоритми сортування класифікують на алгоритми сортування обєктів з довільним доступом (масиви і дискові файли довільного доступу) та алгоритми сортувальні послідовні обєкти (файли на стрічках і дисках).Ідея методу: крок сортування полягає в проході знизу вгору по масиву. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями (Рис. Після нульового проходу по масиву "вгорі" виявляється самий "легкий" елемент - звідси аналогія з бульбашкою (Рис. Наступний прохід робиться до другого зверху елемента, таким чином другий за величиною елемент піднімається на правильну позицію. Робимо проходи по все зменшується нижній частині масиву до тих пір, поки в ній не залишиться тільки один елемент.Спочатку сортуємо простими вставками кожні 8 груп з 2-х елементів (a [0], a [8 [), (a [1], a [9]), ... Потім сортуємо кожну з чотирьох груп по 4 елемента (a [0], a [4], a [8], a [12]), ..., (a [3], a [7], a [11] , a [15]) (Рис. В нульової групи будуть елементи 4, 12, 13, 18, в першій - 3, 5, 8, 9 тощо. Далі сортуємо 2 групи по 8 елементів, починаючи з (a [0], a [2], a [4], a [6], a [8], a [10], a [12], a [14] ) (Рис. В кінці сортуємо вставками всі 16 елементів (Рис.Опис алгоритму: 1. вибрати елемент, званий опорним. 2. порівняти всі інші елементи з опорним, на підставі порівняння розбити безліч на три - «менші опорного», «рівні» та «великі», розташувати їх у порядку менші-рівні-великі. Вибираємо в масиві деякий елемент, який будемо називати опорним елементом. Відомі стратегії: вибирати постійно один і той же елемент, наприклад, середній або останній по положенню; вибирати елемент з випадково вибраним індексом. Операція поділу масиву: реорганізуємо масив таким чином, щоб всі елементи, менші або рівні опорному елементу, виявилися зліва від нього, а всі елементи, великі опорного - праворуч від нього.Ідея методу полягає в тому, щоб створювати відсортовану послідовність шляхом приєднання до неї одного елемента за іншим у правильному порядку. Будемо будувати готову послідовність, починаючи з лівого кінця масиву. Алгоритм складається з n послідовних кроків, починаючи від нульового і закінчуючи (n-1)-му. На i-му кроці вибираємо найменший з елементів a [i] ... a [n] і міняємо його місцями з a [i]. Таким чином, на (n-1)-му кроці вся послідовність, крім a [n] виявляється відсортованої, а a [n] стоїть на останньому місці по праву: все менші елементи вже пішли вліво.Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином на його початку "виростає" відсортована послідовність. Однак у сортуванні бульбашкою або вибором можна було чітко заявити, що на i-му кроці елементи a [0] ... a [i] стоять на правильних місцях і нікуди більше не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a [0] ... a [i] впорядкована. В залежності від результату порівняння елемент або залишається на поточному місці (вставка завершена), або вони міняються місцями і процес повторюється (Рис. Таким чином, в процесі вставки ми "просіваємо" елемент x до початку масиву, зупиняючись у випадку, коли знайдено елемент, менший x або досягнуто початок послідовності.У 1959 році Д.Л.Шелл запропонував замість систематичного включення елемента з індексом i в підмасив попередніх йому елементів (цей спосіб суперечить принципу "балансування", чому і не дозволяє отримати ефективний алгоритм) включати цей елемент в підсписок, що містить елементи з індексами ih, i-2h, i-3h і т.д., де h - деяка натуральна постійна. Таким чином формується масив, в якому h-серії елементів, віддалених один від одного на відстань h, сортуються окремо: Після того, як розсортовані непересічні h-серії, процес поновлюється з новим значенням h "<h. Вибирати опорним елементом середній з трьох (першого, середнього і останнього елементів).

Зміст

Вступ

1. Відомості про методи сортування

2. Алгоритми

2.1 Сортування методом бульбашки

2.2 Сортування методом Шелла

2.3 Швидке сортування

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

2.5 Сортування вставками

3. Інструкція користувача програми

3.1 Сортування методом бульбашки

Висновки

Перелік використаних джерел

Додаток А Додаток Б