 |
Сортировка выбором. Сортировка включениями. Сортировка бинарными включениями. Шейкер-сортировка. 7. 3 демонстрационные Примеры
|
|
|
|
Сортировка выбором
При этом методе сортировки в неупорядоченной последовательности выбирается минимальный элемент, который исключается из дальнейшей обработки, а оставшаяся последовательность элементов принимается за исходную. Процесс повторяется до тех пор, пока все элементы не будут выбраны. Очевидно, что все выбранные элементы образуют упорядоченную последовательность.
Выбранный в исходной последовательности минимальный элемент размещается на предназначенном ему месте упорядоченной последовательности несколькими способами:
а) минимальный элемент после i-го просмотра перемещается на i-е место (i=1, 2, 3,... ) другого специально созданного массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое число, превосходящее по величине любой элемент сортируемого массива. Измененный таким образом массив принимается за исходный, и осуществляется следующий просмотр;
(См. Пример 2. )
б) минимальный элемент после i-го просмотра перемещается на i-е место (i=1, 2, 3,... ) заданного массива, а элемент с i-го места - на место выбранного. После каждого просмотра упорядоченные элементы (от первого до элемента с индексом i) исключаются из дальнейшей обработки, т. е. размер каждого последующего обрабатываемого массива на единицу меньше размера предыдущего.
Сортировка включениями
При сортировке включениями из неупорядоченной последовательности элементов поочередно выбирается каждый элемент, сравнивается с предыдущим (уже упорядоченным) списком и помещается на соответствующее место в последнем.
(См. Пример 3. )
Сортировка бинарными включениями
По количеству сравнений алгоритм сортировки бинарными включениями лучше, чем рассмотренные выше алгоритмы. Различными авторами предпринимались попытки доказательства оптимальности алгоритма сортировки бинарными включениями и даже печатно сообщалось о якобы найденном доказательстве. Позднее выяснилось, что и этот алгоритм не оптимален, т. к. он требует восемь сравнений для упорядочивания пяти чисел, а на самом деле достаточно семи сравнений.
|
|
|
(См. Пример 4. )
Шейкер-сортировка
(См. Пример 5. )
7. 3 ДЕМОНСТРАЦИОННЫЕ ПРИМЕРЫ
Пример 1
' Имя файла 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, " Сортировка пузырьком: "
Пример 2
' Имя файла Sort_Choice. vbs
' Программа демонстрирует сортировку вектора по неубыванию методом простого
' выбора (первый способ).
Option Explicit
Dim i, j, s, B, x, k, m
B=Array (5, 3, 2, 1, 0, -1) ' вектор, который должен быть отсортирован
' Начало алгоритма сортировки
For i=0 to 4
k=i: x=B(i)
For j=i+1 to 5
If B(j)< x Then
k=j
x=B(j)
|
|
|
End If
B(k)=B(i)
B(i)=x
For m=0 to 5
s=s& B(m)& " " ' в переменную s записывается изменённый вектор
Next
s=s& VbCrLf
Next
Next
' Конец алгоритма сортировки
MsgBox " Задача: " & vbCrLf& _
" Отсортировать вектор (5, 3, 2, 1, 0, -1)" & vbCrLf& vbCrLf& _
" Пошаговая сортировка: " & vbCrLf& _
s& vbCrLf, vbInformation, " Сортировка простым выбором (1 сп): "
Пример 3
' Имя файла Sort_Insert. vbs
' Программа демонстрирует сортировку вектора по неубыванию методом простых
' включений.
Option Explicit
Dim i, j, s, x, k, m
Dim B (6) ' вектор, который должен быть отсортирован
B(1)=5
B(2)=3
B(3)=10
B(4)=1
B(5)=0
B(6)=-1
' Начало алгоритма сортировки
For i=1 to 6
x=B(i): B(0)=x: j=i-1
While x< B(j)
B(j+1)=B(j): j=j-1
Wend
B(j+1)=x
For m=0 to 6
s=s& B(m)& " " ' в переменную s записывается изменённый вектор
Next
s=s& VbCrLf
Next
' Конец алгоритма сортировки
MsgBox " Задача: " & vbCrLf& _
" Отсортировать вектор (5, 3, 10, 1, 0, -1)" & vbCrLf& vbCrLf& _
" Пошаговая сортировка: " & vbCrLf& _
s& vbCrLf, vbInformation, " Сортировка простыми включениями: "
Пример 4
' Имя файла Sort_Bin_Insert. vbs
' Программа демонстрирует сортировку бинарными включениями
Option Explicit
const N=8
dim Arr()
redim Arr(N) 'наш массив
dim i 'счетчик
randomize
For i=1 To N
arr(i)=Cint(10*rnd(1))
next
dim s
s=" "
For i=1 To N
s=s+CStr(i)+" --> " +Cstr(arr(i))+"; " +vbcrlf
next
dim x, j, l, r, m
' Начало алгоритма сортировки
For i=2 to N
x=Cint(arr(i)): l=1: r=Cint(i-1)
While Cint(l)< =Cint(r)
m=Cint(l+r)\2
if CInt(x)< arr(m) then
r=m-1
else
l=m+1
end if
Wend
j=i-1
While Cint(j)> =Cint(l)
arr(j+1)=arr(j)
j=j-1
Wend
arr(l)=x
Next
' Окончание алгоритма сортировки
dim s1
s1=" "
For i=1 To N
s1=s1+CStr(i)+" --> " +Cstr(arr(i))+"; " +vbcrlf
next
msgbox " Неотсортированный массив: " & vbCrLf& _
s& vbcrlf& vbcrlf& " Отсортированный: " & vbCrLf& _
s1, 0, " Сортировка бинарными включениями: "
|
|
|
