Улучшенные методы сортировки. Пирамидальная сортировка.
Её эффективность.
Пирамидальная сортировка – это улучшенный алгоритм сортировки простым выбором. Данное улучшение было разработано р.флойдом. Он предложил перестраивать линейный массив в пирамиду, которая моделирует бинарное дерево. В таком дереве два нижних соседних элемента всегда имеют один элемент, который расположен над ними на уровень выше (рис. 15.1). Минимальный элемент ищется среди этих двух соседних элементов.
Все элементы линейного массива можно распределить последовательно, начиная с первого элемента и кончая последним элементом, используя определённый принцип расположения элементов (рис. 15.1). Само действие «распределить последовательно» означает, что элементы данного массива будут выбираться в определённом заданном порядке, так что бы виртуально моделировалась заданная конструкция.
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[7]
A[8]
A[9]
A[10]
A[11]
A[12]
A[13]
A[14]
A[15]
Рисунок 15.1 принцип расположения элементов массива в пирамиде
Сначала производится просеивание – это первая часть алгоритма, а затем осуществляется основная сортировка – это вторая часть алгоритма.
Первая часть алгоритма.Первая часть алгоритма – просеивание, необходима для преобразования исходного массива в пирамиду, в которой каждый верхний элемент «опирается» на два меньших элемента. Эту часть назвали просеиванием, так как данная операция напоминает процесс разделения смеси на фракции в соответствии с их размерами, где сначала задерживаются большие частицы, а потом всё более мелкие.
Из рисунка 15.1 видно, что любой элемент a[i], где 1<=i<=n div 2, «опирается» на элементы a[2*i] и a[2*i+1]. Таким образом формируются тройки из элементов. Такой тройкой являются элементы a[6], a[12] и a[13].
Для просеянной пирамиды необходимо, чтобы выполнялось следующее условие – в каждой тройке максимальный элемент должен находиться «сверху», т.е. A[6] должен быть больше a[12] и a[13]. Исходный массив сначала может и не удовлетворять этому свойству, поэтому его немного перестраивают, т.е. Просеивают в соответствии с приведённым условием. В процессе просеивания изменяется последовательность элементов в массиве.
Начинается просеивание «снизу». Половина элементов с ((n div 2)+1)-го элемента по n-й элемент являются основанием пирамиды, их просеивать не нужно. Но для всех остальных элементов, продвигаясь от конца массива к его началу, проверяются тройки элементов a[i], a[2*i] и a[2*i+1], в которых перемещают максимальный элемент «наверх», т.е. В элемент a[i]. Если в результате такого одного прохода снизу вверх была нарушена пирамидальность в других ниже лежащих тройках элементов, то необходимо снова произвести просеивание, но уже сверху вниз к её основанию.
Вторая часть алгоритма.Для n-1 элементов, начиная с последнего, нужно осуществить следующие действия. Сначала нужно поменять местами очередной «рабочий» элемент с первым. Потом просеивается новый первый элемент сверху вниз так, чтобы не затрагивалось уже отсортированное основание, т.е. Элементы с i-го по n-й.
Первым рабочим элементом является n, а потом n-1, затем n-2 и т.д.
Во второй части алгоритма должно быть осуществлено n-1 перестановок. При первой перестановке самый верхний элемент становится последним элементом и становится первым элементом уже отсортированного основания. После второй перестановки другой верхний элемент перемещается на место предпоследнего элемента массива и так же входит в уже отсортированное основание. Процесс повторяется до тех пор пока в не отсортированной части не останется один самый маленький элемент. Такой способ просеивания помогает вытолкнуть на вершину пирамиды самый большой элемент, а потом его переместить в начало отсортированной последовательности, т.е. В её уже отсортированное основание.
