Алгоритмические языки и программирование. Игошина Л.В. - 73 стр.

(например, на диске) или в оперативной памяти. Очевидно, что с
отсортированными данными работать легче, чем с произвольно
расположенными данными. Когда элементы отсортированы, их проще найти
или определить, что их нет среди данных.
      Наиболее простыми алгоритмами сортировки считаются алгоритмы,
известные в литературе под названиями - обменная (или пузырьковая)
сортировка и сортировка выбором. Эти алгоритмы, в худшем случае, решают
задачу сортировки за время пропорциональное N2, где N - число сортируемых
элементов. Такие алгоритмы называют алгоритмами с квадратичной
сложностью. Эти алгоритмы используют, когда число сортируемых
элементов относительно не велико (до 1000). Для сортировки данных
больших объемов используют более сложные, с точки зрения реализации,
алгоритмы. Сложность этих алгоритмов определяется по формулам: N*lnN
или N*log2N. Такие алгоритмы называют алгоритмами с логарифмической
сложностью или быстрой сортировки. Эти алгоритмы используют чаще всего
при сортировке данных в оперативной памяти, например в массивах или в
динамических списках. Для сортировки данных во внешней памяти можно
использовать алгоритм сортировки слиянием. Кроме перечисленных
алгоритмов существует большое число других алгоритмов, с которыми
можно ознакомиться, например, в [2,3].


                           17.1 Сортировка выбором

      В литературе описано несколько различных модификаций сортировки
выбором, но суть их всех заключается в том, что на очередном шаге
выбирается необходимый элемент, и он помещается на заданное место в
сортируемой последовательности. Рассмотрим одну их модификаций
сортировки выбором.
      Пусть дан одномерный неупорядоченный массив, содержащий целые
числа М={mi}, i=1,n; n - число элементов. Необходимо упорядочить элементы
этого массива по возрастанию их значений.
      На первом шаге из элементов массива выбирается минимальный, и он
меняется местами с элементом, стоящем на первом месте. На втором шаге из
оставшихся неупорядоченных элементов, начиная со второго, выбирается
следующий минимальный элемент, и он меняется местами с элементом,
стоящем на втором месте. Процесс повторяется до тех пор, пока не будут
переставлены все элементы. Последний элемент можно не проверять, так как
к этому времени все элементы уже будут стоять на своих местах.
      В том случае, если требуется упорядочить элементы по убыванию их
значений, осуществляется поиск и перемещение максимального элемента.
      Рассмотрим работу алгоритма по схеме.