Простейшие методы сортировки: пузырьковая, поиском максимального элемента.

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

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

Релевантность- значимость, интерес(в рейтинге)

Пузырьковая сортировка

В первом приближении алгоритм пузырьковой сортировки можно представить как серию просмотров обрабатываемого массива таких, что при каждому просмотре элементов сравниваются между собой два соседних элемента (i и i+1) и при необходимости меняются местами.

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

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

Проходы по массиву имеет смысл повышать до тех пор, пока не выполнится одно из двух условий:

-1) Во время последнего прохода по массиву не было сделано ни одного обмена элементами (массив отсортирован).

-2)Сделано уже n-1 проходов по массиву.

Sub Puz_sort (M As Integer, x() As Integer)

Dim i As Integer, MM As Integer, k As Integer, temp As Integer

MM=M

iter:

k=0

For i=2 to MM ‘Начало внутреннего цикла

If x(i)<x(i-1) then

k=1

temp=x(i):x(i)=x(i-1):x(i-1)=temp ‘Конец внутреннего цикла

End if

Next i

MM=MM-1

If k=1 then GoTo iter ‘ Внешний цикл)

End Sub

x() - массив (с неопределённой длиной)
Dim..Объявление локальных переменных

k→k=1

Если значение переменной не равно нулю, то оно трактуется как истина.

12.. Если значение переменной равно нулю, то оно трактуется как ложь.

Сортировка поиском максимального элемента.

Private Sub knopka()

Dim i As Integer, j As Integer, k As Integer, n As Integer

Dim a() As Integer

n=10

ReDim a(n) ←(Отводит память под массив)

For i=1 to n ‘Cоздаёт массив,

a(i)=Int(100*Rnd) заполненный рандомными

cells(i,1)=a(i) элементами)

Next i ‘Сортировка *(Rnd-псевдо случайное число,

Call MaxSoft(n,a()) Int-целые)

For i=1 to n ‘Записывает в ячейки результат,

Cells(i,4)=a(i) чтобы мы увидели, что он отсортирован

Next i

End Sub

MaxSoft-Получает значение через параметры n и a, выполняет работу сортировки и результат сортировки возвращает через эти же параметры в главную программу.

Sub MaxSoft (n As Integer, a() As Integer)

Dim i As Integer, j As Integer, k As Integer

Dim iMax As Integer, aMax As Integer

For j=n to 2 step -1

aMax=a(1):iMax=1

For i=2 to j

If a(i)>aMax then

aMax=a(i)

iMax=i

End If

Next i

k=a(j):a(j)=a(iMax):a(iMax)=k ‘Обмен элементов местами

Next j

End Sub

Схематическое описание сортировки поиском максимального значения.

Алгоритм сортировки поиском максимального значения схематично можно представить, как серию укорачивающихся просмотров исходного массива (внешний цикл). Во время каждого из таких просмотров ищется максимальный элемент и ставится на последнее, предпоследнее и т.д. место (в зависимости от номера просмотра). При последнем просмотре массива проверяются только 2 первых элемента.

-Обе сортировки одинаково формируют множество уже отсортированных элементов, которое будет расти с конца массива к началу от самого большого элемента к самому маленькому (внешне одинаковы).

-Количество сравнений одинаково в обеих сортировках.

-В пузырьковой сортировке обмениваются 2 соседних числа, а в сортировке поиском максимального значения …….?

с числом, выполняющим роль максимального.

-В пузырьковой сортировке обменом больше.

13. Двумерные массивы …

При работе с таблицами часто нужно применить одну и туже операцию к целому диапазону ячеек или выполнить расчеты по формулам,зависящим от большого массива данных,к таким задачам относятся,например,умножение матрицы на матрицу или умножение матрицы на число.Для решения таких задач в exelе можно исп.массивы. Диапазон массива-это блок ячеек,который имеет общ. Формулу массива. Двумерный массив - это одномерный массив, элементами которого являются одномерные массивы. Другими словами, это набор однотипных данных, имеющий общее имя, доступ к элементам которого осуществляется по двум индексам. Наглядно двумерный массив удобно представлять в виде таблицы, в которой n строк и m столбцов, а под ячейкой таблицы, стоящей в i-й строке и j-м столбце понимают некоторый элемент массива a[i][j]. По-другому двумерный массив также называют матрицей, а в том случае, когда n=m.

Умножение матрицы на вектор
Пример. Дана матрица А(2,3) и вектор В(3). Найти произведение А*В.
Программа
Sub UmnMatNaVec()
Dim a(2, 3) As Single, b(3) As Single, c(2) As Single
Dim s As Single, i, j As Integer
'ввод матрицы
For i = 1 To 2
For j = 1 To 3
a(i, j) = Cells(i + 1, j)
Next j
Next i
'ввод массива
For i = 1 To 3
b(i) = Cells(4, i + 1)
Next i
For i = 1 To 2
s = 0
For j = 1 To 3
s = s + a(i, j) * b(j)
Next j
c(i) = s
Next i
'вывод нового массива b(5)
Cells(6, 1) = "Массив c(2)"
For i = 1 To 2
Cells(6, i + 1) = c(i)
Next i
End Sub

Дата добавления: 2015-11-13