Алгоритм построения пирамиды

1. Полагаем

2. Если i < 0, алгоритм завершен.

3. «Протаскиваем» a [0] через пирамиду, ему подчиненную.

4. Уменьшаем i на единицу.

 

Рассмотрим построение пирамиды на примере.

Массив A = {55, 28, 14, 83, 17, 19, 41, 30, 9, 21} будем превращать в пирамиду. «Протаскиваемый» элемент выделен красным цветом, элементы с которыми на данном этапе происходит сравнение – синим. Траектория «протаскивания» выделена зеленым.

 

 

 

 

Полученный массив-пирамида A = {83, 55, 41, 28, 21, 19, 14, 30, 9, 17}

 

Блок-схема построения пирамиды

 

 

Перейдем ко второму этапу алгоритма – собственно сортировке.

 

Алгоритм пирамидальной сортировки

1. Если N = 1, алгоритм завершен.

2. Меняем местами a [0] и a [ N –1]

3. Уменьшаем N на единицу.

4. «Протаскиваем» a [0] через пирамиду a [0],…, a [ N –1] и идем на шаг 1.

 

Рассмотрим построение пирамиды на примере.

Отсортируем массив A = A = {83, 55, 41, 28, 21, 19, 14, 30, 9, 17}. «Протаскиваемый» элемент выделен красным цветом, элементы с которыми на данном этапе происходит сравнение – синим. Упорядоченная часть массива выделена зеленым.

 

 

 

 

 

 

 

 

 

 

 

Блок-схема алгоритма

 

 

Пирамидальная сортировка очень эффективна при больших значениях N. В самом плохом из возможных случае оценка алгоритма N log₂ N. Отличная производительность алгоритма в самых плохих случаях – одно из привлекательных свойств алгоритма.

 

Сортировка Хоара (быстрая)

 

Рассмотрим алгоритм сортировки, предложенной Хоаром, называемой еще быстрой сортировкой. В этом алгоритме исходят из того соображения, что наибольшая эффективность достигается при перестановках на большие расстояния в самом начале работы. Суть алгоритма состоит в следующем: определив в качестве эталона некоторое значение x, массив a [ L ], a [ L+ 1], …, a [ R– 1], a [ R ] можно разделить на 3 части:

1) все элементы a [ i ], меньшие либо равные x, i = - левый фрагмент,

2) a [ i ] = x, i = m – эталон,

3) все элементы a [ i ], большие либо равные x, i = - правый фрагмент.

Элемент x = a [ m ] занимает позицию, соответствующую положению x в отсортированном массиве.

Рассмотрим механизм деления массива, выбрав в качестве эталона элемент .

1. Полагаем i = L (левая граница массива), j = R (правая граница массива).

2. Увеличиваем i до тех пор, пока не найдем элемент a [ i ] ≥ x.

3. Уменьшаем j до тех пор, пока не найдем элемент a [ j ] ≤ x.

4. Если i ≤ j, меняем местами элементы a [ i ] и a [ j ], увеличиваем i и уменьшаем j на 1.

5. Если i ≤ j, идем на шаг 2.

Теперь в части a [ L ], …, a [ j ] собраны все элементы, меньшие либо равные эталону x, а в части a [ i ], …, a [ R ] – все элементы, большие либо равные эталону. Далее этот же алгоритм применяем для массивов a [ L ], …, a [ j ] и a [ i ], …, a [ R ], то есть алгоритм является рекурсивным.

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

 

m = (0 + 9) / 2 = 9 / 2 = 4

 

i									j
	i							j
		i					j
			i			j
				i	j
				i	j
				j	i

 

Теперь повторим действия для левой и правой частей массива.

 

m = (0+4)/2 = 2			m = (5+9)/2 = 7
i				j			i				j
		i		j					i		j
			i=j							i=j
		j	i						j	i

 

Далее рекурсивно повторяем те же действия (уже для четырех частей массива)

 

m = (0+2)/2 = 1

m = (3+4)/2 = 3

m = (5+7)/2 = 6

m = (8+9)/2 = 8

i

j

i

j

i

j

i

j

i

j

i

j

i

j

i

j

j

i

j

i

j

i

j

i

 

Повторяем те же действия для тех из получившихся восьми частей массива, которые состоят более чем из одного элемента (таких осталось две).

 

m = (0+1)/2 = 0

m = (5+6)/2 = 5

i

j

i

j

i=j

i=j

j

i

j

i

 

Обе части уже отсортированы, элементов для обмена нет. Работа алгоритма закончена, получаем отсортированный массив.

 

 

Алгоритм Хоара

 

1. i = L, j = R,

2. Полагаем i = L (левая граница массива), j = R (правая граница массива).

3. Увеличиваем i до тех пор, пока не найдем элемент a [ i ] ≥ x.

4. Увеличиваем j до тех пор, пока не найдем элемент a [ j ] ≤ x.

