Основы алгоритмизации и программирования. Часть вторая. Типовые алгоритмы обработки массивов. Асламова В.С - 20 стр.

Таблица 4. Пример сортировки по убыванию                                                 Простой выбор
Номер элемента         1     2      3      4     5    6     7      8   9                       Найдем в массиве минимальный элемент и поменяем его местами с
Последовательность     5     11     82     21    9    7     12     6   22                первым элементом. Те же действия выполним с оставшимися (без
Отсортированный                                                                          первого) n–1 элементами массива, затем с n–2 элементами и так далее, до
                       82    22     21     12    11   9     7      6   5                 тех пор, пока не останется один последний элемент, он и будет
по убыванию
                                                                                         наибольшим элементом.
      Сортировка массивов символьного типа обычно заключается в
упорядочении элементов массива по алфавиту (Таблица 5).                                  Таблица 6. Числовой пример алгоритма

Таблица 5. Пример сортировки массива символьного типа                                    Номер элемента                   1    2    3    4    5    6    7    8    9
                                                                                         Исходный массив                  82   31   22   16   7    12   63   29   54
Номер элемента         1     2           3      4     5          6     7     8     9                                  9   7    31   22   16   82   12   63   29   54
Последовательность     сон   шаг         год    тон   фон        ель   дол   рот   лак                                8   7    12   22   16   82   31   63   29   54
Отсортированный                                                                                                       7   7    12   16   22   82   31   63   29   54
                       год    дол        ель    лак   рот        сон   тон   фон   шаг           После выбора
по возрастанию                                                                                                        6   7    12   16   22   82   31   63   29   54
                                                                                              минимального среди
                                                                                                                      5   7    12   16   22   29   31   63   82   54
      Метод сортировки называется устойчивым, если он не изменяет                              правых элементов
                                                                                                                      4   7    12   16   22   29   31   63   82   54
порядок следования элементов с равными значениями.
                                                                                                                      3   7    12   16   22   29   31   54   82   63
      Сортировку можно рассматривать как самостоятельную задачу                                                       2   7    12   16   22   29   31   54   63   82
(например, для получения упорядоченного по алфавиту телефонного                          Упорядоченный массив             7    12   16   22   29   31   54   63   82
справочника) и как вспомогательную (для облегчения последующего                                Обратимся к листу опорного сигнала №3 (Рисунок 22.). Здесь
поиска элементов в упорядоченном массиве). Известные алгоритмы                           представлен метод выбора для последовательности шкатулок различной
сортировки данных, находящихся в оперативной памяти, разнообразны.                       величины. Две первых шкатулки уже упорядочены. Затем отыскивается
                                                                                         минимальная шкатулка среди остальных шкатулок последовательности.
По словам Н. Вирта “ можно построить целый курс программирования,
                                                                                         Если встречаются одинаковые шкатулки, то отыскивается первая среди
выбирая примеры только из задач сортировки”. Основное требование к                       минимальных, таким образом, достигается устойчивость сортировки. Она
методам – это экономное использование памяти. То есть все перестановки,                  меняется местами с третьей шкатулкой (“Малыш, давай меняться!”).
приводящие элементы в требуемый порядок, должны выполняться на том                             При составлении алгоритма следует обратить внимание на то, что
же месте (без вспомогательных массивов). При этом нужно помнить, что                     для получения результата необходимо n–1 раз находить минимальное
первоначальный вид массива после обработки не сохраняется.                               значение в массиве, размер которого уменьшается. Первый раз ищем
                                                                                         минимум среди элементов А[1], А[2],     , А[ n ], во второй раз ищем
       В данном пособии рассматриваются только три наиболее простых                      минимум среди элементов А[2], , А[ n ], в i-тый раз среди А[ i ], , А[n].
способа сортировки. Практически все другие методы упорядочения                           После нахождения минимального элемента, значение которого будем
являются комбинацией этих трех. Быстродействие описываемых методов                       хранить в переменной x, его нужно поменять местами с определенным
для небольших размеров массива примерно одинаково. Все методы                            элементом массива. Необходимо запоминать номер минимального
                                                                                         элемента в переменной k. Блок-схема алгоритма простого выбора
рассчитаны на сортировку одномерных массивов. При необходимости
                                                                                         представлена на Рисунке 23.
двумерный массив можно представить одномерным путем пересчета
индексов. Будем рассматривать упорядочение исходного массива А[ 1 ],
А[ 2 ], , А[ n ] по возрастанию. Переход к сортировке по убыванию не
представляет труда.

                                                                                   39    40