Процедура сортування масиву методом вибору

Факультет прикладної математики

Кафедра специалізованих компьютерних систем

 

 

Курсова робота

з дисципліни “ Структури даних та алгоритми ”

тема “ Дослідження ефективності методів сортування на багатовимірних масивах ”

 

Технічне завдання

1. Описати принцип роботи кожного з методів, що досліджуються, для одновимірного випадку.

2. Скласти алгоритми сортування в багатовимірному масиві методами, що задані за варіантом.

.   Провести практичні дослідження швидкодії складених алгоритмів.

.   За результатами досліджень скласти порівняльні таблиці за різноманітними ознаками.

5. Зробити висновки про порівняння отриманих результатів.

P.S. При бажанні, можна дослідити вплив геометричних розмірів масиву на швидкість сортування, тобто не змінюючи загальної кількості елементів змінювати геометричні розміри масиву. Для випадку перестановки перерізів, не повинна змінюватись загальна кількість перерізів та загальна кількість елементів масиву, а іншими параметрами розмірності можна варіювати. Для випадку перестановки рядків/стовпців у кожному перерізі - не повинна змінюватись кількість рядків/стовпців у кожному перерізі та загальна кількість елементів масиву.

 

Варіант №	Задача	Методи	Способи обходу	Стан масиву
3	7	1, 3, 7	---------------	1, 2, 3

 

Задача

Впорядкувати тривимірний масив 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

	Невпорядкований	Впорядкований	Зворотно впорядкований
Дані по сортуванню вставкою	0141	0	0313
Сортування вибором	0016	0	0000
Шейкерне сортування	0250	0	0547

Масив 100х500х500

Табл. 4.2 - Час сортування для масиву 100х500х500

	Невпорядкований	Впорядкований	Зворотно впорядкований
Дані по сортуванню вставкою	5500	0	12297
Сортування вибором	0 0093	0	0094
Шейкерне сортування	6938	0	14672

Масив 100х500х500

Табл. 4. 3 - Кількість переміщень елементів для масиву 100х500х500

	Невпорядкований	Впорядкований	Зворотно впорядкований
Дані по сортуванню вставкою	649500000	0	1287000000
Сортування вибором	1806000000	0	3712500000
Шейкерне сортування	1806000000	0	3712500000

Масив 100х250х1000

Табл. 4.4 - Час сортування для масиву 100х250х1000

	Невпорядкований	Впорядкований	Зворотно впорядкований
Дані по сортуванню вставкою	5453	0	11485
Сортування вибором	0094	0	0094
Шейкерне сортування	6922	0	14187

 

Масив 100х500х2000

Табл. 4.5 - Час сортування для масиву 100х1000х250

	Невпорядкований	Впорядкований	Зворотно впорядкований
Дані по сортуванню вставкою	6672	0	14250
Сортування вибором	0109	0	0093
Шейкерне сортування	7000	0	14110

4.
Висновки за отриманим результатами

Факультет прикладної математики

Кафедра специалізованих компьютерних систем

 

 

Курсова робота

з дисципліни “ Структури даних та алгоритми ”

тема “ Дослідження ефективності методів сортування на багатовимірних масивах ”

 

Технічне завдання

1. Описати принцип роботи кожного з методів, що досліджуються, для одновимірного випадку.

2. Скласти алгоритми сортування в багатовимірному масиві методами, що задані за варіантом.

.   Провести практичні дослідження швидкодії складених алгоритмів.

.   За результатами досліджень скласти порівняльні таблиці за різноманітними ознаками.

5. Зробити висновки про порівняння отриманих результатів.

P.S. При бажанні, можна дослідити вплив геометричних розмірів масиву на швидкість сортування, тобто не змінюючи загальної кількості елементів змінювати геометричні розміри масиву. Для випадку перестановки перерізів, не повинна змінюватись загальна кількість перерізів та загальна кількість елементів масиву, а іншими параметрами розмірності можна варіювати. Для випадку перестановки рядків/стовпців у кожному перерізі - не повинна змінюватись кількість рядків/стовпців у кожному перерізі та загальна кількість елементів масиву.

 

Варіант №	Задача	Методи	Способи обходу	Стан масиву
3	7	1, 3, 7	---------------	1, 2, 3

 

Задача

Впорядкувати тривимірний масив 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;;;