Понятие сортиравки

Пустьимеетсянеупорядоченноемножество A ={ 1, a 2,, an },эле-

ментами которого являются (целые) числа. В некоторых приложениях

требуется упорядочить элементы множества A, например, в порядке

возрастания значений этих чисел. Такую операцию называют сорти-

ровкой, а множество A определяют как массив.

Элементы a (a [i]) рассматриваются обычно как содержимое ячейки

компьютера с номером i (i = 1, 2,..., п).

В некоторых приложениях требуется упорядочить запись элементов в ячейках массива так, чтобы выполнялось соотношение a [ i ]£ a [ j ], если

i < j, где i, j —номера ячеек массива. В общем случае здесь символ £

определяет отношение порядка, т.е. не обязательно отношение сравнения чисел.

Это могут быть слова в некотором алфавите или иное. Однако для упрощения

будем предполагать, что элементами массива являются целые числа.

Процедуру упорядочивания элементов массива называютсортировкой.

Строго говоря, рассматривая элементы множества A как массив, тем

самым устанавливают порядок рассмотрения элементов этого множества в

зависимости от номера ячейки, где они расположены. Тогда сущность

сортировки состоит в перезаписи элементов массива в соответствии с заданным отношением порядка £.

Существует ряд методов упорядочения, каждый из которых предназначен для решения данной задачи. Разнообразие методов упорядочивания определяется потребностью применения наиболее эффективного метода для конкретного случая. Часто эффективность метода определяется временем,

a

i

необходимым для сортировки массива. Время сортировки напрямую зависит от

числа операций (сравнений, перезаписи элементов массива), которые

необходимо выполнить согласно принятому методу.

Отсортированный массив удобен для дальнейшего использования, так

как позволяет эффективно выполнять некоторые другие функции,

например вставку нового элемента в существующий отсортированный

массив.

Дата добавления: 2015-11-16