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

      Комментарии к записи Пример 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 IntegerDim xmax As Singlen = UBound(x)’Внешний цикл сортировкиFor i = 0 To n — 1xmax = x(i)k = i’Поиск xmax и kFor j = i + 1 To nIf x(j)xmax Thenxmax = x(j)k = jEnd IfNext jx(k) = x(i)x(i) = xmaxNext iEnd 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 IntegerDim xx As Singlen = UBound(x)For i = 0 To n-1For j = i + 1 To nIf x(i)x(j) Thenxx = x(i)x(i) = x(j)x(j) = xxEnd IfNext jNext iEnd Sub

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

Пример 4.7.4-11

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

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

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

Статьи к прочтению:

Курсы программирования. Алгоритм №10. Сортировка массива по возрастанию и убыванию


Похожие статьи: