Сортировка

Сортировка – расположение данных в памяти ЭВМ в регулируемом виде по их ключам. При обработке данных важно знать информационное поле данных и размещение их в машине. Различают внутреннюю и внешнюю сортировку. Внутренняя – сортировка в оперативной памяти. Внешняя - сортировка во внешней памяти. Если сортируемые записи занимают большой объем памяти, то их перемещение требует больше затрат. Для уменьшения затрат применяют метод сортировки таблицы адресов. Производится перестановка указателей, сам массив при этом не перемещается. При сортировке могут встречаться одинаковые ключи данных, в этом случае одинаковые ключи лучше расположить после сортировки в том же порядке, что и в исходном файле. Эффективность сортировки определяется:

1. Временем, затраченным на сортировку

2. Объемом оперативной памяти

3. Временем, затраченным на написание программы

Порядок числа сравнения при сортировке определяется в пределах от О (nlogn) до О (n²). Сортировки классифицируются:

1. Строгие (прямые): прямое включение, прямой выбор, прямой обмен

2. Улучшенные

Сортировка методом прямого включения.

Элементы мысленно делятся на готовую последовательность a₁,…,a_i-1­. В готовой последовательности элементы располагаются по возрастанию или убыванию. В исходной, располагаются элементы, которые нужно отсортировать. При каждом шаге элементы исходной последовательности уменьшаются на 1, а в готовой увеличиваются. То есть i элемент извлекается из исходной последовательности и перекладывается в готовую, при этом он вставляется на нужное место среди элементов готовой последовательности.

Пример: 10,3,11,8,2,15,44,9.

Шаг	Готовая последовательность	Исходная последовательность
1	10	3,11,8,2,155,44,9
2	3,10	11,8,2,15,44,9
3	3,10,11	8,2,15,44,9
4	3,8,10,11	2,15,44,9
5	2,3,8,10,11	15,44,9
6	2,3,8,10,11,15	44,9
7	2,3,8,10,11,15,44	9
8	2,3,8,9,20,11,15,44	-

В данной сортировке на первом шаге элемент 10 является началом готовой последовательности. Элементы сравниваются с первым элементом готовой последовательности и занимают свое место справа или слева от первого элемента.

Эффективность сортировки прямого включения.

Если последовательность отсортирована в нужном порядке, то максимальное число сравнений может возникнуть на i шаге, и определяется по формуле: C_­max­ = i – 1; C_­min­ = 1. Если равновероятны все перестановки, то среднее число сравнений определяется: C_­cp ­= i/2. Число перестановок: ­m_­i­ = i + 3. Если массив отсортирован в обратном порядке, то число сравнений определяется по формуле:

C_­max­ = n(n-1)/2. Данный случай – наихудший. Количество перестановок определяется: m_­max­ = C_­max­ + 3(n-1).

Пример: имеется последовательность: 42,7,12,32,35,7. Отсортировать в порядке возрастания, определить максимальное число сравнений.

шаг	Готовая последовательность	Исходная последовательность
1	42	7,12,32,35,7
2	7,42	12,32,35,7
3	7,12,42	32,35,7
4	7,12,32,42	35,7
5	7,12,32,35,42	7
6	7,7,12,32,35,42	-

C_­max ­= 6 - 1 = 5

Пример: имеется последовательность: 12,4,18,24. Отсортировать в порядке убывания, определить количество перестановок.

шаг	Готовая последовательность	Исходная последовательность
1	12	4,18,24
2	12,4	18,24
3	18,12,4	24
4	24,18,12,4	-

m_­max­ = 6­ + 3(4-1) = 15

Пример: имеется последовательность: 4,9,43,52,17,20,76. Отсортировать в порядке возрастания, определить минимальное число сравнений.

шаг	Готовая последовательность	Исходная последовательность
1	4	9,43,52,17,20,76
2	4,9	43,52,17,20,76
3	4,9,43	52,17,20,76
4	4,9,43,52	17,20,76
5	4,9,17,43,52	20,76
6	4,9,17,20,43,52	76
7	4,9,17,20,43,52,76	-

C_­min­=1

Пример: имеется последовательность: 13,99,15,32,9,68,102. Отсортировать в порядке возрастания, определить число перестановок, определить максимальное число сравнений.

шаг	Готовая последовательность	Исходная последовательность
1	13	99,15,32,9,68,102
2	13,99	15,32,9,68,102
3	13,15,99	32,9,68,102
4	13,15,32,99	9,68,102
5	9,13,15,32,99	68,102
6	9,13,15,32,68,99	102
7	9,13,15,32,68,99,102	-