Пример 1

ДЕМОНСТРАЦИОННЫЕ ПРИМЕРЫ

Шейкер-сортировка

Сортировка бинарными включениями

Сортировка включениями

Сортировка выбором

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

Выбранный в исходной последовательности минимальный элемент размещается на предназначенном ему месте упорядоченной последовательности несколькими способами:

а) минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) другого специально созданного массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое число, превосходящее по величине любой элемент сортируемого массива. Измененный таким образом массив принимается за исходный, и осуществляется следующий просмотр;

(См. Пример 2.)

б) минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) заданного массива, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т.е. размер каждого последующего обрабатываемого массива на единицу меньше размера предыдущего.

При сортировке включениями из неупорядоченной последовательности элементов поочередно выбирается каждый элемент, сравнивается с предыдущим (уже упорядоченным) списком и помещается на соответствующее место в последнем.

(См. Пример 3.)

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

(См. Пример 4.)

(См. Пример 5.)

' Имя файла Sort_Bubble.vbs

' Программа демонстрирует сортировку вектора по неубыванию методом обмена

' или (другое название) пузырьком.

Option Explicit

Dim sorted, i, j, s, B, x

B=Array (5, 3, 2, 1, 0, -1) ' вектор, который должен быть отсортирован пузырьком

sorted=false ' логическая переменная

While not sorted ' пока вектор не отсортирован...

sorted=true

For i=0 to 4

If B(i+1)<B(i) Then ' если левый элемент больше правого, то поменять их местами

x=B(i)

B(i)=B(i+1)

B(i+1)=x

For j=0 to 5 ' в переменную s записывается изменённый вектор

s=s&B(j)&" "

Next

s=s&VbCrLf

Sorted=false

End If

Next

Wend

MsgBox "Задача:"&vbCrLf&_

"Отсортировать вектор (5, 3, 2, 1, 0, -1)"&vbCrLf&vbCrLf&_

"Пошаговая сортировка:"&vbCrLf&_

s&vbCrLf,vbInformation, "Сортировка пузырьком:"

Дата добавления: 2014-12-29