Інформатика – Поглиблений рівень

Пригадаємо!

Відсортуйте масив чисел методом обімну: 8, 23, 7, 11, 9, 2, 42,15.

Відсортуйте масив чисел методом вибору: 67, 87, 24, 34, 55, 11, 2, 99.

Прочитайте!

Як у впорядкований одновимірний масив чисел можна вставити нове число, не порушуючи впорядкування масиву?

Метод сортування вставленням використовується для впорядкованих масивів. Розглянемо сутність алгоритму сортування вставленням на прикладі.

Сортування вставками швидке і просте. На кожній ітерації програма бере один з елементів і підшукує для нього місце у вже відсортованому списку. Так відбувається до тих пір, поки не залишиться жодного невикористаного елемента.

На рис. 6.3 наведено програму, яка реалізує вставлення нового елемента в початковий масив.

Зверніть увагу, що в програмі використано початковий масив [3, 5, 6, 8, 9, 12], хоча оголошено масив [3, 5, 6, 8, 9, 12, 99]. Довжина оголошеного масиву збільшена на одиницю, й останній елемент містить число 99. Це обумовлено тим, що після вставлення масив за довжиною буде більшим на одиницю, чим забезпечується правильна індексація елементів масиву.
Результат виконання програми:

Самостійне виконання вправ

Завдання 1. Проаналізуйте порядок виконання програми сортування масиву методом вставлення (рис. 6.3) на прикладі вставлення числа 13 у масив [7, 10, 15, 21, 29, 39].