сопоставляться уже не как прежде, а тот, номер которого хранится в

Swaplndex. Операция перемещения вынесена за пределы внутреннего цикла и поэтому выполняется только один раз на каждом шаге внешнего цикла, т.е. всего п раз вместо потенциальных й2раз в худшем случае.

Быстрая сортировка

Степень эффективности алгоритма быстрой сортировки (Quick Sort) оценивается функцией 0(п *1п(п)), где 1п(п) - натуральный логарифм от числа п. Кривая натурального логарифма с увеличением значения аргумента растет гораздо медленнее, чем,

скажем, парабола квадратичной функции.

Алгоритм быстрой сортировки основан на подходе, обозначаемом в комбинаторной математике красочным классическим изречением разделяй-и-властвуй (divide-and-conquer). Сортируемый массив делится на части, которые анализируются и при необходимости вновь подвергаются делению. При значениях данных, близких к случайным, исходное множество делится приблизительно пополам. Если степень упорядоченности исходных данных более высока, количество операций деления множества на подмножества увеличивается, что приводит к ухудшению характеристик быстродействия алгоритма. Листинг 12.11 демонстрирует пример реализации алгоритма быстрой сортировки с помощью рекурсивной процедуры Quicksort.

Новый термин

Рекурсивной называется процедура или функция, которая полнения ссылается сама на себя.

в процессе вы-

Листинг 11. Пример реализации алгоритма быстрой сортировки

Su Sort ( ByRe ta( ) As Long Val Left As Long, ByVal Right As Long )

Dim I As Long, J As Long Dim Elem As Long

3 : 4: 5:

8 : 9:

10: 11: 12:

14: 15: 16: 17 18: 19: 20:

21:Break 22 23

24 25:

2 6 27 28 29 30 31

(Right > Left) Then Elem ta ( Right )

I = Left - 1 J = Right

Do While (True) Do

1=1+1

Loop While (Data(l) < Elem) Do

J = J - 1

If (J < LBound(Data)) Then GoTo Break Loop While (J >= LBound(Data)And Data(J) > Eiem)

If (I >= J) Then Exit Do Caii Swap ( Data, I, J )

Loop

Caii Swap( Data, I, Right ) Caii Quicksort( Data, Left, I

1 )

Call Data, I + 1, Right )

End If End Sub

33 : 34: 35: 36: 37 : 38: 39 : 40: 41:

42 :

43 :

45 : 46: 47: 48: 49: 50: 51:

52 :

53 : 54: 55: 56:

57 : 58: 59:

62: 63 :

64: 65:

Sub FillArrayAndSort(

Const Size = 10 Dim Data(Size) As Long Dim I As Long Randomize Time

For I = Lbound( Data ) To Ubound( Data

Data(I) = Rnd * Size Next I

& Time

Lbound( Data ), Ubound( Data ) ) & Time

Call Dump(Data)

Debug.Print Начало: Call Quicksort( Data, Debug.Print Конец: Call Dump( Data )

End Sub

Sub Dump(ByRef Data( ) As Integer) Dim Elem As Variant For Each Elem In Data Debug.Print Elem Next Elem End Sub

Sub Swap ( ByRe ta ( ) As Long Val I As Long Val J As Long ) Dim Temp As Long Temp = Data (I) Data(I) = Data(J) Data(J) = Temp

Debug. Print Меняем местами Data (I) & и & Data(J) End Sub

Анализ

Процедура Quicksort, текст которой размещен в строкам 30 листинга 12.11, демонстрирует высокие показатели производительности даже на больших объемах данных - так, целочисленный массив размером 100000 элементов, упорядоченных случайным образом, был отсортирован на том же компьютере менее чем за 1 секунду, на сортировку 1 миллиона чисел ушло приблизительно 10 секунд, а сортировка массива с 10 миллионами элементов потребовала 2 минуты и 4 секунды.

Функция Dump используется для вывода содержимого сортируемого массива в окне Immediate. Впрочем, ею не рекомендуется пользоваться, если количество элементов массива превышает несколько сотен.

В строках 59-65 размещен текст процедуры Swap, обращения к которой содержатся в листингах 12.9, 12 10 и 12 11. Цель наших действий пооста: создать копию значения одного элемента массива, а затем поменять содержимое двух элементов местами.

Процедура FillArrayAndSort создает массив, заполняет его случайными значениями, вызывает процедуру сортировки и выводит на экран справочные данные о времени, затраченном на решение задачи. С ее помощью можно легко протестировать рассмотренные выше процедуры сортировки методом пузырька и выбора, если заменить выражение в строке 49 соответствующим вызовом.

Строки 1-30 содержат процедуру Quicksort - это характерный случай, когда размер кода подпрофаммы может превышать пределы нескольких строк. (В принципе, процедуру Quicksort нетрудно и сократить, если вынести цикл, охватывающий строки 12-24, в отдельный именованный блок.) Интерфейс подпрофаммы (строка 1) описывается тремя па-

раметрами - именем массива и текущими значениями его нижней и верхней границ. Поскольку реализация алгоритма предполагает разбиение исходного множества на два подмножества с последующей рекурсией, аргументам присвоены имена Left (индекс левой границе! рассматриваемой части массива) и Right (индекс правой границы). В строке 3 объявлены целочисленные индексные переменные I и J. Строка 4 содержит выражение объявления переменной, тип которой совпадает с типом сортируемого массива; она используется в нескольких местах кодах для хранения содержимого граничного элемента, определяющего порядок разбиения множества на подмножества.

В строке 6 первым делом выполняется проверка того, действительно ли значение правой границы (Right) превышает величину левой (Left). В строке 8 сохраняется граничное значение, определяющее разбиение массива на части. Далее индексу I присваивается значение Left - 1, а переменной j - величина, хранимая в Right. Бесконечный цикл, охватывающий строки 12-24, используется для нахождения точек деления левой (строки 13-15) и правой (строки 17-20) половин текущего подмножества. Если значение I достигает величины J или превышает ее, выполнение цикла завершается; в противном случае элементы массива, адресуемые индексными значениями I и J, меняются местами. Процесс повторяется до тех пор, пока не выполнится условие I >= J. Далее в строке 26 вновь вызывается процедура Swap, а затем следуют

рекурсивные обращения к процедуре Quicksort для дальнейшей обработки левой и

правой половин текущего подмножества данных.

Существуют еще более сложные алгоритмы сортировки, учитывающие особенности конкретных типов и разновидностей данных. Однако их исчерпывающий анализ выходит за рамки предмета нашего обсуждения. При необходимости более подробную

информацию вы сможете найти в книге Роберта Сэджвика (Robert Sedgevick) Algorithms in С++ и в ряде других публикаций, упомянутых выше. Учтите, что во многих случаях вам придется переводить тексты примеров на язык VBA. К счастью, бизнес-приложения, для создания которых и предназначен VBA, отнюдь не исчерпываются задачами сортировки данных. Кроме того, проявив определенную настойчивость, вы наверняка сможете отыскать на Web-сайтах множество готовых решений.

Резюме

Массивы - это мощные и эффективные структуры данных, способные сохранить миллионы единиц информации и обеспечить удобные средства управления ею. Элементами массивов могут служить значения стандартнтх и пользовательских типов данных, а также объекты классов.

Главная черта массивов - простота их использования. Массивы настолько доступны, что могут применяться программистами любого уровня квалификации. Впрочем, существуют и отрицательные стороны. В ходе занятия вы усвоили, что обязательными условиями успешного применения массивов служат действия, связанные с объявлением индексных переменных и контролем за допустимыми границами их изменения. Если подобные операции станут неотъемлемой частью создаваемых вами процедур,

работа с массивами окажется значительно более эффективной и надежной.

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

концепций, лежащих в основе объектно-ориентированного подхода к программированию. Решив обратиться к массивам, доверяйте собственному опыту и интуиции, но не

ограничивайте свое творческое воображение только рамками массивов. Следующее

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