Практична робота №9 Тема: Складання алгоритму сортування методом вибору.

МетаОзнайомитися з методами сортування елементів масиву (списку).

Теоретичні відомості

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

Алгоритм сортування виборомприведений у вигляді блок-схеми на мал. 1. Знайдемо в масиві найбільший елемент (блоки 3-7) і поміняємо його місцями з останнім елементом (блок 8). Повторюваний алгоритм пошуку максимального елементу, зменшивши кількість елементів, що проглядаються, на одиницю (блок 9), і поміняємо його місцями з передостаннім елементом (блоки 3-7). Описану вище операцію пошуку проводимо до повного впорядковування елементів в масиві. Оскільки в блоці 9 відбувається зміна змінній n, то на початку алгоритму її значення необхідно зберегти (блок 1).

Для впорядковування масиву по убуванню необхідно переміщати мінімальний елемент.

Рис. 1. Сортування масиву вибором найбільшого елементу

Хід роботи

Скласти алгоритм впорядкування елементів одновимірного масиву із n елементів, котрі вводяться користувачем, за зростанням за допомогою методу вибору максимального елемента.

Контрольні запитання.

1. Які методи сортування елементів масиву ви можете назвати?

2. Назвіть переваги і недоліки сортування методом вибору.

Практична робота №10 Тема: Складання алгоритму порозрядного сортування.

МетаОзнайомитися з методами сортування елементів масиву (списку).

Теоретичні відомості

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

Перш ніж приступити до складання блок-схеми розглянемо наступний приклад|. Хай відомо, що в масиві з восьми елементів перші шість вже впорядковані, а сьомий елемент потрібно вставити між другим і четвертим. Збережемо сьомий елемент в допоміжній змінній, так як показано на малюнку 1, а на його місце запишемо шостий. Далі п'ятий перемістимий на місце шостого, четвертий на місце п'ятого, а третій на місце четвертого, тим самим, виконавши зсув елементів масиву на одну позицію вправо. Записавши вміст допоміжної змінної в третю позицію, досягнемо потрібного результату.

Рис. 1. Процес вставки елементу в масив

Складемо блок-схему алгоритму, враховуючи, що можливо описані вище дії доведеться виконати неодноразово.

Організовуємо цикл для проглядання всіх елементів масиву, починаючи з другого (блок 4). Збережемо значення поточного i-го елементу в допоміжній змінній X, оскільки воно може бути втрачене при зрушенні елементів (блок 5) і привласнимо змінною j значенняіндексу попереднього (i-1)-гоелементу масиву (блок 6). Далі рухаємося по масиву вліво у пошуках елементу меншого, ніж поточний і поки він не знайдений зрушуємо елементи управо на одну позицію. Для цього організовуємо цикл (блок 7), який припинитися, як тільки буде знайдений елемент менше поточного. Якщо такого елементу в масиві не знайдеться і змінна j станерівною нулю, то це означатиме, що досягнута ліва межа масиву, і поточний елемент необхідно встановити в першу позицію. Зсув елементів масиву управо на одну позицію виконується в блоці 8, а зміна лічильника j вблоці 9. Блок 10 виконує вставку поточного елементу у відповідну позицію.

Рис. 2. Сортування масиву вставкою

Хід роботи

Скласти алгоритм впорядкування елементів одновимірного масиву із n елементів, котрі вводяться користувачем, за зростанням за допомогою методу вставки.

Контрольні запитання.

1. Які методи сортування елементів масиву ви можете назвати?

2. Назвіть переваги і недоліки сортування методом вставки.

Список літератури

1. Голощук Р.О. та ін. Алгоритми і структури даних. Л.: "Магнолія", 2010

2. Катренко А.В. Дослідження операцій. Л.: "Магнолія", 2010

3. Кузнецов Ю.Н. и др. Математическое программирование. М.: Высшая школа, 2001

4. Симонович С.В. Информатика. Учебник для ВУЗов. СПб.: Питер, 2005

5. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение (пер. с англ.). М.: Мир, 2001.

6. Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989.

7. Пискунов Н. С. Дифференциальное и интегральное исчисления для вузов.

Зміст