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