Машина Тюрінга
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ється місцями з третім.
Цей метод сортування, званий простим вибором, в деякому розумінні протилежний до методу простих включень; при сортуванні простими включеннями на кожному кроці розглядається тільки один черговий елемент вхідної підпослідовності і усі елементи готового масиву для знаходження місця включення; при сортуванні простим вибором розглядаються усі елементи вхідного масиву для знаходження елементу з найменшим ключем, і цей один черговий елемент вирушає в готову підпослідовність.
Наступником методу простого вибору є - сортування модифікованим методом простого вибору.
Цей метод ґрунтується на алгоритмі пошуку мінімального елементу. У масиві А(1.n) відшукується мінімальний елемент, який ставиться на перше місце . Для того, щоб не втратити елемент, що стоїть на першому місці, цей елемент встановлюється на місце мінімального . Потім в такій же послідовності, виключаючи перший елемент, відшукується мінімальний елемент і ставиться на друге місце і так далі n - 1 раз доки не встане на своє місце передостанній n - 1 елемент масиву А, перемістивши максимальний елемент в самий кінець.
Розглянемо алгоритмічне рішення задачі на прикладі сортування деякого масиву значень за збільшенням. Відповідно до вищеописаного методу нам необхідно кілька разів виконувати операції пошуку мінімального елементу і його перестановку з іншим елементом, тобто потрібно буде кілька разів переглядати елементи масиву з цією метою. Кількість переглядів елементів масиву згідно з описом модифікованого методу простого вибору рівна n - 1, де n - кількість елементів масиву. Таким чином, можна зробити висновок, що проектований алгоритм сортування міститиме цикл, в якому виконуватиметься пошук мінімального елементу і його перестановка з іншим елементом. Позначимо через i - лічильник (номер) переглядів елементів масиву і зображує узагальнений алгоритм сортування на (сх. 1).
Відмітимо, що для перестановки елементів місцями необхідно знати їх порядкові номери, алгоритм перестановки елементів масиву був розглянутий раніше. Алгоритми введення початкового масиву і виведення цього ж масиву після сортування зображені на малюнках 16 і 24 відповідно. Алгоритм пошуку в масиві мінімального елементу і його номера буде аналогічний розглянутому алгоритму пошуку максимального елементу. Проте, в цьому алгоритмі будуть внесені зміни. Для того, щоб визначити які зміни слід внести розглянемо виконання сортування цим методом з акцентом на пошук мінімального елементу на конкретному прикладі. Нехай початковий масив містить 5 елементів (2,8,1,3,7). Кількість переглядів згідно з модифікованим методом простого вибору дорівнюватиме 4. Покажемо в таблиці 1, як змінюватиметься початковий масив на кожному перегляді.
Таблиця 1.
Номер перегляданню масиву іЗавдань масивМінімальний елементПереставлюваний елементМасив після перестановкиНомерЗначенняНомерЗначення1(2,8,1,3,7)3112(1,8,2,3,7)21,(8,2,3,7)32281,(2,8,3,7)31,2,(8,3,7)43381,2,(3,8,7)41,2,3,(8,7)57481,2,3,7,8
З даних, приведених в таблиці 1, випливає, що пошук мінімального значення в масиві на кожному перегляді здійснюється в скороченому масиві, який спочатку починається з першого елементу, а на останньому перегляді масив, в якому шукається мінімальний елемент починається вже з четвертого (чи n - 1) елементу. При цьому можна помітити, що номер першого елементу масиву для кожного пошуку і перестановки співпадає з номером перегляду i.
Введемо наступні позначення:
К- номер мінімального елементу- номер елементу масиву
М і А(К) - одне і теж значення мінімального елементу масиву- номер що переставляється з мінімальним елементу
А(i) - значення елементу, що переставляється.
Тоді циклічний алгоритм сортування модифікованим методом простого вибору виглядатиме таким чином (сх.2).
Словесний опис алгоритму
.У вхідній підпослідовності елементів вибирається елемент з найменшим ключем.
. Цей елемент міняється місцями з першим елементом a1.
Ці операції потім повторюються з n, що залишилися, - 1 елементами, потім з n - 2 елементами, поки не залишиться тільки один елемент - найбільший.
Структура даних
[]n - масив даних з n елементів- кількість елементів,j - індекси елементів масиву- змінна, що зберігає значення елемента який обмінюють місцями[i] - i-тий елемент масиву[j] - j-тий елемент масиву- обмін елементів місцями
Опис схеми алгоритму
.Масив даних A[]n подається на вхід, після чого входить в цикл по змінні
і(n-1),0 .
.Функцією цього циклу є прохід по всіх значеннях масиву, окрім останнього(n-1).
.Після проходження першого значення циклу по і, цикл по j(n),i+1 проходить всі інші значення які стоять після першого значення, порівнюючи ці значення із першим.
. Якщо знаходиться найближчий елемент A[i]>A[j], який більший за перший, то тоді повертаємось до циклу по j, якщо ж ні, то елементи обмінюємо місцями. 5. Данy послідовність дій потібно проробити для всих елементів.
.Після проходження циклів, вони завершають свою роботу.
.Новоутворений масив данихA[] виводиться на екран .
Опис процедури Obmin
. Змінній k значення першого елемента k=A[i]
. На місце першого записується знайдений менший елементA[i]=A[j].
. На місце знайденого меншого елемента записується перший елемент A[j]=k. Таким чином елементи обмінюються .
Покроковий опис схеми алгоритмів
мал.1 Опис основної схеми
Блок №1
Ввод масиву А, який містить n елементів.
Блок №2
Цикл по і, починається із 0, триває до n-1.
Бло