Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Процедура сортування масиву методом виборуСтр 1 из 4Следующая ⇒
Факультет прикладної математики Кафедра специалізованих компьютерних систем
Курсова робота з дисципліни “ Структури даних та алгоритми ” тема “ Дослідження ефективності методів сортування на багатовимірних масивах ”
Технічне завдання 1. Описати принцип роботи кожного з методів, що досліджуються, для одновимірного випадку. 2. Скласти алгоритми сортування в багатовимірному масиві методами, що задані за варіантом. . Провести практичні дослідження швидкодії складених алгоритмів. . За результатами досліджень скласти порівняльні таблиці за різноманітними ознаками. 5. Зробити висновки про порівняння отриманих результатів. P.S. При бажанні, можна дослідити вплив геометричних розмірів масиву на швидкість сортування, тобто не змінюючи загальної кількості елементів змінювати геометричні розміри масиву. Для випадку перестановки перерізів, не повинна змінюватись загальна кількість перерізів та загальна кількість елементів масиву, а іншими параметрами розмірності можна варіювати. Для випадку перестановки рядків/стовпців у кожному перерізі - не повинна змінюватись кількість рядків/стовпців у кожному перерізі та загальна кількість елементів масиву.
Задача Впорядкувати тривимірний масив A[m,n,p] наступним чином:переставити перерізи масиву (зміна другого індексу змінює номер перерізу) за не спаданням сум елементів перших рядків кожного перерізу. Методи 1. Вибір. 2. Вставка з лінійним пошуком місця вставки від взятого елемента («справа») без бар’єру. . Шейкерне сортування. Стан масиву Вихідний масив впорядкований, як задано за варіантом. Елементи вихідного масиву невпорядковані. Вихідний масив впорядкований протилежно, ніж задано за варіантом Опис теоретичних положень Сортування вибором Опис алгоритму: алгоритм сортування масиву за не спаданням методом вибору можна описати так: 1. Серед всіх елементів масиву, починаючи з першого, будь яким способом відшукується мінімальний елемент. 2. Знайдений мінімальний елемент поміщається на місце першого елементу. 3. Перевіряється масив від другого елементу, знаходиться мінімальний серед тих, що залишилися і поміщається на місце другого елементу.
4. І так далі до останнього елементу.
Малюнок 2.1 - Алгоритм сортування по не спаданню методом вибору.
Аналіз описаних вище дій при сортуванні вибором показує, що для програмної реалізації цього методу сортування буде потрібно два цикли for. У зовнішньому циклі повинен змінюватися номер змінного елементу від першого до передостаннього. Цей цикл визначатиме кількість проходів по масиву. Внутрішній цикл повинен забезпечити послідовне порівняння змінного елементу зі всіма елементами, які слідують в масиві за ним. У тілі внутрішнього циклу виробляється порівняння елементів. У тілі внутрішнього циклу виробляється порівняння елементів, індекси яких задаються параметрами зовнішнього і внутрішнього циклу. Якщо при порівнянні виявляється, що порядок дотримання елементів порушений, то порівнювані елементи міняються місцями. Схема алгоритму сортування масиву методом вибору показана на малюнку 2.1. Вихідними даними для алгоритму є: сортований масив mas і кількість елементів в цьому масиві count Процедура сортування масиву методом вибору procedure SortChoise (var a: TArray100; count: integer); var i, j, x: integer; begin i:= 1 to count - 1 do begin j:= i + 1 to count do if a[j] > a[i] then begin:= a[i];[i]:= a[j];[j]:= x; end;;; Begin // Порядок порушений, запамятовуємо i-й елемент x:= a[i]; // Починаємо цикл зрушень вправо на місце i-го елементу j:= i; // j - індекс вакантного місця Repeat // зрушуємо вправо a[j]:=a[j-1];:=j-1; // поки зліва не зявилось меньше число, // або дішли до початку масиву until (j = 1) or (a[j-1] <= x); //'Тепер вставим колишній i-й елемент на нове місцез індексом j a[j]:= x; end;;; Метод шейкерного сортування
Метод шейкерного сортування є удосконаленим методом сортування обміном із запам’ятовуванням місця останньої перестановки. Основна ідея методу полягає в тому, що послідовні проходи по масиву здійснюються з двох боків, і відсортованих частин у масиві є дві, причому вони з двох сторін «насуваються» на невпорядковану частину. Пари елементів послідовно порівнюються, та, якщо їх порядок розташування не відповідає певному критерію, елементи міняються місцями. Таким чином, найбільший елемент «спливає» у кінець масиву, а найменший - «тоне» у початок.
Метод шейкерного сортування за визначенням не зменшує кількість обмінів, але кількість порівнянь у нього є зазвичай меншою, аніж у методу обміну. Гарним прикладом переваги шейкерного методу над методом обміну може бути послідовність 2, 3, 4, 5, 1, яку необхідно впорядкувати за неспаданням. Методом шейкерного сортування достатньо 1-2 проходи (залежно від того, з якого боку починати), а методом обміну знадобилося б чотири проходи,якщо кожен раз починати прохід з початку масиву. Складність алгоритму O(n²), для найгіршого та середнього способу розташування, якщо масив майже відсортовано - прямує до O(n). Для сортування тривимірного масиву згідно із варіантом завдання алгоритм ускладнюється так само як і для методу обміну. Схематично (у вигляді блок-схеми) алгоритм шейкерного сортування зображено на Рис 2.3. Малюнок 2.3. Алгоритм шейкерного сортування (блок-схема) Час сортування
Час наведено у «тіках» процесору, він є відносним.
Масив 100х100х100 Табл. 4. 1 - Час сортування для масиву 100х100х100
Масив 100х500х500 Табл. 4.2 - Час сортування для масиву 100х500х500
Масив 100х500х500 Табл. 4. 3 - Кількість переміщень елементів для масиву 100х500х500
Масив 100х250х1000 Табл. 4.4 - Час сортування для масиву 100х250х1000
Масив 100х500х2000 Табл. 4.5 - Час сортування для масиву 100х1000х250
4. Факультет прикладної математики Кафедра специалізованих компьютерних систем
Курсова робота з дисципліни “ Структури даних та алгоритми ” тема “ Дослідження ефективності методів сортування на багатовимірних масивах ”
Технічне завдання 1. Описати принцип роботи кожного з методів, що досліджуються, для одновимірного випадку. 2. Скласти алгоритми сортування в багатовимірному масиві методами, що задані за варіантом. . Провести практичні дослідження швидкодії складених алгоритмів. . За результатами досліджень скласти порівняльні таблиці за різноманітними ознаками. 5. Зробити висновки про порівняння отриманих результатів. P.S. При бажанні, можна дослідити вплив геометричних розмірів масиву на швидкість сортування, тобто не змінюючи загальної кількості елементів змінювати геометричні розміри масиву. Для випадку перестановки перерізів, не повинна змінюватись загальна кількість перерізів та загальна кількість елементів масиву, а іншими параметрами розмірності можна варіювати. Для випадку перестановки рядків/стовпців у кожному перерізі - не повинна змінюватись кількість рядків/стовпців у кожному перерізі та загальна кількість елементів масиву.
Задача Впорядкувати тривимірний масив A[m,n,p] наступним чином:переставити перерізи масиву (зміна другого індексу змінює номер перерізу) за не спаданням сум елементів перших рядків кожного перерізу. Методи 1. Вибір. 2. Вставка з лінійним пошуком місця вставки від взятого елемента («справа») без бар’єру. . Шейкерне сортування. Стан масиву Вихідний масив впорядкований, як задано за варіантом. Елементи вихідного масиву невпорядковані. Вихідний масив впорядкований протилежно, ніж задано за варіантом Опис теоретичних положень Сортування вибором Опис алгоритму: алгоритм сортування масиву за не спаданням методом вибору можна описати так: 1. Серед всіх елементів масиву, починаючи з першого, будь яким способом відшукується мінімальний елемент. 2. Знайдений мінімальний елемент поміщається на місце першого елементу. 3. Перевіряється масив від другого елементу, знаходиться мінімальний серед тих, що залишилися і поміщається на місце другого елементу. 4. І так далі до останнього елементу.
Малюнок 2.1 - Алгоритм сортування по не спаданню методом вибору.
Аналіз описаних вище дій при сортуванні вибором показує, що для програмної реалізації цього методу сортування буде потрібно два цикли for. У зовнішньому циклі повинен змінюватися номер змінного елементу від першого до передостаннього. Цей цикл визначатиме кількість проходів по масиву. Внутрішній цикл повинен забезпечити послідовне порівняння змінного елементу зі всіма елементами, які слідують в масиві за ним. У тілі внутрішнього циклу виробляється порівняння елементів. У тілі внутрішнього циклу виробляється порівняння елементів, індекси яких задаються параметрами зовнішнього і внутрішнього циклу. Якщо при порівнянні виявляється, що порядок дотримання елементів порушений, то порівнювані елементи міняються місцями. Схема алгоритму сортування масиву методом вибору показана на малюнку 2.1. Вихідними даними для алгоритму є: сортований масив mas і кількість елементів в цьому масиві count
Процедура сортування масиву методом вибору procedure SortChoise (var a: TArray100; count: integer); var i, j, x: integer; begin i:= 1 to count - 1 do begin j:= i + 1 to count do if a[j] > a[i] then begin:= a[i];[i]:= a[j];[j]:= x; end;;;
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-02-07; просмотров: 209; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.116.69.240 (0.029 с.) |