Лабораторна робота №9

 

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

 

Мета роботи – оволодіння методами реалізації сортувань числових масивів.

 

Теоретична частина

 

Під сортуванням в програмуванні розуміють процес розміщення елементів в порядку зростання або спадання їх значень. Наприклад, нам треба розмістити елементи в масиві A (2, 0, -3, 1, -5) за зростанням та спаданням їх значень. В результаті маємо:

• за зростанням – A (-5, -3, 0, 1, 2);
• за спаданням – A (2, 1, 0, -3, -5).

Існують різні методи сортування (обмінне сортування, сортування методом вибору, сортування методом перестановки за індексами, турнірне сортування, сортування вставкою та ін.). Більш детально з методами сортування можна ознайомитися в навчальній літературі.

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

 

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

Розглянемо масив А= (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 Лабораторна робота №9, задача №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. Як відсортувати масив за:

· зростанням;

· спаданням?

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

   -

   +

   

   ai ai+1

   Перечисліть пункти, з яких складається розв’язання задачі на сортування.
2. Перечисліть відомі вам методи сортування.
3. Наведіть (словесно) алгоритми розповсюджених методів сортування.

 

Варіанти завдань

 

1. Задано масив чисел B(M). Упорядкувати K перших елементів (K<M) у порядку спадання їх значень.

2. У заданому масиві чисел C(M) упорядкувати K його перших елементів (K<M) у порядку спадання їх значень, а інші елементи — в порядку зростання їх значень.

3. Упорядкувати заданий числовий масив X(M) в порядку спадання значень його елементів.

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

5. У заданому масиві чисел C(M) упорядкувати елементи, номери яких розміщені в інтервалі [K,L], у порядку спадання значень елементів. Дано, що K<L<M.

6. Перетворити заданий числовий масив D(N), упорядкувавши перші K елементів за зростанням, наступні M елементів за спаданням, інші залишити без зміни. (Відомо, що 1<K<M, K+M<N).

7. Перетворити даний числовий масив X(N), упорядкувавши елементи з K-го по L-й за зростанням, а елементи з M-го по P-й за спаданням. (Відомо, що 1<K<L<M<P<N).

8. Перетворити даний числовий масив В(N), упорядкувавши його за спаданням так, щоб M його останніх елементів залишились неупорядкованими. (Відомо, що M<N).

9. Перетворити даний числовий масив D(N), упорядкувавши незалежно першу та другу половини вихідного масиву за зростанням. (Відомо, що N - парне число).

10. Задано масив чисел D(N). Визначити кількість K додатних елементів масиву та упорядкувати в порядку зростання останні K елементів масиву. У разі неможливості зробити це, видати повідомлення.

11. Задано масив чисел Z(M). Якщо максимальний елемент масиву кратний мінімальному, то упорядкувати елементи масиву за зростанням, інакше - за спаданням.

12. Задано масив чисел Q(y). Визначити кількість N від¢ємних елементів масиву та упорядкувати в порядку зростання перші N елементів масиву. У разі неможливості зробити це, видати повідомлення.

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

14. Задано масив чисел X(N) з попарно різних елементів. Визначити, чи є масив упорядкованим за зростанням.

15. Задано масив чисел K(H). Визначити, чи є він упорядкованим за спаданням.

16. Задано масив чисел X(K) з попарно різних елементів. Визначити, чи є він упорядкованим за спаданням. Якщо так, то видалити максимальний елемент.

17. Задано масив чисел A(N). Якщо в результаті заміни від¢ємних елементів їх квадратами, елементи масиву будуть створювати неспадаючу послідовність, то одержати суму членів вихідної послідовності, в протилежному випадку - добуток.

18. Задано масив чисел Q(M). Упорядкувати його останні L елементів за незростанням (за неспаданням)(1<L<M).

19. Задано масив чисел A(N), де N — кратне трьом. Упорядкувати першу третину елементів масиву за спаданням, другу третину—за зростанням, решту елементів залишити на своїх місцях.

20. Задано масив чисел В(М), де М — кратне чотирьом. Упорядкувати першу чверть елементів масиву за зростанням, третю чверть—за спаданням, решту елементів залишити на своїх місцях.

21. Задано масив чисел U(N), де N — кратне чотирьом. Упорядкувати другу чверть елементів масиву за спаданням, третю чверть—за зростанням, решту елементів залишити на своїх місцях.

22. Задано масив чисел KO(S), де S—кратне чотирьом. Упорядкувати першу чверть елементів масиву за зростанням, четверту чверть за спаданням, решту елементів залишити на своїх місцях.

23. Задано масив чисел U(T), що складається з попарно різних чисел. Упорядкувати елементи від першого до максимального за зростанням (за спаданням).

24. Задано масив чисел А(К), що складається з попарно різних чисел. Упорядкувати елементи з першого до мінімального за зростанням (за спаданням).

25. Задано масив чисел UT(N), що складається з попарно різних чисел. Упорядкувати елементи, починаючи з максимального елементу до кінця масиву за зростанням (за спаданням).

26. Задано масив чисел АМ(К), що складається з попарно різних чисел. Упорядкувати елементи, що розміщені після мінімального елемента до кінця масиву за зростанням (за спаданням).

27. Задано масив чисел V(M), елементи якого попарно різні. Упорядкувати елементи, що розміщені між мінімальним та максимальним елементами масиву за спаданням (за зростанням).

28. Задано масив чисел G(K), де К — парне число. Визначити чи є перша половина його елементів упорядкованою.

29. Задано натуральне число К і масив чисел А(N), де N кратне К. Масив розбито на частини по К елементів у кожній. Упорядкувати кожну частину з парним номером за зростанням значень елементів.