Сортування вставкою

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

Ідея алгоритму наступна.

Шукається номер максимального елемента масиву. На його місце поміщається останній елемент масиву. А на місце останнього елемента ставиться максимальний елемент (елементи міняються місцями). Потім береться частина масиву без останнього елемента. (Останнє місце вже остаточно зайняв максимальний елемент.) З цим залишком робиться те ж саме, що і з вихідним масивом, доки довжина останнього залишку не стане рівній одиниці.

Алгоритм представлений наступним програмним кодом.

Код 3.9

Даний код — це визначення процедури, що не є рекурсивною, але використовує визначену вище (див. код 3.8) рекурсивну функцію ІдексМаксЕеменma.

Цей алгоритм має яскраво виражений рекурсивний характер. Ідея алгоритму така.

Відокремимо від масиву останній елемент. За допомогою цього ж алгоритму (рекурсивно) відсортуємо скорочений масив (без останнього елемента). У відсортований масив вставимо відділений спочатку останній елемент. Умовою закінчення рекурсії є те, що останній скорочений масив буде містити всього один елемент.

Найважчим в цьому алгоритмі є вставка елемента у відсортований масив. Робиться це так. Масив послідовно проглядається до тих пір, поки не буде виявлене місце, куди треба вставити цей елемент. Потім всі елементи масиву, що знаходяться після цього місця, переміщаються на одну позицію вправо, а елемент, що вставляється, займає звільнене місце.

Програму даного алгоритму зручно представити у вигляді двох загальних процедур: СортуванняВставкою і Вставка (коди 3.10 і 3.11):

Код 3.10

Код 3.11

Hові поняття:

Дата добавления: 2014-12-23