Сортировка элементов массива

Сортировкой, или упорядочиванием называется расположение этих объектов по возрастанию или убыванию согласно определённому линейному отношению порядка, такому как «≤» для чисел.

Сортировка бывает внутренней и внешней. При внутренней сортировке все сортируемые данные помещаются в оперативную память компьютера, где можно получить доступ к данным в любом порядке (то есть используется модель памяти с произвольным доступом). Внешняя сортировка применяется тогда, когда объём упорядочиваемых данных слишком большой, чтобы все данные можно было поместить в оперативную память. Здесь узким местом является механизм перемещения больших блоков данных от устройств внешнего хранения данных к оперативной памяти компьютера и обратно. Так как физически непрерывные данные надо для удобного перемещения организовывать в блочную структуру, то применяют разнообразные методы внешней сортировки.

В данной главе рассмотрим алгоритмы внутренней сортировки: метод «пузырька», метод вставками, сортировка посредством выбора и алгоритм «быстрой» сортировки. Будем предполагать, что сортируемые объекты являются целыми и действительными числами, символьными массивами, содержащими одно или несколько полей. Одно из полей, называемое ключом, имеет такой тип данных, что на нем определено отношение линейного порядка "<".

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