Обмінне сортування

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

Розглянемо масив А= (3, 0, 5, 2, -1), що треба упорядкувати в порядку зростання значень елементів. Порівнюючи сусідні елементи (a_i та а_i+1), бачимо, що їх необхідно поміняти місцями, якщо а_i > а_i+1. Масив буде змінюватися при кожному його перегляді. Звернемо увагу на те, як найменший елемент (-1) повільно переміщується в початок масиву.

В результаті одержимо:

• після першого перегляду: А=(0, 3, 2, -1, 5);

• після другого перегляду: А=(0, 2, -1, 3, 5);

• після третього перегляду: А=(0, -1, 2, 3, 5);

• після четвертого перегляду: А=(-1, 0, 2, 3, 5).

При перегляді масиву цикл треба завершати на передостанньому елементі, тому що порівнюються i-й та (i+1)-й елементи. Для упорядкування масиву A(N) достатньо N-1 послідовних переглядів. Дійсно, в розглянутому масиві А(5) із останнього місця найменший елемент перемістився на перше місце за чотири перегляди масиву.

Таким чином, алгоритм сортування складається з двох циклів: внутрішнього, в якому проводиться перестановка необхідних елементів, та зовнішнього, що організує повторні перегляди масиву (рис.9.1). Крім того, необхідно передбачити також виведення елементів вхідного та упорядкованого масивів.

Існує декілька модифікацій наведеного методу, які дозволяють зменшити кількість перевірок та час роботи програми. Наприклад, ввівши допоміжну змінну («прапорець»), можна перевірити настання моменту скінчення сортування (рис. 9.2).

При упорядкуванні за зростанням у циклі перевіряється умова a_i > a_j+1. Неважко побачити, що при упорядкуванні за спаданням треба перевіряти умову a_i < a_j+1.

Приклад 1. Задано масив D(M) та натуральні числа L, N. Упорядкувати за спаданням значень елементи, розміщені між елементами з індексом L та індексом N. Для розв’язання задачі застосуємо метод «прапорця».

REM Сортування частини масиву

20 INPUT M, L, N: DIM D(M)

IF NOT (L>=1 AND N>L AND N<= M) THEN GOTO 20

FOR I=1 TO M: INPUT D(I): NEXT I

80 FLAG=1

FOR I=L+1 TO N-1

IF D(I)<D(I+1) THEN SWAP D(I),D(I+1): FLAG=0

NEXT I

IF FLAG=0 THEN GOTO 80

FOR I=1 TO M: PRINT D(I): NEXT I

END

Приклад 2. Задано масив A(N). Упорядкувати його в порядку зростання значень елементів. Блок-схема на рис. 9.3.

Інші методи сортування

Обмінне сортування має свої переваги та недоліки. Його недоліком є невисока швидкість. Розглянемо декілька інших методів сортування.

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

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

• Сортування методом перестановки за індексами

У масиві, що складається з N елементів, послідовним порівнянням у процесі пошуку знаходиться найменший (найбільший) елемент і запам’ятовується його індекс (К). Після перегляду всього масиву обмінюються місцями перший та К-й елементи. Процедура повторюється, починаючи з другого, третього, четвертого,…, (N-1)-го елементу.

• Сортування підрахунком

Ідея методу базується на тому, що значення j-го елемента в упорядкованій послідовності перевищує рівно (j-1) інших елементів. Таким чином, попарно порівнюються усі елементи та підраховується, скільки з них менше (більше) кожного окремого елемента, що дозволяє визначити номер розглянутого елемента в упорядкованому масиві.

Розв’яжемо приклад 2, але вже методом перестановки за індексами:

REM Перестановка за індексами

INPUT N: DIM A(N)

FOR I=1 TO N: INPUT A(I): NEXT I

FOR I=1 TO N: PRINT A(I): NEXT I

FOR J=1 TO N-1

MIN=A(J)

FOR I=J TO N

IF A(I)<MIN THEN MIN=A(I): K=I

NEXT I

SWAP A(J), A(K)

NEXT J

FOR I=1 TO N: PRINT A(I): NEXT I

END

Приклад 3. Задано масив U(N) та натуральне число К. Упорядкувати елементи, починаючи з елементу з номером К, за зростанням. Для розв’язання цієї задачі застосуємо комбінований метод.

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

20 INPUT N,K

IF 1<=N AND N<K THEN GOTO 40 ELSE GOTO 20

40 DIM U(N)

FOR I=1 TO N: INPUT U(I): NEXT I

FOR I=K TO N-1

FOR J=I+1 TO N

IF U(I)>U(J) THEN SWAP U(I),U(J)

NEXT J,I

FOR I=1 TO N

PRINT U(I)

NEXT I

END

Практика показала, що розв’язання задачі на сортування елементів масиву доцільно подавати у вигляді таких етапів:

• ввести вхідний масив;

• надрукувати вхідний (не впорядкований масив);

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

• здійснити сортування;

• вивести впорядкований масив.

Приклад 4. Задано масив A(M), де M – парне число. Упорядкувати першу половину його в порядку зростання, а другу – у порядку спадання значень елементів.

REM Лабораторна робота №8, задача №1

CLS

REM Сортування одновимірного масиву

INPUT "Введіть розмірність масиву"; M

DIM A(M)

FOR I = 1 TO M:

INPUT "Введіть елементи масиву"; A(I)

NEXT I

CLS

PRINT "Вхідний масив"

FOR I = 1 TO M: PRINT A(I): NEXT I

’ Сортування першої половини масиву в порядку зростання

K = M / 2 : L = K + 1

FOR P = 1 TO K - 1

FOR I = 1 TO K - 1

IF A(I) > A(I + 1) THEN SWAP A(I), A(I + 1)

NEXT I, P

' Сортування другої половини масиву в порядку спадання

FOR P = L TO M - 1

FOR I = L TO M - 1

IF A(I) < A(I + 1) THEN SWAP A(I), A(I + 1)

NEXT I, P

PRINT

PRINT "Впорядкований масив"

FOR I = 1 TO M: PRINT A(I): NEXT I

END

Приклад 5. Задано масив A(M). Упорядкувати N останніх елементів у порядку спадання їх значень (відомо, що N<M).

CLS

REM Лабораторна робота №9, задача №2

INPUT " Введіть розмірність масиву "; M

INPUT "Введіть кількість елементів, які необхідно впорядкувати"; N

PRINT “Введіть елементи масиву”

FOR I = 1 TO M: INPUT A(I);: NEXT I

CLS

PRINT " Вхідний масив "

FOR I = 1 TO M: PRINT A(I);: NEXT I

' Сортування N останніх елементів

R = M - N + 1

FOR P = R TO M - 1

FOR I = R TO M - 1

IF A(I) < A(I + 1) THEN SWAP A(I), A(I + 1)

NEXT I,P

PRINT

PRINT " Впорядкований масив "

FOR I = 1 TO M: PRINT A(I);: NEXT I

END

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

1. Що розуміють під циклом?

2. Описати будову циклу.

3. Що розуміють під тілом циклу?

4. Назвати види циклів.

1. Охарактеризувати цикл з параметром

2. Описати побудову циклу з використанням команди WHILE .

3. Масиви та їх описання.

4. Використання оператора DIM.

5. Способи присвоєння значень елементам масиву.

6. Сортування елементів масиву – що це?

7. Як відсортувати масив за :

• зростанням?

• спаданням?

13. П

    Рис. 1. Блок-схема

    еречисліть пункти, з яких складається розв’язання задачі на сортування.

14. Перечисліть відомі вам методи сортування.

15. Наведіть (словесно) алгоритми розповсюджених методів сортування.

16