Что еще следует знать о массивах

Массивы просты в использовании, но не достаточно надежны. Чтобы ладить с ними, вы должны ясно осознавать и четко выполнять несколько несложных правил.

Прежде чем обратиться к элементу массива по индексу, вы должны гарантировать попадание последнего в допустимый интервал. Функции Lbound и Dbound - вот ваши надежные помощники.

При использовании глобальных массивов создайте отдельные функции для выполнения операции измепепия их размеров и проверки правильности индексов. Хотя подобные

функции окажутся небольшими по объему, ваша программа приобретет ясность и управляемость - ведь один фрагмент кода исправить гораздо легче, чем несколько, верно?

Сортировка данных

Массивы - простой и удобный инструмент хранения и логической организации

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

Проблемам сортировки посвящено достаточное количество статей, монографий и учебников. Классикой жанра считается Numerical Recipes in С: The Art of Scientific Computing Уильяма Пресса (William H. Press) (издательство Cambridge University Press, 1993). Названная работа содержит исчерпывающий свод подробных описаний самых разнообразных алгоритмов и их реализаций на языке программирования С. Существуют и публикации, которые специально ориентированы на читателя, нуждающегося в готовых решениях на языке Visual Basic. Например, обратившись к книге Ready-To-Run Visual Basic Algorithms Рода (Rod) и Кеннета (Kenneth) Стефензов (Stephens) (издательство John Wiley & Sons, 1998), вы сможете пользоваться приведенной информацией непосредственно, не прибегая к исправлению текста функций или его трансляции с одного языка программирования на другой. (В числе лучших книг следует упомянуть всемирно известную монографию Дональда Кнута (Donald Е. Knuth) Искусство программирования, т.З. Сортировка и поиск. - М.: Изд. дом Вильяме , 2000. - Прим. перев.).

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

быстрой сортировки , с другой, существенно возрастают.

Сортировка методом пузырька

Алгоритм пузырька (Bubble Sort) - неплохой выбор в том случае, если объем массива не превышает 10000 элементов и данные уже в достаточной мере отсортированы. Если говорить кратко, метод состоит в сопоставлении содержимого каждой пары элементов массива и обмене их местами в случае успешного результата сравнения. При выполнении сортировки по возрастанию значение элемента с индексом / сопоставляется с содержимым следующего элемента - i+l. Если первая величина превосходит вторую, элементы меняются местами. Чтобы изменить порядок сортировки (т.е. получить массив, упорядоченный по убыванию), достаточно вместо оператора

сравнения больше (>) использовать оператор меньше (<). Пример процедуры сортировки, реализующей метод пузырька , приведен в листинге 12.9.

Листинг 12.9. Пример сортировки массива с помощью метода пузырька

2 3 4 5 6 7 8 9 10: 11 12 13 14 15: 16 17: 18: 19: 20: 21 22: 23 : 24 25 26 27 28 29 30 31 32 33 34 35

Su ef Data О As Long Val I As Long Val 0 As Long) Dim Temp As Long Temp = Data (I) Data (I) = Data (J) Data{J) = Temp

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

End Sub

Sub BubbleSort (ByRe a() As Long) Dim I As Long, J As Long

For I = Lbound( Data ) To Ubound( Data ) - 1 For J = I + i To Ubound( Data )

If (Data(I) >Data(J)) Then

Call Swap ( Data, I, J ) End If Next J

Next End Sub

Sub FillArrayAndSort0

Const Size = 10 Dim Data(Size) As

Dim I As Long

Randomize Time For I = LBound(Data) Data(I) = Rnd *

Next I

Long

Size

Debug.Print Начало работы: Caii BubleSort(Data) Debug.Print Конец работы:

End Sub

& Time

& Time

II Для выполнения сортировки по методу пузырька необходимо иметь I два целочисленных индекса - I и J. Строка 11 содержит заголовок внешнего цикла, а строка 12 - внутреннего. Чтобы сопоставить значение каждого /-Г0 элемента массива с содержимым ; + /-го элемента, необходимы именно два цикла. Обратите внимание на начальное значение переменной внутреннего цикла - J = I + 1 (строка 12). Строка 13 выполняет сравнение значений элементов а (I) a(J). В случае удачи (когда значение предьщущего элемента окажется большим очередного последующего) элементы меняются местами - эта операция выполняется с помощью процедуры Swap. Чтобы протестировать подпрограмму сортировки, выполните процедуру FillArrayAndSort.

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

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

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

Процедура сортировки методом пузырька в изложенной выше редакции, примененная к массиву из 10000 целых чисел, выполняется на компьютере Intel Pentium 800 с

256 Мбайт оперативной памяти приблизительно 51 секунду. Возможно, это мало о чем

говорит, но подобная информация вам пригодится, так как такая скорость работы вполне может устроить. В терминах теории вычислительной сложности алгоритмов степень эффективности метода пузырька оценивается функцией 0(п2). Другими словами, время решения задачи - это квадратичная функция от ее размерности (и в данной ситуации равно числу элементов массива), поскольку в худшем случае программе предстоит выполнить п2 операций сравнения. При размерности задачи, равной 10000, количество операций сравнения ограничено величиной 100000000. Ясно, что при дальнейшем росте п вам вряд ли поможет даже самый производительный компьютер.

Сортировка посредством выбора

Для алгоритма сортировки посредством выбора (Selection Sort) справедлива та же оценка эффективности, зависящая от размерности задачи, что и для метода пузырька , - О( п2). Отличие метода сортировки посредством выбора состоит в том, что перестановка элементов массива выполняется только в случае, когда найдена точная позиция текущего элемента относительно остальных. Метод пузырька же предполагает перемещение элементов при любом успешном результате теста сравнения.

Листинг 12.10 содержит текст процедуры, реализующей алгоритм сортировки посредством выбора. Как и в предыдущем примере, представлены неплохие результаты при числе элементов, не превосходящем 10000, но с ростом размерности задачи показатели производительности заметно ухудшаются.

Листин .10. Пример сортировки массива посредством выбора

1: Sub SelectionSort(ByRef Data ( ) As Long)

2: Dim I As Integer, J As Integer, Swaplndex As 3: For I = Lbound(Data) To Ubound(Data) - 1

4: Swaplndex = I

5: For J = I + 1 To Ubound( Data )

6: If (Data(Swaplndex) > Data(J)

7 : Swaplndex = J

8: End If

9: Next J

10: Call Swap (Data, I, Swaplndex)

11: Next I 12:End Sub

Integer

Then

На том же компьютере на сортировку 10000 числовых элементов с помощью алгоритма выбора было затрачено около 19 секунд - налицо повышение эффективности работы примерно на 40%. Рост производительности существенно зависит от числа реально выполняемых перемещений элементов, что, в свою очередь, определяется характеристиками относительной упорядоченности исходного множества данных. Алгоритмы отличаются незначительно. Обратите внимание на дополнительную переменную Swapln-dex, объявленную в строке 2. В строке 4 она получает текущее значение I. В строке 7 вместо слепого перемещения элементов запоминается текущее значение индекса J, для которого тест сравнения дал положительный результат. Па очередном шаге внутреннего цикла с J-м элементом будет