Лабораторная работа “Методы
сортировки ”
Цель:
Данное методическое указание предназначено для того, чтобы
получить навыки составления программ на языке VBA, при помощи различных метод сортировок.
Введение:
Сортировка – это последовательное
упорядочивание элементов массива. Существует множество методов сортировок. В
данном методическом указании разматриваются различные методы сортировок. А
именно:
1. Метод сортировки Шелла.
2. Метод сортировки: линейный выбор.
3. Метод челночной сортировки.
4. Быстрая сортировка (метод Хаара).
В данной работе содержится два примера метода линейного
выбора.
Метод сортировки Шелла.
Цель:
1.
Составить программу сортировки массива.
2.
В программе использовать динамический ввод массива.
3.
Отсортировать массив при помощи метода Шелла.
Методические указания:
Метод сортировки
Шелла:
Суть его состоит в том, что выбирается интервал h между
сравниваемыми элементами, который увеличивается после каждого прохода. Для
последовательности интервалов выполняются условия:
h(p)=1; h(i+1)>h(i); i=1,2,…,p-1;
Сначала, сравниваются (и если нужно, переставляются ) соседние элементы , а на последнем проходе –
далеко стоящие элементы.
Выигрыш получается за счет того, что на каждом этапе
сортировки либо участвует мало элементов, либо эти элементы уже довольно хорошо
упорядочены, и требуется небольшое количество перестановок.
Пример:
ListBox1 ListBox2
CommandButton1 CommandButton2
CommandButton3
Программная реализация программы.
Чуть- чуть ниже находится программный код, если ты, милый
мой друг, не хочешь разбираться сам в исходнике, то просто скатай его и
перебацей его под себя. Но мне придется все это тебе объяснить. Ну, что поехали.
Первые две строчки --
Dim mas() As Integer
Dim rasmer As Integer
объявление глобальных переменных.
ListBox1.Clear – очищение окошка, при каждом новом вводе массива.
Дальше у нас идет ввод динамического
массива, также осуществляется проверка на ввод букв и т.д. Надеюсь, как вводить
динамический массив ты знаешь, если нет - то учи, исходник перед тобой.
Так, поехали дальше. Рассмотрим
программную реализацию метода Шелла.
Что, наверно не все понятно, но ничего сейчас я тебе все
объясню и даже нарисую. Предположим у тебя есть массив из 6 элементов.
Сначала по циклу берется первый элемент массива: For i
= 0 To (rasmer - 1);
Потом начинается подцикл:
For k = i +1 To (rasmer - 1);
Дальше у нас идет сравнение и перестановка: If mas(i) > mas(k) Then
g = mas(i)
d = mas(k)
mas(i) = d
mas(k) = g
End If
Т.е. сначала 1-ый элемент массива сравнивается с
оставшимися 5-ю элементами, там где надо – перестанавливается; потом берется 2-
элемент массива и сравнивается с оставшимися 4-мя элементами массива;
соответственно 3-ий с оставшимися 3-мя и т.д.
Это все что тебе надо знать по этому методу. Удачи!!!
Метод сортировки: линейный выбор
Статья I.
Метод
предполагает наличие рабочего массива, в который помещается отсортированный
массив. Количество просмотров определяется количеством элементов массива.
Сортировка посредством линейного выбора сводится к следующему:
1.
Найти наименьший элемент, переслать его в рабочий
массив и заменить его в исходном массиве величиной, которая больше любого
реального элемента.
2.
Повторить шаг 1. На этот раз будет выбран наименьший
из оставшихся элементов.
3. Повторять шаг 1
до тех пор, пока не будут выбраны все n элементов.
Схема алгоритма приведена ниже на
рисунке 1.
Блок-схема алгоритма процедуры
сортировки
Программа алгоритма процедуры
сортировки
Dim imin As Integer
Dim amin As Integer
Dim intmax As Integer
Dim amax As Integer
Dim a(1 To 10) As Integer
Dim r(1 To 10) As Integer
Dim j As Integer
Dim p As Integer
Dim t As Integer
Dim i As Integer
Private Sub CommandButton1_Click()
ListBox1.Clear
If IsNumeric(TextBox1.Text) =
False Then
Exit Sub
Else
If t > 10 Then
TextBox1.Text = ""
Else
t = CInt(TextBox1.Text) ‘ввод размерности массива
For i = 1 To t
a(i) = InputBox("Введите"
+ Str(i) + -й элемент массива")
ListBox1.AddItem (a(i))
Next i
End If
End If
End Sub
Private Sub CommandButton2_Click()
ListBox2.Clear
For j = 1 To t
amax = a(1)
imax = 1
For i = 2 To t
If a(i) > amax Then
amax = a(i)
imax = i
End If
Next i
amin = a(1)
imin = 1
For i = 2 To t
If a(i) < amin Then
amin = a(i)
imin = i
End If
Next i
r(j) = amin
a(imin) = amax
ListBox2.AddItem (r(j))
Next j
End Sub
Private Sub CommandButton3_Click()
Unload UserForm1
End Sub
Метод челночной сортировки.
Алгоритм челночной сортировки действует точно так же , как
стандартный обмен до тех пор , пока не возникает необходимость перестановки
элементов исходного массива . Сравниваемый
меньший элемент поднимается , на сколько это возможно , вверх. Этот
элемент сравнивается в обратном порядке со своими предшественниками по
направлению к первой позиции . Если он меньше предшественника , то выполняется
обмен и начинается очередное сравнение . Когда элемент , передвигаемый вверх ,
встречает меньший элемент , этот процесс прекращается и нисходящее сравнение
возобновляется с той позиции , с которой выполнялся первый обмен . Сортировка
заканчивается когда нисходящее сравнение выходит на границу массива.
Private Sub CommandButton1_Click()
Dim k As String
Dim i As Integer
k = InputBox("Введите количество элементов массива(1-100)", "Ввод
массива")
If IsNumeric(k) = False Then
MsgBox "Я же просил ввести цифру!!!", vbCritical, "ОШИБКА"
Exit Sub
Else
razmer = CInt(k)
If razmer > 100 Then
MsgBox "Введите элемент массива 100", vbExclamation, "Сообщение"
Exit Sub
End If
End If
ReDim massiv(0 To (razmer - 1))
For i = 0 To (razmer - 1)
k = InputBox("Введите " & CInt(i + 1) & "элемент
массива", "Ввод данных")
If IsNumeric(k) = False Then
MsgBox "Вводи цифры!!!",
vbCritical, "ОШИБКА"
Exit Sub
Else
massiv(i) = CInt(k)
ListBox1.AddItem (massiv(i))
End If
Next i
End Sub
Private Sub CommandButton2_Click()
Dim temp As Integer
Dim i As Integer
Dim q As Integer
Dim u As Integer
Dim y As Integer
Dim o As Integer
ListBox2.Clear
While y < 6
For i = 0 To (razmer - 2)
u = i + 1
If massiv(i) > massiv(u) Then
temp = massiv(i)
o = massiv(u)
massiv(u) = temp
massiv(i) = o
End If
Next i
For i = (razmer - 1) To 1 Step -1
q = i - 1
If massiv(i) < massiv(q) Then
temp = massiv(i)
o = massiv(q)
massiv(q) = temp
massiv(i) = o
End If
Next i
y = y + 1
Wend
For i = 0 To (razmer - 1)
ListBox2.AddItem (massiv(i))
Next i
End Sub
Private Sub CommandButton3_Click()
End
End Sub
Метод линейной сортировки 2.
Метод предполагает наличие рабочего массива, в который
помещается отсортированный массив. Количество просмотров определяется
количеством элементов массива. Сортировка посредством линейного выбора сводится
к следующему:
1.
Найти наименьший элемент, переслать его в рабочий
массив и заменить его в исходном массиве величиной, которая больше любого
реального элемента.
2.
Повторить шаг 1. На этот раз будет выбран наименьший
из оставшихся элементов.
3.
Повторять шаг 1 до тех пор, пока не будут выбраны все
n элементов.
Текст
программы
Dim rab_massiv(), ish_massiv() As
Integer
Dim k, i As Integer
Private Sub CommandButton1_Click()
Dim v As Integer
ListBox1.Clear
k = InputBox("Введите количество элементов массива(1-50)")
If IsNumeric(k) = False Then
MsgBox "ОШИБКА ВВОДА!"
Exit Sub
Else
If k > 50 Then
MsgBox "Массив должен быть меньше
50"
Exit Sub
End If
End If
ReDim ish_massiv(0 To (k - 1))
ReDim rab_massiv(i = 0 To k - 1)
For i = 0 To (k - 1)
v = InputBox("Введите " & CInt(i + 1) &
"й элемент массива")
If IsNumeric(v) = False Then
MsgBox "ОШИБКА ВВОДА!"
Exit Sub
Else
ish_massiv(i) = v
ListBox1.AddItem (ish_massiv(i))
End If
Next i
End Sub
Private Sub CommandButton2_Click()
Dim max, min, j, y As Integer
ListBox2.Clear
max = ish_massiv(0)
For i = 1 To (k - 1)
If max < ish_massiv(i) Then
max = ish_massiv(i)
End If
Next i
max = max + 1
For j = 0 To (k - 1)
min = ish_massiv(j)
For i = 0 To (k - 1)
If min >= ish_massiv(i) Then
min = ish_massiv(i)
y = i
End If
Next i
ish_massiv(y) = max
rab_massiv(j) = min
Next j
For i = 0 To (k - 1)
ListBox2.AddItem (rab_massiv(i))
Next i
End Sub
Private Sub CommandButton3_Click()
Unload UserForm1
End Sub
Private Sub CommandButton4_Click()
ListBox1.Clear
ListBox2.Clear
End Sub
Быстрая сортировка (метод Хаара)
Суть метода заключается в следующем. Найдем такой элемент
массива, который разобьет весь массив на два подмножества: те элементы, которые
меньше делящего элемента, и те, которые по величине не меньше его (т.е. как бы
“отсортируем” один элемент, определив его окончательное местоположение).
Далее применим эту же процедуру к более коротким левому и
правому подмножествам. Таким образом, надо реализовать рекурсивный алгоритм,
который сортирует элементы множества, начиная с элемента с индексом left
Внешний вид формы.
'
Массив элементов
Private A() As
Integer
' Количество элементов
Private Count As
Long
Private Sub
QuickSort(LeftBound, RightBound As Long)
Dim PrevLeftBound,
PrevRightBound As Long
Dim Tmp As Integer
Dim MiddleValue As
Integer
If LeftBound >= RightBound Then Exit Sub
PrevLeftBound = LeftBound
PrevRightBound = RightBound
' Выбор среднего значения элемента в центре массива
MiddleValue = A((LeftBound + RightBound) \
2)
LeftBound = LeftBound - 1
RightBound
= RightBound + 1
' Пока левая граница меньше правой
Do While LeftBound
< RightBound
' Сужение левой границы
Do
LeftBound = LeftBound + 1
Loop While A(LeftBound) <
MiddleValue
' Сужение правой границы
Do
RightBound = RightBound - 1
Loop While A(RightBound) >
MiddleValue
' Если левая граница меньше правой
If LeftBound < RightBound Then
' То обменять элементы
Tmp = A(LeftBound)
A(LeftBound) = A(RightBound)
A(RightBound) = Tmp
End If
Loop
'
Вызов рекурсии для левой половины
QuickSort PrevLeftBound, LeftBound
- 1
'
Вызов рекурсии для правой половины
QuickSort
RightBound + 1, PrevRightBound
End Sub
Private Sub
CommandButton1_Click()
If Count = 0 Then
Exit Sub
End If
'
Сортировка
QuickSort 0, Count
- 1
' Вывод результата
ListBox1.List = A
End Sub
Private Sub
CommandButton2_Click()
If Not IsNumeric(TextBox1.Text) Then
MsgBox "Неверно введено количество
элементов!", vbExclamation, "Ошибка"
TextBox1.SetFocus
Else
Count = TextBox1.Value
If Count < 1 Or Count
> 1000000 Then
MsgBox "Количество элементов должно быть от 1 до 1000000!",
vbExclamation, "Ошибка"
TextBox1.SetFocus
Count = 0
Else
ReDim A(0 To Count - 1)
' Случайное заполнение массива
Randomize
For I = 0 To Count - 1
A(I) = Int(Rnd() * 1000) + 1
Next I
' Вывод результата
ListBox1.List = A
End If
End If
End Sub
Private Sub
CommandButton3_Click()
Unload UserForm1
End Sub