Реализации алгоритмов/Сортировка/Пирамидальная: различия между версиями
Содержимое удалено Содержимое добавлено
ISbot (обсуждение | вклад) м Снятие {{К переименованию}} и добавление {{BookCat}}; избыточные <big /> и <font /> вокруг <source />; ссылки; пробелы. |
|||
Строка 388: | Строка 388: | ||
end; |
end; |
||
</source> |
</source> |
||
здесь нет ввывода и ввода массива лиибо рандома , либо пользователем |
|||
== Pascal (другой вариант) == |
== Pascal (другой вариант) == |
Версия от 16:34, 18 сентября 2016
C
#include <stdio.h>
#define MAXL 1000
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 (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])
{
swap (&a[i+sh], &a[i*2+1+sh]);
b = 1;
}
else if (a[i*2+2+sh] < a[i*2+1+sh])
{
swap (&a[i+sh],&a[i*2+2+sh]);
b = 1;
}
}
}
else if (i * 2 + 1 + sh < n)
{
if (a[i+sh] > a[i*2+1+sh])
{
swap (&a[i+sh], &a[i*2+1+sh]);
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;
}
C++
#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-- );
}
C++ (другой вариант)
#include <iostream>
#include <conio.h>
using namespace std;
void iswap(int &n1, int &n2)
{
int temp = n1;
n1 = n2;
n2 = temp;
}
int main()
{
int const n = 100;
int a[n];
for ( int i = 0; i < n; ++i ) { a[i] = n - i; cout << a[i] << " "; }
//заполняем массив для наглядности.
//-----------сортировка------------//
//сортирует по-возрастанию. чтобы настроить по-убыванию,
//поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
int sh = 0; //смещение
bool b = false;
for(;;)
{
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++; //смещение увеличивается, когда на текущем этапе
//сортировать больше нечего
if ( sh + 2 == n ) break;
} //конец сортировки
cout << endl << endl;
for ( int i = 0; i < n; ++i ) cout << a[i] << " ";
getch();
return 0;
}
C#
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();
}
C# (другой вариант)
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 - любой тип, на множестве элементов которого можно ввести отношение частичного порядка.
Pascal
Вместо «SomeType» следует подставить любой из арифметических типов (например integer).
procedure Sort(var Arr: array of SomeType; Count: Integer);
procedure DownHeap(index, Count: integer; Current: SomeType);
//Функция пробегает по пирамиде восстанавливая ее
//Также используется для изначального создания пирамиды
//Использование: Передать номер следующего элемента в index
//Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента
var
Child: Integer;
begin
while index < Count div 2 do begin
Child := (index+1)*2-1;
if (Child < Count-1) and (Arr[Child] < Arr[Child+1]) then
Child:=Child+1;
if Current >= Arr[Child] then
break;
Arr[index] := Arr[Child];
index := Child;
end;
Arr[index] := Current;
end;
//Основная функция
var
i: integer;
Current: SomeType;
begin
//Собираем пирамиду
for i := (Count div 2)-1 downto 0 do
DownHeap(i, Count, Arr[i]);
//Пирамида собрана. Теперь сортируем
for i := Count-1 downto 0 do begin
Current := Arr[i]; //перемещаем верхушку в начало отсортированного списка
Arr[i] := Arr[0];
DownHeap(0, i, Current); //находим нужное место в пирамиде для нового элемента
end;
end;
здесь нет ввывода и ввода массива лиибо рандома , либо пользователем
Pascal (другой вариант)
Примечание: myarray = array[1..Size] of integer; N — количество элементов массива
procedure HeapSort(var m: myarray; N: integer);
var
i: integer;
procedure Swap(var a,b:integer);
var
tmp: integer;
begin
tmp:=a;
a:=b;
b:=tmp;
end;
procedure Sort(Ns: integer);
var
i, tmp, pos, mid: integer;
begin
mid := Ns div 2;
for i := mid downto 1 do
begin
pos := i;
while pos<=mid do
begin
tmp := pos*2;
if tmp<Ns then
begin
if m[tmp+1]<m[tmp] then
tmp := tmp+1;
if m[pos]>m[tmp] then
begin
Swap(m[pos], m[tmp]);
pos := tmp;
end
else
pos := Ns;
end
else
if m[pos]>m[tmp] then
begin
Swap(m[pos], m[tmp]);
pos := Ns;
end
else
pos := Ns;
end;
end;
end;
begin
for i:=N downto 2 do
begin
Sort(i);
Swap(m[1], m[i]);
end;
end;
Pascal (третий вариант)
//процедура для перессылки записей
procedure swap(var x,y:integer);
var temp:integer;
begin
temp:=x;
x:=y;
y:=temp;
end;
//процедура приведения массива к пирамидальному виду (to pyramide)
procedure toPyr(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 left(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
topyr(a,i);
left(a,n);
end;
Python
def heapSort(li):
"""Сортирует список в возрастающем порядке с помощью алгоритма пирамидальной сортировки"""
def downHeap(li, k, n):
new_elem = li[k]
while 2*k+1 < n:
child = 2*k+1
if child+1 < n and li[child] < li[child+1]:
child += 1
if new_elem >= li[child]:
break
li[k] = li[child]
k = child
li[k] = new_elem
size = len(li)
for i in range(size//2-1,-1,-1):
downHeap(li, i, size)
for i in range(size-1,0,-1):
temp = li[i]
li[i] = li[0]
li[0] = temp
downHeap(li, 0, i)
Python (другой вариант)
def heapsort(s):
sl = len(s)
def swap(pi, ci):
if s[pi] < s[ci]:
s[pi], s[ci] = s[ci], s[pi]
def sift(pi, unsorted):
i_gt = lambda a, b: a if s[a] > s[b] else b
while pi*2+2 < unsorted:
gtci = i_gt(pi*2+1, pi*2+2)
swap(pi, gtci)
pi = gtci
# heapify
for i in range((sl/2)-1, -1, -1):
sift(i, sl)
# sort
for i in range(sl-1, 0, -1):
swap(i, 0)
sift(0, i)
Perl
@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;
}
}
Java
/**
* Класс для сортировки массива целых чисел с помощью кучи.
* Методы в классе написаны в порядке их использования. Для сортировки
* вызывается статический метод 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 + 1;
}
/**
* Возвращает индекс левого потомка текущего узла
*
* @param i индекс текущего узла кучи
* @return индекс левого потомка
*/
private static int left(int i) {
return 2 * i + 2;
}
/**
* Меняет местами два элемента в массиве
*
* @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;
}
}