ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Опишіть алгоритми сортування в одновимірному масиві.

Однією з найбільш поширених операцій обробки масивів є їх упорядкування, або сортування. Упорядкування масиву — це зміна порядку розташування його елементів за певним критерієм. Наприклад, числовий масив можна упорядкувати за зростанням значень його елементів або за їх спаданням, а масив рядків можна відсортувати в алфавітному порядку. Найчастіше сортування масиву здійснюється з метою полегшення подальшого пошуку.

Відомо багато методів сортування масиву, що відрізняються швидкодією й обсягом оперативної пам'яті, яка при цьому використовується. Серед цих методів можна вирізнити методи внутрішнього та зовнішнього сортування. Методи внутрішнього сортування не передбачають використання допоміжних масивів. Ці методи застосовують до масивів, що повністю розташовані в оперативній пам'яті. Методи зовнішнього сортування застосовують до великих масивів даних, які зберігаються на зовнішніх носіях. У цьому розділі розглянемо методи внутрішнього сортування масиву, обмежуючись задачею сортування за зростанням. Методи внутрішнього сортування прийнято поділяти на дві групи: елементарні (прямі) та удосконалені методи.

Найбільш відомими елементарними методами сортування масиву є:

сортування вставкою (включенням);

сортування вибором;

сортування обміном (бульбашкове сортування).

З удосконалених методів сортування найчастіше використовуються такі:

швидке сортування, або метод Хоара;

сортування включенням зі спадним приростом, або метод Шелла;

сортування за допомогою дерева, або пірамідальне сортування;

сортування методом злиття.

Нижче буде розглянуто всі три вищезгаданих елементарних методи сортування та два удосконалених — метод Хоара й метод злиття.

Сортування методом вставки

На кожному кроці цього методу масив розділений на дві частини: ліву, вже відсортовану, та праву, ще не відсортовану. Перший елемент правої частини вставляється до лівої частини так, щоб ліва частина залишалася відсортованою. У результаті відсортована частина збільшується на один елемент, а невідсортована - на один елемент зменшується. Отже, на кожному кроці алгоритму сортування методом вставки слід виконати дві операції: пошук позиції для вставки елемента та власне його вставку із подальшим зсувом на одну позицію вправо від елементів відсортованої частини. Цей зсув «затре» перший елемент невідсортованого під-масиву останнім елементом відсортованого. Спочатку відсортованим підмасивом вважаємо перший елемент, а решту елементів масиву відносимо до невідсорто-ваної частини.

Приклад 7.9

Формалізуємо алгоритм сортування методом вставки, а також наведемо його програмну реалізацію. Підмасив, що містить елементи з другого до останнього, вважати невідсортованого частиною. Поки ця частина не стане порожньою, виконувати такі дії.

Зберегти перший елемент невідсортованого підмасиву в допоміжній змінній.

Визначити позицію вставки збереженого елемента у масив. Для цього дотримуватися перелічених далі вказівок.
2.1. Вважати перший елемент масиву поточним.
2.2. Доки елемент для вставки більше за поточний, збільшувати індекс поточного елемента.

Вставити збережений на кроці 1 елемент на знайдену позицію вставки, зсунувши на одну позицію вправо решту відсортованої частини.

Пересунути початок невідсортованої частини на одну позицію вправо.

Program EX7_8;
var n,i,j,k:integer;
a:array[1..10]of integer;
tmp:integer;
begin
randomize;
writeln('insertion sort');

writeln('enter number of the components (<=10)');

readln(n);
for i:=1 to n do
a[i]:=random(30);

writeln('generated array');

for i:=1 to n do
write(a[i],' ');

writeln;
writeln('sort process');

for i:=2 to n do
begin
tmp:=a[i];
j:=1;
while tmp>a[j] do
j:=j+1;
for k:=i-1 downto j do
a[k+1]:=a[k];
a[j]:=tmp;
for k:=1 to n do
write(a[k],' ');

writeln;
end;
writeln('sorted array');

for i:=1 to n do

write(a[i],' ');

end.

Рис. 7.10. Результати роботи програми ех7_8. Сортування масиву методом вставки

Демонстрація прикладу

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

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

Приклад 7.10

Формалізуємо алгоритм сортування методом вибору і реалізуємо його мовою Pascal. Весь масив вважати невідсортованою частиною. Поки ця частина містить більше одного елемента, виконувати такі дії:

Вибрати перший елемент невідсортованої частини масиву і вважати його мінімальним; запам'ятати індекс цього елемента.

Для елементів від наступного після вибраного і до останнього повторювати такі дії.
2.1. Порівняти вибраний елемент і поточний.

2.2. Якщо вибраний елемент більший за поточний, запам'ятати поточний елемент як мінімальний, а його індекс — як індекс мінімального елемента.

Поміняти місцями мінімальний і вибраний на кроці 1 елементи.

Пересунути початок невідсортованої частини на одну позицію вправо.

Program EX7_9;
var n,i,j:integer;
a: array[1..10] of integer;
min,imin:integer;
begin
randomize;
writeln('selection sort');

writeln('enter number of thr components (<=10)');

readln(n);
for i:=1 to n do

a[i]:=random(30);

writeln('generated array');

for i:=1 to n do

write(a[i],' ');

writeln;

writeln('series of selection');

for i:=1 to n-1 do
begin
min:=a[i];
imin:=i;
for j:=i+1 to n do
if min>a[j] then
begin
min:=a[j];
imin:=j;
end;
a[imin]:=a[i];
a[i]:=min;
for j:=1 to n do
write(a[j],' ');

writeln;
end;
writeln('sorted array');

for i:=1 to n do
write(a[i],' ');
end.

Рис. 7.11. Результати роботи програми ех7_9. Сортування масиву методом вибору

Сортування методом обміну

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

Приклад 7.11

Розглянемо алгоритм сортування методом обміну та його реалізацію мовою Pascal.

Установити лічильник ітерацій рівним одиниці.

Для елементів масиву, від останнього до елемента з індексом, що дорівнює поточному значенню лічильника ітерацій, повторювати такі дії.
2.1. Якщо поточний елемент більший за попередній, поміняти ці елементи місцями.
2.2. Перейти до попереднього елемента.

Збільшити лічильник ітерацій. Якщо значення лічильника дорівнює кількості елементів масиву, завершити сортування.

Program EX7_10;
var n,i,j,k:integer;
a:array[1..10]of integer;
tmp:integer;
begin
randomize;
writeln('exchange sort');

writeln('enter number of the components (<=10)');

readln(n);
for i:=2 to n do
a[i]:=random(30);
writeln('generated array');

for i:=1 to n do
write( a[i],' ');

writeln;
writeln('sort process');

for i:=2 to n do
for j:=n downto i do
if a[j]<a[j-1] then
begin
tmp:=a[j];
a[j]:=a[j-1];
a[j-1]:=tmp;
for k:=1 to n do
write(a[k],' ');
writeln;
end;
writeln('sorted array');

for i:=1 to n do
write(a[i],' ');

end.

Рис. 7.12. Результати роботи програми ех7_10. Сортування масиву методом обміну

Алгоритми сортування масивів методами вибору, вставки та обміну не потребують додаткової оперативної пам'яті. Час виконання розглянутих алгоритмів сортування пропорційний кількості операцій порівняння або перестановок елементів. Сортування n-елементного масиву методом вибору потребує n2/2 операцій порівняння та n операцій обміну елементів. Метод сортування вставкою потребує n2/4 операцій порівняння та стільки ж операцій обміну, а метод сортування обміном — n2/2 операцій порівняння та n2/2 операцій обміну. Отже, методи вставки та вибору за характеристиками приблизно еквівалентні, проте метод обміну поступається перед ними швидкодією.

Удосконалені методи сортування масиву використовують значно меншу кількість операцій порівняння та перестановок елементів. Детальний аналіз алгоритмів сортування зроблено у [5, 12, 13]. Розглянемо один з удосконалених методів сортування масиву.

Швидке сортування

Автор цього метода Ч. Хоар назвав його швидким сортуванням, оскільки для більшості масивів цей метод потребує приблизно (n/6) log n обмінів елементів і n log n порівнянь, тобто набагато менше, ніж будь-який з елементарних методів. Метод функціонує за принципом «розділяй та пануй»: елементи масиву діляться на дві частини, і кожна з них потім сортується окремо. Для цього обирають деякий елемент х, назвемо його розділовим. Мета полягає у розташуванні всіх менших за х елементів зліва від х, а всіх більших за х елементів — справа від х. Поділивши масив, слід повторити процедуру сортування для кожної частини, потім - для частин цих частин і т. д., доки кожна з частин масиву не міститиме лише один елемент. Зауважимо, що у деяких модифікаціях методу Хоара розташування та значення розділового елемента можуть змінюватися під час розподілу елементів. Розглянемо одну з таких модифікацій.

