Лекція 7. Сортування

План лекції:

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

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

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

Алгоритм сортування — це алгоритм для впорядкування елементів в списку (масиві). У разі, коли елемент списку має декілька полів, поле, що служить критерієм порядку, називається ключем сортування.

Відомо багато методів сортування масиву, що відрізняються швидкодією й обсягом оперативної нам’яті, яка при цьому використовується.

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

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

  • Внутрішнє сортування, коли працюють з даними в оперативній пам’яті з довільним доступом;
  • Зовнішнє сортування , коли впорядковують інформацію, розташовану на зовнішніх носіях.

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

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

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

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

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

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

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

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

Незважаючи на значну кількість алгоритмів сортування, з’являються нові алгоритми. Наприклад, відносно новим є алгоритм Timsort, який був опублікований у 2002 році Тімом Петерсом.  Це гібридний алгоритм, який поєднує сортування вставками і сортування злиттям. Зараз він є стандартним алгоритмом сортування в мові Python і реалізований в Android JDK 1.5.

Елементарні алгоритми сортування

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

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

Обчислювальна складність алгоритму О(n2), тобто, при збільшенні розміру масиву час роботи алгоритму зростає квадратично.

Опис алгоритму.

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

Рисунок 7. 1. Сортування вставками

Опис алгоритму на псевдокоді (алгоритм Вірта)

for i = 1 to n-1 do

x = A[i]

j = i

while (j > 0 and A[j-1] > x) do

A[j] = A[j-1]

j = j — 1

end while

A[j] = x

end for

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

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

Опис алгоритму на псевдокоді

function selectionSort(T[n] a):

for i = 0 to n — 2

for j = i + 1 to n — 1

if a[i] > a[j]

swap(a[i], a[j])

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

Цей алгоритм вважається найпростішим та найчастіше використовуваним для сортування невеликих масивів.

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

Запис алгоритму на псевдокоді

Вхід: масив A з елементів A[1], A[2], …, A[n-1], A[n]

t := true

цикл поки t:

t := false

цикл для j = 1, 2, …, n − 1:

якщо A[j] > A[j+1], то:

поміняти місцями елементи A[j] і A[j+1]

t := true

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


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

  1. Поняття сортування. Види сортування.
  2. Опис сортування методом вставки.
  3. Опис сортування методом вибору.
  4. Опис сортування методом обміну.

 

Презентація Методи сортування