5. Если i ≤ j, меняем местами элементы a [ i ] и a [ j ], увеличиваем i и уменьшаем j на 1.

6. Если i ≤ j, идем на шаг 2.

7. Если L < j, полагаем R = j и идем на шаг 1.

8. Если R > i, полагаем L = i и идем на шаг 1.

 

Блок-схема сортировки Хоара

 

 

Теперь поговорим о выборе эталона x. Сам Хоар предполагал, что выбор элемента для сравнения должен быть случайным. В нашем случае мы выбирали средний элемент. Однако почти с тем же успехом можно выбирать первый или последний элементы. В этих случаях хуже всего будет, если массив окажется первоначально уже упорядочен.

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

В лучшем случае общее число сравнений равно C = N log₂ (N), а общее число обменов . Средняя производительность алгоритма быстрой сортировки при случайном выборе эталона обличается от оптимального случая лишь коэффициентом 2 log₂(2). Наихудшая производительность алгоритма будет порядка N ².

Однако быстрой сортировке присущи некоторые недостатки. Главный из них – плохая производительность при небольших N, впрочем, это недостаток всех усовершенствованных методов. Но перед другими усовершенствованными методами этот алгоритм имеет то преимущество, что для обработки небольших частей (например, когда (R – L) < 10) в него можно легко включить какой-либо из простых методов сортировки, например, прямую вставку.

Побитовая сортировка

 

В основе алгоритма побитовой сортировки лежит та же идея Хоара, что и в алгоритме быстрой сортировки (сортировки Хоара). Массив разбивается на две части – левую и правую так, чтобы все элементы в левой части были меньше всех элементов правой части. Затем та же процедура рекурсивно повторяется для левой и правой частей, и так далее, до тех пор, пока массив не будет отсортирован.

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

Рассмотрим механизм разбиения массива на две части.

1. Выделяем интересующий нас бит (в начале это старший бит).

2. Полагаем i = L (левая граница массива), j = R (правая граница массива).

3. Увеличиваем i до тех пор, пока не найдем элемент такой элемент a [ i ], в двоичном представлении у которого интересующий нас бит равен 0, либо пока массив не закончится.

4. Уменьшаем j до тех пор, пока не найдем элемент a [ j ], в двоичном представлении у которого интересующий нас бит равен 0, либо пока массив не закончится.

5. Если i < j, меняем местами элементы a [ i ] и a [ j ], увеличиваем i и уменьшаем j на единицу.

6. Если i ≤ j, идем на шаг 3.

В результате элементы a [ L ], …, a [ j ] будут содержать в выделенном разряде 0, а элементы a [ i ], …, a [ R ] будут содержать в выделенном разряде 1.

Приведем пример. Пусть L = 0, R = 9. Сам массив

181 111 42 217 70 144 43 92 191 91

Интересующий нас бит выделен синим цветом, элементы, подлежащие обмену – красным. В верхней строке приведена нумерация битов, в первом столбце – индексация массива, далее – представление элементов массивов в двоичной системе счисления, в последнем столбце – элементы в десятичной системе счисления.

 

L =0	i
R =9	j
L =0	i
R =9	j
L =0
	i
	j
R =9
L =0
	i
	j
R =9
L =0
	j
	i
R =9

 

Здесь j > i, разбиение массива закончено. Он распадается на два массива:

 

91 11 42 92 70 43 и 144 217 191 181

 

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

 

левая часть ссылка1 правая часть ссылка2

 

Начало ссылки1

 

L =0	i
R =5	j
L =0	i
R =5	j
L =0
	i
	j
R =5
L =0
	j
	i
R =5

 

Здесь j > i, массив распадается на два массива:

 

43 42 и 111 92 70 91

 

левая часть ссылка11 правая часть ссылка12

Конец ссылки1

 

Начало ссылки11

 

L =0	i
R =1	j
	j
L =0
R =1	i

 

Здесь j > i, индекс j вышел за границу массива. Это произошло потому, что все элементы в пятом бите содержат единицу. В этом случае массив не распадается на два массива, то есть не меняется. Процедура вызывается рекурсивно для того же массива и следующего бита.

L =0	i
R =1	j
L =0	j
R =1
	i

 

Здесь j > i, индекс i вышел за границу массива. Это произошло потому, что все элементы в четвертом бите содержат ноль. В этом случае тот же массив разбивается по следующему биту.

Для следующих трех битов разбиения также не происходит (приведем здесь только окончательные значения индексов i и j).

 

	j
L =0
R =1	i
L =0	j
R =1
	i
	j
L =0
R =1	i

 

Рассмотрим разбиение по нулевому биту:

 

L =0	i
R =1	j
L =0	i
R =1	j
L =0	j
R =1	i

 

Произведено разбиение по последнему биту, значит, сортировка данной части исходного массива закончена.

Конец ссылки11

 

Начало ссылки12