Главная страница / 25. Типовые алгоритмы: 25.8. Алгоритмы упорядочи...
25.8. Алгоритмы упорядочивания элементов в массивах
| ← 25.7. Поиск минимальных или максимальных... | 25.9. Умножение матрицы на вектор и матрицы на... → |
Алгоритмы упорядочивания элементов одномерных массивов по возрастанию или убыванию их величины (сортировки) являются одними из важнейших в программировании. Существует достаточно много различных алгоритмов сортировки; здесь рассматривается только два из них.
Первый алгоритм достаточно прост по сути – он строится на основе изложенного в разделе 25.7. Рассмотрим его на примере упорядочивания по возрастанию n элементов одномерного массива X. Он основан на следующих действиях.
Сначала находится минимальный элемент массива. Этот элемент >Xm c индексом im обменивается местами с первым. Затем находится новый минимальный элемент в ряду от второго до последнего. Он обменивается местами со вторым. И так далее. Цикл поиска и обмена местами повторяется до предпоследнего элемента, т.е. n-1 раз. Блок-схема этого алгоритма представлена на рис. 25.15.
Если найденный минимальный элемент совпадает с начальным элементом поиска, то их не нужно обменивать местами. Но для некоторого упрощения в блок-схеме исключена проверка этого случая и сохранен обмен элемента с самим собой. Обмен элементов местами производится через вспомогательную переменную tmp.
Проанализируем работу этого алгоритма на примере массива из четырех элементов:
При первом исполнении основного цикла будет найден минимальный четвертый элемент и обменен местами с первым:
При втором прохождении будет найден минимальный третий элемент и обменен местами со вторым:
И наконец, при последнем прохождении цикла будет найден минимальный четвертый элемент, обменен местами с третьим и все элементы окажутся упорядочены.
Рис. 25.15. Сортировка элементов одномерного массива
(упорядочивание по возрастанию)
Более эффективен другой алгоритм сортировки, называемый пузырьковым. Его блок-схема приведена на рис. 25.16. Он более компактный, чем предыдущий. Проанализируем его работу на таком же примере. Для наглядности изобразим вертикальное расположение ячеек массива при возрастании номера сверху вниз.
Рис. 25.16. Сортировка элементов одномерного массива
(упорядочивание по возрастанию пузырьковым методом)
Исходное состояние элементов массива следующее:
При первом исполнении тела внешнего цикла внутренний цикл будет исполняться трижды. При этом сначала обменяются местами третий и четвертый элементы, затем – второй и третий и, наконец, первый и второй. В результате этих обменов элемент массива, равный единице, как пузырек воздуха, всплывает вверх:
При втором исполнении тела внешнего цикла внутренний цикл будет исполняться 2 раза. Сначала обменяются местами третий и четвертый элементы, а затем – второй и третий.
При последнем исполнении тела внешнего цикла внутренний цикл исполняется один раз и в нем переставляются местами третий и четвертый элементы;
Сортировка завершена.
Алгоритмы упорядочивания матриц оказываются более сложными. Приведем в качестве примера алгоритм перестановки строк матрицы, в результате которой средние значения элементов по строкам возрастают от первой строки до последней. Он представлен на рис. 25.17.
Рис. 25.17. Сортировка строк матрицы: в результате сортировки средние значения по строкам
возрастают от первой строки к последней
Матрица A имеет m строк и n столбцов. Сначала в цикле по индексу строки i рассчитываются средние значения по строкам; их значения записываются в массив S. Затем сортируются элементы массива S по возрастанию первым из описанных выше методом. При перестановке элементов массива S одновременно переставляются связанные с ними строки матрицы. После окончания сортировки массива S все строки матрицы A оказываются упорядочены нужным образом.
Второй алгоритм, представленный на рис. 25.18, упорядочивает элементы матрицы A из m строк и n столбцов так, чтобы они возрастали как по строкам, так и по столбцам. Для этого используется вспомогательный одномерный массив X. Сначала элементы матрицы A по строкам переписываются в одномерный массив X, затем упорядочиваются там пузырьковым методом и переписываются обратно в той же последовательности по строкам. При переписывании данных из двумерного массива в одномерный и обратно использованы два разных способа установления соответствия индексов двумерного и одномерного массивов. В первом случае индекс одномерного массива формируется как счетчик, который сначала обнуляется, а в теле цикла перезаписи увеличивается на единицу. Во втором случае используется соответствие индексов i (строки) и j (столбца) матрицы и индексу k одномерного массива:
k = j + (i - 1)·n
Оба этих способа эквивалентны. На блок-схеме фрагмент упорядочивания одномерного массива не детализирован, так как он совпадает с приведенным на рис. 25.16.
Для исполнения этой задачи может быть предложен более оптимальный алгоритм, не использующий одномерный массив и представляющий собой двумерный вариант алгоритма на рис. 25.15. Однако приведенный вариант с одномерным массивом полезен тем, что показывает приемы перезаписи элементов из двумерного массива в одномерный и обратно – иногда это требуется при разработке алгоритмов.
Рис. 25.18. Сортировка строк матрицы: в результате сортировки
элементы возрастают как по строкам, так и по столбцам
| ← 25.7. Поиск минимальных или максимальных... | 25.9. Умножение матрицы на вектор и матрицы на... → |