Задача 1. Методи сортування
Завдання:
Скласти програму, що реалізовує зазначений вид сортування для масиву елементів розмірності N (N? 50) зазначеного типу сформованого випадковим чином. Звіт повинен містити коротке пояснення алгоритму сортування, лістинг програми та результати роботи програми. Для варіанта № 10: сортування масиву цілих чисел алгоритмом лінійна вставка. p align="justify"> Рішення:
Пояснення алгоритму сортування В«лінійна вставкаВ».
Сортування лінійної вставкою - найпростіший алгоритм, що реалізує ручне сортування карт при грі в Брідж. Переглядаючи масив з одного кінця до іншого, кожен елемент масиву ставиться в правильну позицію по відношенню до вже відсортованим елементам. p align="justify"> Ця сортування працює зі списком невпорядкованих позитивних цілих чисел, сортуючи їх у порядку зростання. p align="justify"> Опис алгоритму:
Сортувати вектор A довжиною N
Нач
Для i від 2 до N Цикл
X: = A [i];: = i-1;
Поки (j Ві 1) і (A [j]> X) Цикл [j +1] : = A [j]; {зрушення елементів}: = j - 1;
КЦікл [j +1]: = X; {вставка елемента на своє місце}
КЦікл
Кон
На кожній ітерації перше число НЕ відсортованого списку видаляється з нього і поміщається на відповідне йому місце в відсортованому списку. Для цього відсортований список, проглядається, починаючи з найменшого числа до тих пір, поки не знаходять відповідне місце для нового числа, тобто поки всі числа з меншими значеннями не опиняться попереду нього, а всі числа з великими значеннями - після нього.
Покажемо роботу алгоритму на прикладі:
412 71 81 59 14 273 87
Ітерація 0:
несортовані: 412 71 81 59 14 273 87
Відсортований: 27
Ітерація 1:
несортовані: 412 71 81 59 14 273 87
Відсортований: 27412
Ітерація 2:
несортовані: 71 81 59 14 273 87
Відсортований: 2771 412
Ітерація 3:
несортовані: 81 59 14 273 87
Відсортований: 2771 81 412
Ітерація 4:
несортовані: 59 14 273 87
Відсортований: 2759 71 81 412
Ітерація 5:
несортовані: 14273 87
Відсортований: 14 27 59 71 81 412
Ітерація 6:
несортовані: 273 87
Відсортований:...
