Вивчення принципів к упорядкування даних за певною ознакою. Дослідження умов сортування. З’ясування сутності його видів: методів бульбашки та Шелла, швидкого, вибором і вставками. Розгляд алгоритмів, створення програм мовою Microsoft Visual C .
Аннотация к работе
Але для того, щоб вирішити поставлену задачу, необхідно вказати послідовність дій, виконання яких приведе до необхідного результату, - скласти програму. Для зручності роботи з ЕОМ ця операція проводиться за допомогою мов програмування (високого або низького рівня).Для вирішення багатьох завдань зручно спочатку упорядкувати дані за певною ознакою, так можна прискорити пошук деякого обєкту. Наприклад, в преферансі гравці розкладають карти по мастям і за значенням. Перегруповування заданої множини обєктів в певному порядку називають сортуванням.Ідея методу: крок сортування полягає в проході знизу вгору по масиву. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями (Рис. Після нульового проходу по масиву "вгорі" виявляється самий "легкий" елемент - звідси аналогія з бульбашкою (Рис. Наступний прохід робиться до другого зверху елемента, таким чином другий за величиною елемент піднімається на правильну позицію. Робимо проходи по все зменшується нижній частині масиву до тих пір, поки в ній не залишиться тільки один елемент.Розглянемо наступний алгоритм сортування масиву a [0] .. a [15] (Рис. Спочатку сортуємо простими вставками кожні 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]) (Рис. Далі сортуємо 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 або досягнуто початок послідовності.Шелл запропонував замість систематичного включення елемента з індексом i в підмасив попередніх йому елементів (цей спосіб суперечить принципу "балансування", чому і не дозволяє отримати ефективний алгоритм) включати цей елемент в підсписок, що містить елементи з індексами ih, i-2h, i-3h і т.д., де h - деяка натуральна постійна. Таким чином формується масив, в якому h-серії елементів, віддалених один від одного на відстань h, сортуються окремо: Після того, як розсортовані непересічні h-серії, процес поновлюється з новим значенням h "<h. Вибирати опорним елементом середній з трьох (першого, середнього і останнього елементів). Щоб уникнути досягнення небезпечної глибини рекурсії в гіршому випадку (або при наближенні до нього) можлива модифікація алгоритму, що усуває одну гілку рекурсії: замість того, щоб після поділу масиву викликати рекурсивну процедуру поділу для обох знайдених підмасива, рекурсивний виклик робиться тільки для меншого підмасива, а більший обробляється в циклі в межах цього ж виклику процедури. Існує ефективна модифікація (алгоритм Седжвіка) для сортування рядків - спочатку порівняння з опорним елементом тільки за нульовим символу рядка, далі застосування аналогічної сортування для «більшого» і «меншого» масивів теж за нульовим символу, і для «рівного» масиву по вже першого символу .