QBASICBOOK.ru: сайт про QB64

Одной из основных операций, производимых над массивами, являются операции сортировки или упорядочивания элементов массива по какому-либо признаку: чаще по возрастанию или убыванию – для чисел, и по алфавиту – для символов и строк. Сортировок придумано множество, и, говорят, тому, кто придумает новый эффективный метод сортировки, сразу будет вручена Нобелевская премия. С древних времен до нас дошли два самых простых (конечно, не самых эффективных) способа сортировки, которые мы здесь и рассмотрим.

Задача. Отсортировать одномерный массив (вектор) методом «пузырька» по возрастанию.

Название данного метода часто вызывает нездоровый смех у молодежи, хотя никакого тайного смысла у этого метода нет. Просто он выполняется таким образом, что максимальное число после каждого шага сортировки как бы всплывает в конец массива, на свое заслуженное место.

Заключается метод в следующем: программа, начиная с первых элементов массивов, сравнивает эти элементы попарно, и, в случае, если они расположены не по возрастанию, меняет их местами.

Прежде чем написать полную программу, я попробую объяснить суть работы «пузырькового» метода.

Дан массив: 4 3 2 1.

Рассмотрим по шагам метод «пузырька» для этого массива:

• (3) (4) 2 1
• 3 (2) (4) 1
• 3 2 (1) (4)
• (2) (3) 1 4
• 2 (1) (3) 4
• (1) (2) 3 4

Теперь приступим к основному решению:

---

1. REM VECTOR
2. CLS
3. RANDOMIZE TIMER
4. CONST N = 5 'RAZMER MASSIVA
5. DIM A(N)
6. 'ZAPOLNENIYE SLUCHAYNYMI CHISLAMI OT 0 DO 10
7. A = 0: B = 10
8. FOR I = 1 TO N
9.     A(I) = INT((B - A + 1) * RND + A)
10. NEXT I
11. 'VIVOD
12. PRINT "ISKHODNYY MASSIV:"
13. FOR I = 1 TO N
14.     PRINT USING "##.##  "; A(I);
15. NEXT I
16. 'SORTIROVKA
17. PRINT
18. FOR I = 1 TO N
19.     FOR CNT = 1 TO N - 1
20.         IF (A(CNT) > A(CNT + 1)) THEN
21.             TEMP = A(CNT)
22.             A(CNT) = A(CNT + 1)
23.             A(CNT + 1) = TEMP
24.         END IF
25.     NEXT CNT
26. NEXT I
27. PRINT "UPORYADOCHENNYY PO VOZRASTANIYU:"
28. FOR I = 1 TO N
29.     PRINT USING "##.##  "; A(I);
30. NEXT I
31. END

---

 

Рисунок 1 – Исходный текст программы сортировки массива по возрастанию пузырьковым методом

 

Рисунок 2 – Результат выполнения программы сортировки массива по возрастанию пузырьковым методом

Теперь рассмотрим сортировку выбором.

Допустим, дан числовой массив из N элементов. Надо отсортировать его по возрастанию.

Суть способа в следующем:

• Находим наибольший элемент в массиве и меняем его местами с последним.
• Уменьшаем количество рассматриваемых элементов на 1 (т. к. последний элемент уже на своем месте).
• Повторяем операцию для уменьшенного на единицу массива. И так – N - 1 раз.

Пусть дан массив из пяти элементов: 8 4 9 6 7.

Рассмотрим процесс упорядочивания по шагам:

• 8 4 (7) 6 (9)
• (6) 4 7 (8) 9
• (6) 4 7 (8) 9
• (4) (6) 7 8 9

Пример:

---

1. REM VYBOR
2. CLS
3. RANDOMIZE TIMER
4. CONST N = 5 'RAZMER MASSIVA
5. DIM A(N)
6. 'ZAPOLNENIYE SLUCHAYNYMI CHISLAMI OT 0 DO 10
7. A = 0: B = 10
8. FOR I = 1 TO N
9.     A(I) = INT((B - A + 1) * RND + A)
10. NEXT I
11. 'VIVOD
12. FOR I = 1 TO N
13.     PRINT USING "##  "; A(I);
14. NEXT I
15. PRINT
16. 'VYBOR
17. FOR I = 1 TO N - 1
18.     MIN = I
19.     FOR CNT = I + 1 TO N
20.         IF (A(MIN) > A(CNT)) THEN MIN = CNT
21.     NEXT CNT
22.     SWAP A(I), A(MIN)
23. NEXT I
24. 'VIVOD
25. FOR I = 1 TO N
26.     PRINT USING "##  "; A(I);
27. NEXT I
28. END

---

 

Рисунок 3 – Исходный текст программы сортировки массива по возрастанию методом выбора

Рисунок 4 – Результат выполнения программы сортировки массива по возрастанию методом выбора

Следующий пример продемонстрирует сортировку по возрастанию методом Шелла (Shall)

---

1. CLS
2. RANDOMIZE TIMER
3. CONST N = 10
4. DIM A(N)
5. PRINT "ISKHODNYY MASSIV:"
6. A = 0: B = 10
7. FOR I = 1 TO N
8.     A(I) = INT((B - A + 1) * RND + A)
9.     PRINT USING "##.##  "; A(I);
10. NEXT
11. PRINT
12. 'SORTIROVKA SHALL
13. D = N \ 2
14. WHILE (D > 0)
15.     DO
16.         DONE = 1
17.         FOR I = 1 TO N - D
18.             IF A(I) > A(I + D) THEN
19.                 SWAP (A(I)), (A(I + D)) 'OBMEN ZNACHENIY DVUKH PEREMENNYKH
20.                 DONE = 0
21.             END IF
22.         NEXT
23.     LOOP UNTIL DONE
24.     D = D \ 2
25. WEND
26. PRINT "UPORYADOCHENNYY PO VOZRASTANIYU:"
27. FOR I = 1 TO N
28.     PRINT USING "##.##  "; A(I);
29. NEXT
30. PRINT
31. END

---

 

Рисунок 5 – Исходный текст программы сортировки массива по возрастанию методом Шелла

 

Рисунок 6 – Результат выполнения программы сортировки массива по возрастанию методом Шелла

Новым здесь является оператор SWAP. Синтаксис:

SWAP <переменная_1>, <переменная_2>

Обмен значениями с помощью оператора SWAP может выполняться для любых типов переменных (целых, с обычной точностью, с двойной точностью, строковых), однако, обе переменные должны иметь один и тот же тип. В противном случае возникает ошибка «Type mismatch».

Самостоятельно разберитесь в работе этих программ. Попробуйте отобразить работу этих методов на бумаге, если не получится, обратитесь к поисковикам сети Интернет или в комментарии.

Ниже представлены задачи для самостоятельного изучения.

Задача: Дан массив переменных A(10), который заполнен последовательностью чисел от 1 до 10. С помощью различных методов, отсортировать его по убыванию.

Сортировка методом пузырька:

---

1. N = 10
2. DIM A(N)
3. FOR I = 1 TO N
4.     A(I) = I
5. NEXT
6. FOR I = 1 TO N
7.     PRINT A(I);
8. NEXT
9. PRINT
10. FOR I = 1 TO N - 1
11.     FOR J = 1 TO N - I
12.         IF A(J) < A(J + 1) THEN SWAP A(J), A(J + 1)
13.     NEXT
14. NEXT
15. FOR I = 1 TO N
16.     PRINT A(I);
17. NEXT

---

 

Рисунок 7 – Исходный текст программы сортировки массива по убыванию методом пузырька

 

Рисунок 8 – Результат выполнения программы сортировки массива по убыванию методом пузырька

Сортировка методом вставки:

---

1. CONST N = 10
2. DIM A(N)
3. FOR I = 1 TO N
4.     A(I) = I
5. NEXT
6. FOR I = 1 TO N
7.     PRINT A(I);
8. NEXT
9. PRINT
10. FOR I = 1 TO N
11.     X = A(I)
12.     J = I - 1
13.     WHILE J > 0 AND A(J) < X
14.         A(J + 1) = A(J)
15.         J = J - 1
16.     WEND
17.     A(J + 1) = X
18. NEXT
19. FOR I = 1 TO N
20.     PRINT A(I);
21. NEXT

---

 

Рисунок 9 – Исходный текст программы сортировки массива по убыванию методом вставки

 

Рисунок 10 – Результат выполнения программы сортировки массива по убыванию методом вставки

Сортировка методом выбора:

---

1. N = 10
2. DIM A(N)
3. FOR I = 1 TO N
4.     A(I) = I
5. NEXT
6. FOR I = 1 TO N
7.     PRINT A(I);
8. NEXT
9. PRINT
10. FOR I = 1 TO N
11.     MAX = A(I)
12.     K = I
13.     FOR J = I + 1 TO N
14.         IF A(J) > MAX THEN MAX = A(J): K = J
15.     NEXT
16.     SWAP A(I), A(K)
17. NEXT
18. FOR I = 1 TO N
19.     PRINT A(I);
20. NEXT

---

 

Рисунок 11 – Исходный текст программы сортировки массива по убыванию методом выбора

 

Рисунок 12 – Результат выполнения программы сортировки массива по убыванию методом выбора

Вот ещё один вариант с чуть более нагруженным внутренним циклом, но с меньшей инициализаций его же.

Назовём эту штуку «двусторонняя» сортировка выбором:

---

1. DATA -4,3,4,3,4,5,9,8,5,9
2. CLS
3. FOR I = 1 TO 10: READ A(I): PRINT A(I);: NEXT
4. FOR I = 0 TO 4
5.     MNI = 1 + I: MXI = MNI
6.     MIN = A(MNI): MAX = MIN
7.     FOR N = 1 + I TO 10 - I
8.         IF A(N) > MAX THEN MAX = A(N): MXI = N
9.         IF A(N) < MIN THEN MIN = A(N): MNI = N
10.     NEXT
11.     SWAP A(1 + I), MAX
12.     SWAP A(10 - I), MIN
13. NEXT
14. PRINT
15. FOR I = 1 TO 10: PRINT A(I);: NEXT

---

 

Рисунок 13 – Исходный текст программы сортировки массива по убыванию «двусторонним» методом выбора

 

Рисунок 14 – Результат выполнения программы сортировки массива по убыванию «двусторонним» методом выбора

Ограничение этого метода: Должно быть чётное число элементов.

Алгоритм легко масштабируется (для случаев с количеством элементов кратных 4, 8, и т.д.). Полагаю, что он уступает сложным алгоритмам, например, QSort'у (быстрая сортировка), но зато не требует дополнительной памяти, легко реализуется (без структур типа «бинарное дерево») и не «страдает» от «плохого» распределения данных.

Для сравнения сортировка 15000 чисел (на QB64):

• Этим алгоритмом: ~22.5 сек
• Сортировкой выбором: ~35.5 сек

Спасибо за прочтение этой статьи.

 

• sort-vector-in-ascending-order-1.bas
• sort-vector-in-ascending-order-2.bas
• sort-vector-in-ascending-order-3.bas
• sort-vector-in-ascending-order-4.bas
• sort-vector-in-ascending-order-5.bas
• sort-vector-in-ascending-order-6.bas
• sort-vector-in-ascending-order-7.bas