- •2.1 Словесная запись алгоритма.
- •2.2 Графическая запись алгоритма.
- •4.1 Полная и сокращенная формы ветвления.
- •4.2 Применение сложных условий.
- •4.1 Арифметические операции и выражения
- •4.2 Функциональные операции
- •4.3 Операции отношения
- •4.4 Логические операции
- •4.5 Строковые операции
- •1. Цикл For…Next.
- •2. Оператор Do...Loop
- •3. Оператор While...Wend
- •NameList — наименование списка, задаваемое свойством Name;
- •Выражение — элемент списка. Если это символьная величина, то она должна быть помещена в кавычки;
- •NameList — наименование списка, задаваемое свойством Name;
- •Выражение — элемент списка. Если' это символьная величина, то она должна быть помещена в кавычки;
- •Index — порядковый номер элемента в списке.
- •Сортировка массива. Способы сортировки массива.
- •Сортировка вставкой. Сортировка выбором.
- •Сортировка методом простого обмена (пузырька). Рекурсивная сортировка.
- •Сортировка методом слияний.
- •Функции обработки строковых выражений.
- •InStrRev(Исходная_Строка, Искомая_Строка [, Начальная_Позиция])
Сортировка массива. Способы сортировки массива.
Для решения многих задач удобно сначала упорядочить данные по определенному признаку, так можно ускорить поиск некоторого объекта. Например, в преферансе игроки раскладывают карты по мастям и по значению. Так легче определить, каких карт не хватает. Или возьмем любой энциклопедический словарь - статьи в нем упорядочены в алфавитном порядке.
Перегруппирование заданного множества объектов в определенном порядке называют сортировкой.
Почему сортировке уделяется большое внимание? Вы это поймете, прочитав цитаты двух великих людей.
"Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования." /Д. Кнут/
"Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки." /Н. Вирт/
Отличительной особенностью сортировки является то обстоятельство, что эффективность алгоритмов, реализующих ее, прямо пропорциональна сложности понимания этого алгоритма. Другими словами, чем легче для понимания метод сортировки массива, тем ниже его эффективность.
Сегодня существует множество методов сортировки, но для понимания сути сортировки рассмотрим некоторые из них.
Но прежде чем перейти к рассмотрению конкретного алгоритма той или иной сортировки немного вспомним материал, который пригодится нам в дальнейшем.
Задача. Составить фрагмент программы поиска максимального числа из трех введенных с клавиатуры чисел.
Пусть а, b, c - вводимые с клавиатуры числа, Max - максимальное из их значений. На первом шаге предположим , что а - максимальное из чисел и поэтому Max:=a. Затем сравним значение предполагаемого максимума со значениями переменных b и с. Если значение m окажется меньше, чем значение очередной переменной, то переопределим значение максимума.
Private Sub Command1_Click()
Cls
a = Val(Text1.Text)
b = Val(Text2.Text)
c = Val(Text3.Text)
Max = a
If Max < b Then
Max = b
End If
If Max < c Then
Max = c
End If
Print Max
End Sub
Задача. Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.
Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива.
Private Sub Command1_Click()
Cls
Dim I As Integer
Dim x(100) As Integer
For I = 1 To 10
x(I) = Rnd() * 100
Next I
Max = x(1)
For I = 2 To 10
If Max < x(I) Then
Max = x(I)
End If
Next
Print Max
For I = 1 To 10
Print x(I);
Next I
End Sub
Практически каждый алгоритм сортировки можно разбить на три части:
сравнение, определяющее упорядоченность пары элементов;
перестановку, меняющую местами пару элементов;
собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены.
Ниже кратко описаны некоторые алгоритмы сортировки.
Метод пузырька (обменная сортировка с выбором)
Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.
Сортировка выбором
На этот раз при просмотре мaccива мы будем искать наименьший элемент, Сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив.
Метод Шелла
Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).
Метод Хoopа
Этот метод, называемый также быстрой сортировкой(QuickSort), был разработан в 1962 г. (его разработал Charles Antony Richard Hoare).Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.