Отже, алгоритм методу Хоара є рекурсивним і для його реалізації було б зручно застосувати рекурсивну процедуру. Параметрами цієї процедури будуть змінні left та right, що позначатимуть ліву та праву межу розглядуваної частини масиву. Розділовим елементом вважатимемо середній за номером елемент частини масиву і присвоїмо значення цього елемента змінній х. Рекурсивний виклик процедури для поділу лівого підмасиву на дві частини здійснюється в тому разі, якщо ліва межа підмасиву менша за індекс його середнього елемента, а для поділу правого підмасиву — якщо права межа більша за індекс середнього елемента. Для поділу елементів на дві частини застосовуємо два цикли while у середині циклу repeat-until. На кожній ітерації зовнішнього циклу здійснюватиметься один обмін елементами між лівою та правою частинами. Внутрішні цикли (здійснюють перегляд масиву зліва та справа) призначені для знаходження чергової пари елементів, що мають бути переставлені. Зазначимо, що переставленим може бути і сам розділовий елемент, при цьому він може втратити властивість розділовості. Цей факт не впливає на коректність роботи розглянутої далі програми.

Нижче наведено код програми ех7_11, а на рис. 7.13 зображено результати її виконання. Цикл, що здійснює виведення проміжних результатів, у код програми ех7_11 не включено.

Приклад 7.12

Program EX7_11;
var i,n:integer;

a:array[1..10] of integer;
procedure quicksort(left,right:integer);
var i,j,k,x,tmp:integer;
begin
i:=left;
j:=right;
x:=a[(left+right) div 2];

writeln('left=',left,' right=',right,' x=',x);

repeat
while a[i]<x do i:=i+1;
while a[j]>x do j:=j-1;
if i<=j then
begin
tmp:=a[i];
a[i]:=a[j];
a[j]:=tmp;
i:=i+1;
j:=j-1;
for k:=1 to n do
write(a[k],' ');

writeln;
end;
until i>j;
if left<j then
quicksort(left,j);
if i<right then
quicksort(i,right);
end;
begin
randomize;
writeln('quick sort');

writeln('enter number of the components (<=10)');

readln(n);
for i:=1 to n do
a[i]:=random(30);
writeln('generated array');

for i:=1 to n do

write(a[i],' ');

writeln;

writeln('sort process');

quicksort(1,n);

writeln('sorted array');

for i:=1 to n do

write(a[i],' ');

writeln;
end.

Рис. 7.13. Результати роботи програми ех7_11. Швидке сортування масиву

Сортування методом злиття

У запропонованому Дж. фон Нейманом методі сортування злиттям, як і в методі Хоара, реалізовано принцип «розділяй та пануй». Масив ділиться навпіл, до кожної половини застосовується рекурсивно та сама процедура сортування злиттям, а відсортовані частини з'єднуються в один впорядкований масив.

Отже, базовою операцією методу є злиття двох упорядкованих масивів в один. Ефективний спосіб виконання цієї операції полягає в тому, що елементи масивів порівнюються і за результатами порівняння в новий масив записується елемент або з першого, або з другого масиву. Один з масивів під час злиття може закінчитися раніше. В такому випадку елементи іншого масиву, які ще не були опрацьовані, слід додати до нового масиву.

Час злиття упорядкованих масивів лінійно залежить від їх сумарної довжини. Враховуючи цей факт, неважко буде довести, що повне сортування методом злиття, як і сортування методом Хоара, потребує виконання O(n log n) базових операцій над елементами масиву розмірності n.

Програму сортування методом злиття наведемо у прикладі 7.13 з наступного розділу. Задачу злиття двох масивів реалізуємо за допомогою процедури. Оскільки процедура злиття має бути застосована до різних підмасивів, то зручно було б передавати масив до процедури як параметр. Особливостям використання масивів як параметрів підпрограм і присвячено наступний розділ.

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти