Пример 4.7.4-11. Разработать процедуры-Sub, в которых осуществляется сортировка по убыванию значений элементов массива.

Сделаем несколько общих замечаний по поводу сортировки элементов массива.

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

1) Упорядочивание по возрастанию. Каждый следующий элемент в массиве должен быть больше предыдущего.

2) Упорядочивание по убыванию. Каждый следующий элемент в массиве должен быть меньше предыдущего.

3) Упорядочивание по неубыванию. Каждый последующий элемент в массиве должен быть больше или равен предыдущему.

4) Упорядочивание по невозрастанию. Каждый последующий элемент в массиве должен быть меньше или равен предыдущему.

 

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

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

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

Рассмотрим «сортировку выбором» (метод «прямого выбора»).

Алгоритм и программа сортировки массива по убыванию методом «прямого выбора» приведены на рис. 4.7.4-11.

Sub Pr7411(ByRef x() As Single) Dim i, n, j, k As Integer Dim xmax As Single n = UBound(x) 'Внешний цикл сортировки For i = 0 To n - 1 xmax = x(i) k = i 'Поиск xmax и k For j = i + 1 To n If x(j) > xmax Then xmax = x(j) k = j End If Next j x(k) = x(i) x(i) = xmax Next i End Sub

Рис. 4.7.4-11. Схема алгоритма и программный код процедуры Pr7411()

Пример 4.7.4-11

 

Суть этого метода сортировки состоит в следующем.

Сортировка элементов массива по убыванию производится с помощью вложенных циклов. Сначала осуществляется поиск наибольшего элемента массива и его индекса среди всех элементов, начиная с 1-го. Найденный максимальный элемент меняется с первым элементом. Затем вновь осуществляется поиск наибольшего элемента массива и его индекса, но уже со второго элемента, и найденный максимальный элемент обменивается со 2-м элементом, и т.д. Таким образом, число найденных максимумов (поисков) равно n. При этом во внешнем цикле, начиная с первого и до предпоследнего элемента массива, сначала очередной элемент принимается за максимальный, а затем, после выполнения внутреннего цикла, обеспечи­вается заполнение этого очередного элемента массива наибольшим «среди оставшихся элементов».

Внут­ренний цикл осуществляет перебор и сравнение последующих эле­ментов, начиная с (i+1) -го до последнего элемента массива. В результате выполнения внутреннего цикла, в переменной xmax фиксируется значение наибольшего элемента, а в переменной k - его номер. Далее, во внешнем цикле выполняется перестановка найденного максимального эле­мента на место очередного i -го элемента массива.

Рассмотрим сортировку элементов массива модифицированным методом «пузырька» (прямого обмена).

Алгоритм и программа упорядочения массива по модифицированному методу «пузырька» приведены на рис. 4.7.4-12.

 

Sub Pr7412(ByRef x() As Single) Dim i, n, j As Integer Dim xx As Single n = UBound(x) For i = 0 To n-1 For j = i + 1 To n If x(i) > x(j) Then xx = x(i) x(i) = x(j) x(j) = xx End If Next j Next i End Sub

 

Рис. 4.7.4-12. Схема алгоритма и программный код процедуры Pr7412()

Пример 4.7.4-11

 

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

Продолжая таким же образом, вплоть до предпоследнего элемента, сортируют весь массив.

Обратите внимание, что в схемах алгоритмов обмен значениями обозначается символом «↔», а в примере обмен реализован через дополнительную переменную xx.