p align="justify"> (1 2 4 5 8) (1 2 4 5 8)
Тепер масив повністю відсортований, але алгоритм не знає чи це так. Тому йому необхідно зробити повний прохід і визначити, що перестановок елементів не було. p align="justify"> Третій прохід:
(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) Тепер масив відсортований і алгоритм може бути завершений.
void protalkivanie (int * & kop, int razmer) - функція сортуюча масив методом вибору.
Ідея методу полягає в тому, щоб створювати відсортовану послідовність шляхом приєднання до неї одного елемента одним в правильному порядку. p align="justify"> Будемо будувати готову послідовність, починаючи з лівого кінця масиву. Алгоритм складається з n послідовних кроків, починаючи від нульового і закінчуючи (n-1)-му. p align="justify"> На i-му кроці вибираємо найменший з елементів a [i] ... a [n] і міняємо його місцями з a [i]. Послідовність кроків при n = 5 зображена на малюнку нижче. br/>В
Незалежно від номера поточного кроку i, послідовність a [0] ... a [i] (виділена курсивом) є впорядкованою. Таким чином, на (n-1)-му кроці вся послідовність, крім a [n] виявляється відсортованій, а a [n] стоїть на останньому місці по праву: все менші елементи вже пішли вліво. p align="justify"> void vstavka (int * & kop, int razmer) - функція сортуюча масив методом вставки.
Сортування простими вставками в чомусь схожа на вищевикладені методи.
Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином на його початку "виростає" відсортована послідовність.
Однак у сортуванні бульбашкою або вибором можна було чітко заявити, що на i-му кроці елементи a [0] ... a [i] стоять на правильних місцях і нікуди паче не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a [0] ... a [i] впорядкована. При цьому по ходу алгоритму в неї будуть вставлятися (див. назва методу) все нові елементи. p align="justify"> Будемо розбирати алгоритм, розглядаючи його дії на i-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a [0] ... a [i] і невпорядковану a [i +1] ... a [n]. p align="justify"> На наступному, (i +1)-м кожному кроці алгоритму беремо a [i +1] і вставляємо на потрібне місце в готову частину масиву. p align="justify"> Пошук відповідного місця для чергового елемента вхідної послідовності здійснюється шляхом послідовних порівнянь з елементом, що стоять перед ним.
Залежно від результату порівняння елемент або залишається на поточному місці (вставка завершена), або вони міняються місцями і процес повторюється.
В
Таким чином, в процесі вставки ми "просіюємо" елемент x до початку масиву, зу...
