Лабораторная работа № 8.
Тема: «Алгоритми сортування»
Теоретические сведения. Наиболее широко известная структура данных - массив. Массив состоит из компонент одного типа, называемого базовым. Поэтому структура массивов однородна. Кроме того, массивы относят к так называемым структурам с прямым доступом. Для того чтобы обозначить отдельную компоненту, к имени всего массива добавляется индекс. Индекс - это значение специального типа, определенного как тип индекса массива. Количество индексов называется размерностью массива. Отметим, что в памяти ПЭВМ каждой компоненте массива отводится отдельное поле равных размеров, при этом, все элементы массива расположены подряд.
Если х является переменной-массивом размерности n, то отдельная компонента обозначается с помощью имени массива, за которым следует индекс требуемой компоненты – хi. Иногда компоненты массивов называют переменными с индексами.
Обычный прием работы с массивами, в особенности с большими массивами – выборочное изменение отдельных его компонент, а не конструирование полностью нового составного значения. При этом переменная-массив рассматривается как массив составляющих переменных, и возможно присваивание значений отдельным компонентам, например, хi ← 0.456.
Сортировка массивов. В общем случае сортировку следует понимать как перегруппировку заданного множества объектов (массива, файла и т.д.) в некотором порядке. Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве. Выбор алгоритма сортировки зависит от структуры обрабатываемых данных. Рассмотрим основные методы сортировки применительно к одномерным массивам.
Дан одномерный массив размерности n: a0, a1,…, an-1. Сортировка данного массива есть перестановка его элементов в массив где при некоторой упорядочивающей функции f
выполняются отношения
Обычно упорядочивающая функция не вычисляется, а хранится как явная компонента каждого элемента. Ее значение называется ключом элемента. Основное условие при выборе метода сортировки массивов – выбранный метод должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте («in site»). Методы сортировки «in site» можно разбить в соответствии с определяющими их принципами на три основные типа – сортировка с помощью прямого включения; сортировка с помощью прямого выбора; сортировка с помощью прямого обмена.
Сортировка с помощью прямого включения (вставкой).
Сортировка вставкой напоминает способ, к которому прибегают игроки для сортировки имеющихся на руках карт. Пусть вначале в левой руке нет ни одной карты, и все они лежат на столе рубашкой вверх. Далее со стола берется по одной карте, каждая из которых помещается в нужное место среди карт, которые находятся в левой руке. Чтобы определить, куда нужно поместить очередную карту, ее масть и достоинство сравнивается с мастью и достоинством карт в руке. Допустим, сравнение проводится в направлении слева направо. В любой момент времени карты в левой руке будут рассортированы, и это будут те карты, которые первоначально лежали в стопке на столе.
Псевдокод сортировки методом вставок представлен ниже под названием Insertion__sort. На его вход подается массив А [1..п], содержащий последовательность из п сортируемых чисел (количество элементов массива А обозначено в этом коде как length [A].) Входные числа сортируются без использования дополнительной памяти: их перестановка производится в пределах массива, и объем используемой при этом дополнительной памяти не превышает некоторую постоянную величину. По окончании работы алгоритма inserti0n_s0rt входной массив содержит отсортированную последовательность: