Сделай Сам Свою Работу на 5

Методы сортировки массивов





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

1. Количество присваивания;

2. Количество сравнений;

Все методы сортировки можно разделить на две большие группы:

1. Прямые методы сортировки;

2. Улучшенные методы сортировки;

Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три группы:

сортировка вставкой (включением)

2) сортировка выбором (выделением)

3) сортировка обменом (‘пузырьковая’ сортировка )

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



Сортировка вставкой

Принцип метода:

Массив разделяется на две части: отсортированную и не отсортированную. Элементы из неотсортированной части поочерёдно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве не отсортированной части – все остальные элементы.
Таким образом, исполнение алгоритма состоит из n -1-го прохода (n- размерность массива), каждый из которых будет включать четыре действия:

Взятие очередного i- го не отсортированного элемента и сохранение его в дополнительной переменной;

Поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
Сдвиг элементов массива от i- 1- го до j- 1- го вправо, чтобы освободить найденную позицию вставки;



Вставки взятого элемента в найденную j- ю позицию.

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

Sub sort_v()

Dim a(1 To 10) As Integer, ar As Range

Dim i As Integer, temp As Integer

Set ar = Range("A1:A10")

‘инициализация массива

For i = 1 To 10

a(i) = ar.Cells(i, 1)

Next i

'взятие элемента неотсортированной части и сохранение его в дополнительной переменной temp

For i = 2 To 10

temp = a(i)

'поиск места для temp в отсортированной части массива

For j = 1 To i - 1

If temp < a(j) Then

'сдвиг элементов отсортированной части

For k = i To j + 1 Step -1

a(k) = a(k - 1)

Next k

a(j) = temp ‘вставка элемента из неотсортированной части массива в отсортированную

j = i ‘присвоение счетчику j конечного значения для досрочного окончания цикла, т.к. место для элемента из неотсортированной части уже найдено

End If

Next j

Next i

‘вывод массива в ячейки листа MSExcel

For i = 1 To 10

ar.Cells(i, 1) = a(i)

Next i

End Sub

Пример алгоритма сортировки массива из 10-ти элементов (рис. 45):

Рис. 45. Сортировка методом вставки

 

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

Принцип метода:

Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1- го элемента до n- го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2- го до n –го элемента и меняем местами со вторым элементом.

И так далее для всех элементов до n-1- го.

Sub sort_vyb()

Dim a(1 To 10) As Integer, ar As Range

Dim i As Integer, temp As Integer

Set ar = Range("A1:A10")

‘инициализация массива



For i = 1 To 10

a(i) = ar.Cells(i, 1)

Next i

For i = 1 To 10

‘сохранение первого элемента неотсортированной части во временной переменной для обеспечения первого сравнения

temp = a(i)

k = i

'поиск минимального элемента массива

For j = i To 10

If a(j) < temp Then

temp = a(j)

k = j

End If

Next j

‘перемена мест текущего элемента с минимальным

a(k) = a(i)

a(i) = temp

Next i

‘вывод массива в ячейки MSExcel

For i = 1 To 10

ar.Cells(i, 1) = a(i)

Next i

End Sub

Пример алгоритма сортировки массива из 10-ти элементов (рис. 46):

Рис. 46. Сортировка методом выбора

 

Сортировка обменом (‘пузырьковая’ сортировка)

Принцип метода:

Выбираются 2 первых элемента массива. Если они не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n- ой позиции массива будет стоять максимальный элемент(‘всплыл’ первый ‘пузырёк’). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1- го элемента. И так далее. Всего требуется n-1 проход.

Sub sort_p()

Dim a(1 To 10) As Integer, ar As Range

Dim i As Integer, temp As Integer

Set ar = Range("A1:A10")

‘инициализация массива

For i = 1 To 10

a(i) = ar.Cells(i, 1)

Next i

‘задание цикла для n-1 проходов по всему массиву

For j = 1 To 9

‘проход по всем элементам массива, цикл задан до 9, т.к. сравниваются текущий элемент со следующим и если бы цикл был задан до 10, то 10-й элемент сравнивался бы с 11-м, которого в массиве из 10 элементов нет

For i = 1 To 9

If a(i) > a(i + 1) Then

temp = a(i) ‘сохранение i-го элемента массива во временной переменной temp

a(i) = a(i + 1) ‘присвоение i-му элементу меньшего значения i+1-го элемента

a(i + 1) = temp ‘присвоение i+1-му элементу i-го, которое ранее было сохранено в переменной temp

End If

Next i

Next j

For i = 1 To 10

ar.Cells(i, 1) = a(i)

Next i

End Sub

Пример алгоритма сортировки массива из 10-ти элементов (рис. 47):

Рис. 47. Сортировка «пузырьковым» методом

 

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


Функции

Встроенные функции

 

Функция – это встроенная формула, которая оперирует выражениями и формирует значения. Функция всегда возвращает значение, которое VBA вставляет в ту точку программы, в которой встречается имя функции. Существует два вида функций: встроенные и созданные пользователем.

Свойства функций:

· результат функции можно использовать в выражении;

· результат функции можно присвоить переменной;

· результат функции можно использовать в качестве аргумента процедуры или другой функции;

· список аргументов функции заключается в круглые скобки, аргументы функции нужно располагать в определенном порядке, через запятую;

Если какие-либо аргументы являются необязательными и не требуются для использования в данном случае, то вместо них ничего не пишется, т.е. две запятые идут подряд, без каких-либо символов между ними, в том числе пробелов.

Аргументов функции может быть один, несколько или вообще не быть. В случае отсутствия аргументов после имени функции должны следовать пустые круглые скобки.

В VBA есть несколько встроенных функций, не имеющих аргументов, например: Time (возвращает текущее время), Now (возвращает текущую дату и время).

Существует два способа передачи аргументов в функцию: перечисление через запятую или используя поименованные аргументы.

При использовании поименованных аргументов, в скобках пишется название аргумента, знак присваивания := (не путать с присваиванием переменным =), значение аргумента, например:

A = ImputBox(“введите пароль”, “запрос пароля”)

A = ImputBox(Promrt:=“введите пароль”, Title:= “запрос пароля”)

При использовании поименованных аргументов неважен порядок их указания. Для определения имен аргументов функции используется средство Auto Quick Info, которое появляется в редакторе VBA при вводе имени функции после нажатия пробела.

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

Рис. 48. Список объектов

 

Если этим способом вызвать список функций не удается, то нужно проверить, включен ли параметр Auto List Members , выполнив команду Tools → Options , а затем выбрав вкладку Editor.

Для того чтобы вызвать справку по функции нужно поставить курсор перед первой буквой имени функции и нажать клавишу F1. После этого появляется окно со справочной информацией на английском языке (рис. 49).

 

Рис. 49. Вызов справки к функции

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.