Реализации алгоритмов/Сортировка/Пирамидальная
#include <stdio.h>
#define MAXL 1000
#define root i+sh
#define left 2*i+1+sh
#define right 2*i+2+sh
void swap (int *a, int *b) { int t = *a; *a = *b; *b = t; }
int main()
{
int a[MAXL], n, i, sh = 0, b = 0;
scanf ("%i", &n);
for (i = 0; i < n; ++i) scanf ("%i", &a[i]);
while (1)
{
b = 0;
for (i = 0; i < n; ++i)
{
if (right < n)
{
if (a[root] > a[left] || a[root] > a[right])
{
if (a[left] < a[right])
{
swap (&a[root], &a[left]);
b = 1;
}
else if (a[right] < a[left])
{
swap (&a[root], &a[right]);
b = 1;
}
}
}
else if (left < n)
{
if (a[root] > a[left])
{
swap (&a[root], &a[left]);
b = 1;
}
}
}
if (!b) sh++;
if (sh + 2 == n) break;
}
for (i = 0; i < n; i++) printf ("%i%c", a[i], (i != n - 1) ? ' ' : '\n');
return 0;
}
Вариант № 1
править#include <iterator>
template< typename Iterator >
void adjust_heap( Iterator first
, typename std::iterator_traits< Iterator >::difference_type current
, typename std::iterator_traits< Iterator >::difference_type size
, typename std::iterator_traits< Iterator >::value_type tmp )
{
typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
diff_t top = current, next = 2 * current + 2;
for ( ; next < size; current = next, next = 2 * next + 2 )
{
if ( *(first + next) < *(first + next - 1) )
--next;
*(first + current) = *(first + next);
}
if ( next == size )
*(first + current) = *(first + size - 1), current = size - 1;
for ( next = (current - 1) / 2;
top > current && *(first + next) < tmp;
current = next, next = (current - 1) / 2 )
{
*(first + current) = *(first + next);
}
*(first + current) = tmp;
}
template< typename Iterator >
void pop_heap( Iterator first, Iterator last)
{
typedef typename std::iterator_traits< Iterator >::value_type value_t;
value_t tmp = *--last;
*last = *first;
adjust_heap( first, 0, last - first, tmp );
}
template< typename Iterator >
void heap_sort( Iterator first, Iterator last )
{
typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
for ( diff_t current = (last - first) / 2 - 1; current >= 0; --current )
adjust_heap( first, current, last - first, *(first + current) );
while ( first < last )
pop_heap( first, last-- );
}
Вариант № 2
править#include <iostream>
void iswap (int &n1, int &n2)
{
int temp = n1;
n1 = n2;
n2 = temp;
}
int main ()
{
const int n = 100;
int a[n];
// Для наглядности заполняем массив числами от n до 0.
for (int i = 0; i < n; i++) {
a[i] = n - i;
std::cout << a[i] << ' ';
}
// ----------- Сортировка ------------
// Сортирует по возрастанию. Чтобы получить сортировку по убыванию,
// поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
int sh = 0; // Смещение
bool b;
do
{
b = false;
for (int i = 0; i < n; i++)
{
if (i * 2 + 2 + sh < n)
{
if ((a[i + sh] > /*<*/ a[i * 2 + 1 + sh]) || (a[i + sh] > /*<*/ a[i * 2 + 2 + sh]))
{
if (a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh])
{
iswap(a[i + sh], a[i * 2 + 1 + sh]);
b = true;
}
else if (a[i * 2 + 2 + sh] < /*>*/ a[i * 2 + 1 + sh])
{
iswap(a[i + sh], a[i * 2 + 2 + sh]);
b = true;
}
}
// Дополнительная проверка для последних двух элементов;
// с её помощью можно отсортировать пирамиду
// состоящую всего лишь из трёх элементов
if (a[i * 2 + 2 + sh] < /*>*/ a[i * 2 + 1 + sh])
{
iswap(a[i * 2 + 1 + sh], a[i * 2 + 2 + sh]);
b = true;
}
}
else if (i * 2 + 1 + sh < n)
{
if (a[i + sh] > /*<*/ a[ i * 2 + 1 + sh])
{
iswap(a[i + sh], a[i * 2 + 1 + sh]);
b = true;
}
}
}
if (!b)
++sh; // Смещение увеличивается, когда на текущем этапе сортировать больше нечего
} while (sh + 2 < n); // Конец сортировки
std::cout << std::endl << std::endl;
for (int i = 0; i < n; i++)
std::cout << a[i] << ' ';
return 0;
}
Вариант № 1
править static Int32 add2pyramid(Int32[] arr, Int32 i, Int32 N)
{
Int32 imax;
Int32 buf;
if ((2 * i + 2) < N)
{
if (arr[2 * i + 1] < arr[2 * i + 2]) imax = 2 * i + 2;
else imax = 2 * i + 1;
}
else imax = 2 * i + 1;
if (imax >= N) return i;
if (arr[i] < arr[imax])
{
buf = arr[i];
arr[i] = arr[imax];
arr[imax] = buf;
if (imax < N / 2) i = imax;
}
return i;
}
static void Pyramid_Sort(Int32[] arr, Int32 len)
{
//step 1: building the pyramid
for (Int32 i = len / 2 - 1; i >= 0; --i)
{
long prev_i = i;
i = add2pyramid(arr, i, len);
if (prev_i != i) ++i;
}
//step 2: sorting
Int32 buf;
for (Int32 k = len - 1; k > 0; --k)
{
buf = arr[0];
arr[0] = arr[k];
arr[k] = buf;
Int32 i = 0, prev_i = -1;
while (i != prev_i)
{
prev_i = i;
i = add2pyramid(arr, i, k);
}
}
}
static void Main(string[] args)
{
Int32[] arr = new Int32[100];
//заполняем массив случайными числами
Random rd = new Random();
for(Int32 i = 0; i < arr.Length; ++i) {
arr[i] = rd.Next(1, 101);
}
System.Console.WriteLine("The array before sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
//сортировка
Pyramid_Sort(arr, arr.Length);
System.Console.WriteLine("\n\nThe array after sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
System.Console.WriteLine("\n\nPress the <Enter> key");
System.Console.ReadLine();
}
Вариант № 2
правитьpublic class Heap<T>
{
private T[] _array; //массив сортируемых элементов
private int heapsize;//число необработанных элементов
private IComparer<T> _comparer;
public Heap(T[] a, IComparer<T> comparer){
_array = a;
heapsize = a.Length;
_comparer = comparer;
}
public void HeapSort(){
build_max_heap();//Построение пирамиды
for(int i = _array.Length - 1; i > 0; i--){
T temp = _array[0];//Переместим текущий максимальный элемент из нулевой позиции в хвост массива
_array[0] = _array[i];
_array[i] = temp;
heapsize--;//Уменьшим число необработанных элементов
max_heapify(0);//Восстановление свойства пирамиды
}
}
private int parent (int i) { return (i-1)/2; }//Индекс родительского узла
private int left (int i) { return 2*i+1; }//Индекс левого потомка
private int right (int i) { return 2*i+2; }//Индекс правого потомка
//Метод переупорядочивает элементы пирамиды при условии,
//что элемент с индексом i меньше хотя бы одного из своих потомков, нарушая тем самым свойство невозрастающей пирамиды
private void max_heapify(int i){
int l = left(i);
int r = right(i);
int lagest = i;
if (l<heapsize && _comparer.Compare(_array[l], _array[i])>0)
lagest = l;
if (r<heapsize && _comparer.Compare(_array[r], _array[lagest])>0)
lagest = r;
if (lagest != i)
{
T temp = _array[i];
_array[i] = _array[lagest];
_array[lagest] = temp;
max_heapify(lagest);
}
}
//метод строит невозрастающую пирамиду
private void build_max_heap(){
int i = (_array.Length-1)/2;
while(i>=0){
max_heapify(i);
i--;
}
}
}
public class IntComparer : IComparer<int>
{
public int Compare(int x, int y) {return x-y;}
}
public static void Main (string[] args)
{
int[] arr = Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).ToArray();//вводим элементы массива через пробел
IntComparer myComparer = new IntComparer();//Класс, реализующий сравнение
Heap<int> heap = new Heap<int>(arr, myComparer);
heap.HeapSort();
}
Здесь T - любой тип, на множестве элементов которого можно ввести отношение частичного порядка.
/**
* Класс для сортировки массива целых чисел с помощью кучи.
* Методы в классе написаны в порядке их использования. Для сортировки
* вызывается статический метод sort(int[] a)
*/
class HeapSort {
/**
* Размер кучи. Изначально равен размеру сортируемого массива
*/
private static int heapSize;
/**
* Сортировка с помощью кучи.
* Сначала формируется куча:
* @see HeapSort#buildHeap(int[])
* Теперь максимальный элемент массива находится в корне кучи. Его нужно
* поменять местами с последним элементом и убрать из кучи (уменьшить
* размер кучи на 1). Теперь в корне кучи находится элемент, который раньше
* был последним в массиве. Нужно переупорядочить кучу так, чтобы
* выполнялось основное условие кучи - a[parent]>=a[child]:
* @see #heapify(int[], int)
* После этого в корне окажется максимальный из оставшихся элементов.
* Повторить до тех пор, пока в куче не останется 1 элемент
*
* @param a сортируемый массив
*/
public static void sort(int[] a) {
buildHeap(a);
while (heapSize > 1) {
swap(a, 0, heapSize - 1);
heapSize--;
heapify(a, 0);
}
}
/**
* Построение кучи. Поскольку элементы с номерами начиная с a.length / 2 + 1
* это листья, то нужно переупорядочить поддеревья с корнями в индексах
* от 0 до a.length / 2 (метод heapify вызывать в порядке убывания индексов)
*
* @param a - массив, из которого формируется куча
*/
private static void buildHeap(int[] a) {
heapSize = a.length;
for (int i = a.length / 2; i >= 0; i--) {
heapify(a, i);
}
}
/**
* Переупорядочивает поддерево кучи начиная с узла i так, чтобы выполнялось
* основное свойство кучи - a[parent] >= a[child].
*
* @param a - массив, из которого сформирована куча
* @param i - корень поддерева, для которого происходит переупорядочивание
*/
private static void heapify(int[] a, int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < heapSize && a[i] < a[l]) {
largest = l;
}
if (r < heapSize && a[largest] < a[r]) {
largest = r;
}
if (i != largest) {
swap(a, i, largest);
heapify(a, largest);
}
}
/**
* Возвращает индекс правого потомка текущего узла
*
* @param i индекс текущего узла кучи
* @return индекс правого потомка
*/
private static int right(int i) {
return 2 * i + 2;
}
/**
* Возвращает индекс левого потомка текущего узла
*
* @param i индекс текущего узла кучи
* @return индекс левого потомка
*/
private static int left(int i) {
return 2 * i + 1;
}
/**
* Меняет местами два элемента в массиве
*
* @param a массив
* @param i индекс первого элемента
* @param j индекс второго элемента
*/
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Вариант № 1
правитьВместо «SomeType» следует подставить любой из арифметических типов (например integer).
procedure HeapSort (var sequence: array of T; count: Word);
procedure SiftDown (index, count: Word; current: T);
{
Функция пробегает по пирамиде восстанавливая ее
Также используется для изначального создания пирамиды
Использование: Передать номер следующего элемента в index
Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента
}
var child: Word;
begin
while index < count div 2 do
begin
child := (index + 1) * 2 - 1;
if (child < count - 1) and (sequence[child] < sequence[child + 1]) then
child := child + 1;
if current >= sequence[child] then
break;
sequence[index] := sequence[child];
index := child
end;
sequence[index] := current
end;
{ Основная функция }
var i: Integer;
current: T;
begin
{ Собираем пирамиду }
for i := (count div 2) - 1 downTo 0 do
SiftDown(i, count, sequence[i]);
{ Пирамида собрана. Теперь сортируем }
for i := count - 1 downTo 0 do
begin
current := sequence[i]; { перемещаем верхушку в начало отсортированного списка }
sequence[i] := sequence[0];
SiftDown(0, i, current) { находим нужное место в пирамиде для нового элемента }
end
end;
Здесь нет вывода и ввода массива. Либо случайный, либо пользователем.
Вариант № 2
правитьПримечание: N — количество элементов массива
procedure HeapSort (var sequence: array of T; N: Integer);
var i: Integer;
{ Выполняет обмен значениями двух элементов массива sequence с указанными индексами }
procedure SwapItems (index_1, index_2: Word);
var temp: T;
begin
temp := sequence[index_1];
sequence[index_1] := sequence[index_2];
sequence[index_2] := temp
end;
procedure Sort (Ns: integer);
var i, child, pos, mid: Integer;
begin
mid := Ns div 2;
for i := mid downTo 1 do
begin
pos := i;
while pos <= mid do
begin
child := pos * 2;
if child < Ns then
begin
if sequence[child + 1] < sequence[child] then
child := child + 1;
if sequence[child] < sequence[pos] then
begin
SwapItems(pos, child);
pos := child
end
else
pos := Ns
end
else if sequence[child] < sequence[pos] then
begin
SwapItems(pos, child);
pos := Ns
end
else
pos := Ns
end
end
end;
begin
for i := N downTo 2 do
begin
Sort(i);
SwapItems(1, i)
end
end;
Вариант № 3
править{ Процедура для обмена значений переменных }
procedure swap (var x, y: integer);
var temp: integer;
begin
temp := x;
x := y;
y := temp
end;
{ Процедура приведения массива к пирамидальному виду (to heap) }
procedure ToHeap (var data: TArray; n: integer); { n - размер массива }
var i: integer;
begin
for i := n div 2 downTo 1 do
begin
if 2 * i <= n then
if data[i] < data[2 * i] then
swap(data[i], data[2 * i]);
if 2 * i + 1 <= n then
if data[i] < data[2 * i + 1] then
swap(data[i], data[2 * i + 1])
end
end;
{ Процедура для сдвига массива влево }
procedure ShiftLeft (var data: TArray; n: integer);
var i: integer;
temp: integer;
begin
temp := data[1];
for i := 1 to n - 1 do
data[i] := data[i + 1];
data[n] := temp
end;
{ Основная программа }
BEGIN
for i := n downTo 1 do
begin
ToHeap(a, i);
ShiftLeft(a, n);
end
END.
@out=(6,4,2,8,5,3,1,6,8,4,3,2,7,9,1)
$N=@out+0;
if($N>1){
while($sh+2!=$N){
$b=undef;
for my$i(0..$N-1){
if($i*2+2+$sh<$N){
if($out[$i+$sh]gt$out[$i*2+1+$sh] || $out[$i+$sh]gt$out[$i*2+2+$sh]){
if($out[$i*2+1+$sh]lt$out[$i*2+2+$sh]){
($out[$i*2+1+$sh],$out[$i+$sh])=($out[$i+$sh],$out[$i*2+1+$sh]);
$b=1;
}elsif($out[$i*2+2+$sh]lt$out[$i*2+1+$sh]){
($out[$i*2+2+$sh],$out[$i+$sh])=($out[$i+$sh],$out[$i*2+2+$sh]);
$b=1;
}
}elsif($out[$i*2+2+$sh]lt$out[$i*2+1+$sh]){
($out[$i*2+1+$sh],$out[$i*2+2+$sh])=($out[$i*2+2+$sh],$out[$i*2+1+$sh]);
$b=1;
}
}elsif($i*2+1+$sh<$N && $out[$i+$sh]gt$out[$i*2+1+$sh]){
($out[$i+$sh],$out[$i*2+1+$sh])=($out[$i*2+1+$sh],$out[$i+$sh]);
$b=1;
}
}
++$sh if!$b;
last if$sh+2==$N;
}
}
Приведённые алгоритмы упорядочивают принимаемую последовательность sequence (список, символьную строку) по неубыванию (sequence[i] ≤ sequence[i + 1]). Для упорядочения по невозрастанию (sequence[i] ≥ sequence[i + 1]) необходимо заменить все знаки < на > в строках, помеченных # !
Для большей эффективности вычислений умножение и деление нацело на 2 производятся операторами побитового сдвига влево (<<) и вправо (>>) соответственно. Например parent << 1 вместо parent * 2, length >> 1 вместо length // 2 и т. п.
Проверить работу любой из функций можно добавив, например, следующий код (Python 3; для Python 2 следует опустить скобки в операторах print):
count = 30 # Количество значений в последовательности
# Заполняем последовательность значениями, расположенными в порядке, обратном желаемому:
sequence = list(range(count, 0, -1))
# Для упорядочения по невозрастанию закомментируйте предыдущую строку и раскомментируйте следующую
# sequence = list(range(1, count))
print("Исходная последовательность:")
print(sequence)
heap_sort(sequence)
print("Упорядоченная последовательность:")
print(sequence)
Вариант № 1
правитьdef heap_sort (sequence):
def sift_down (parent, limit):
item = sequence[parent]
while True:
child = (parent << 1) + 1
if child >= limit:
break
if child + 1 < limit and sequence[child] < sequence[child + 1]: # !
child += 1
if item < sequence[child]: # !
sequence[parent] = sequence[child]
parent = child
else:
break
sequence[parent] = item
# Тело функции heap_sort
length = len(sequence)
# Формирование первичной пирамиды
for index in range((length >> 1) - 1, -1, -1):
sift_down(index, length)
# Окончательное упорядочение
for index in range(length - 1, 0, -1):
sequence[0], sequence[index] = sequence[index], sequence[0]
sift_down(0, index)
Вариант № 2
правитьdef heap_sort (sequence):
def swap_items (index1, index2):
if sequence[index1] < sequence[index2]: # !
sequence[index1], sequence[index2] = sequence[index2], sequence[index1]
def sift_down (parent, limit):
while True:
child = (parent + 1) << 1 # То же, что и parent * 2 + 2
if child < limit:
if (sequence[child] < sequence[child - 1]):
swap_items(parent, child-1)
parent = child-1
else:
swap_items(parent, child)
parent = child
else:
if (child-1<limit):
swap_items(parent,child-1)
break
# Тело функции heap_sort
length = len(sequence)
# Формирование первичной пирамиды
for index in range((length >> 1) - 1, -1, -1):
sift_down(index, length)
# Окончательное упорядочение
for index in range(length - 1, 0, -1):
swap_items(index, 0)
sift_down(0, index)
Приведённые алгоритмы упорядочивают принимаемую последовательность sequence (в её качестве могут выступать массив (array), вектор (Vec), срез (slice)) по неубыванию (sequence[i] ≤ sequence[i + 1]). Для упорядочения по невозрастанию (sequence[i] ≥ sequence[i + 1]) необходимо закомментировать знаки < и раскомментировать > в местах, помеченных /*>*/
Для большей эффективности вычислений умножение и деление нацело на 2 производятся операторами побитового сдвига влево (<<) и вправо (>>) соответственно. Например parent << 1 вместо parent * 2, length >> 1 вместо length / 2 и т. п.
Проверить работу любой из функций можно добавив, например, следующий код (следует учитывать, что в Rust массивы до 32 элементов могут выводиться макросами print! и println!; для более длинных придётся писать собственную функцию вывода):
fn main () {
let mut sequence = [0i32; 30]; // Массив из 30 элементов
let mut value = sequence.len() as i32;
// Заполнение последовательности убывающими значениями
for i in 0..sequence.len() {
sequence[i] = value;
value -= 1;
// Для заполнения возрастающими значениями закомментируйте две предыдущие строки и раскомментируйте следующую:
// sequence[i] = i as i32 + 1;
}
// Вывод исходной последовательности
println!("Исходная последовательность:\n{:?}", sequence);
// Упорядочение последовательности
heap_sort(&mut sequence);
// Вывод упорядоченной последовательности
println!("Упорядоченная последовательность:\n{:?}", sequence);
}
Вариант № 1
правитьfn heap_sort <T: PartialOrd> (sequence: &mut[T]) {
let length = sequence.len();
let mut offset = 0usize;
let mut flag = false;
while {
for index in 0..length {
let left = (index << 1) + 1 + offset; // Индекс левого ребёнка
let right = left + 1; // Индекс правого ребёнка
if right < length { // Если существуют оба ребёнка
if sequence[left] < /*>*/ sequence[index + offset] || sequence[right] < /*>*/ sequence[index + offset] {
if sequence[left] < /*>*/ sequence[right] {
sequence.swap(index + offset, left);
flag = true;
} else if sequence[right] < /*>*/ sequence[left] {
sequence.swap(index + offset, right);
flag = true;
}
}
// Дополнительная проверка для последних двух элементов;
// с её помощью можно отсортировать пирамиду состоящую всего лишь из трёх элементов
if sequence[right] < /*>*/ sequence[left] {
sequence.swap(left, right);
flag = true;
}
} else if left < length { // Если существует только один ребёнок
if sequence[left] < /*>*/ sequence[index + offset] {
sequence.swap(index + offset, left);
flag = true;
}
}
}
if flag {
flag = false;
} else {
offset += 1; // Смещение увеличивается, когда на текущем этапе сортировать больше нечего
}
offset + 2 < length // Условие повторения цикла while
} { /* Пустое тело цикла (имитация цикла с постусловием)*/ }
}
Вариант № 2
правитьПо сравнению с предыдущим вариантом элементы последовательности также должны быть копируемыми (реализовывать типаж Copy).
fn heap_sort <T: PartialOrd + Copy> (sequence: &mut[T]) {
fn sift_down <T: PartialOrd + Copy> (sequence: &mut[T], root: usize, limit: usize) {
let mut parent = root;
let mut child: usize;
let item = sequence[root]; // Элемент, для которого ищется место в последовательности
while {
child = (parent << 1) + 1;
child < limit // Условие повторения № 1: у sequence[parent] есть хоть один ребёнок
} && {
// Выбор большего /*меньшего*/ из детей sequence[parent]
if child + 1 < limit && sequence[child] < /*>*/ sequence[child + 1] {
child += 1;
};
item < /*>*/ sequence[child] // Условие повторения № 2: item меньше наибольшего /*больше наименьшего*/ из детей sequence[parent]
} { // Тело цикла
sequence[parent] = sequence[child]; // Сдвигаем ребёнка на место его родителя
parent = child;
}
if parent > root { // Если в ходе предыдущей отработки цикла делались сдвиги
sequence[parent] = item; // Перемещаем item на найденное для него место
}
};
// Формирование первичной пирамиды
let length = sequence.len();
let mut index = length >> 1; // Индекс родителя последнего элемента последовательности
while index > 0 {
index -= 1;
sift_down(sequence, index, length);
}
// Окончательное упорядочение
index = length;
while index > 1 {
index -= 1;
sequence.swap(0, index); // Обмен крайних элементов неупорядоченной части последовательности
sift_down(sequence, 0, index); // Восстановление свойства пирамиды в неупорядоченной части последовательности
}
}