Правила форума
Внимание!
допустим, наш изначальный массив 3 7 4 1 8 3 3 5 9 1. Строится бинарное дерево, на следующий уровень идут
3 1 3 3 1, то есть соседние числа сравниваются, дальше идет наименьший элемент.
Следующие уровни: 1 3 1,
1 1
1
В конце остаётся 1, она отправляется в отсортированный массив (в данном случае на первое место), а из начального массива отбрасывается (заменяется на бесконечность).
Вобщем, в этом суть, преподаватель назвал его "турнирной" сортировкой, но это явно не "пирамидальная-турнирная-HeapSort" сортировка, преведённая на форуме.
Вот мой код:
#include <iostream>
#include<conio.h>
#include <windows.h>
#include <math.h>
using namespace std;
int xe;
int temp[1000], buff[1000];
int stTwo(int size)
{
int k=0;
while (pow(2,k)<size)
k+=1;
return k;
}
void TurnirSort(int *a, long size, int st, int li)
{
int cl = size;
int S = li;
for (int i=0; i<S; i++)
buff[i]=a[i];
while(cl != 1)
{
for (int i=0,j=0;i<cl; i+=2,j++)
{
if (buff[i]>buff[i+1])
temp[j]=buff[i+1];
else temp[j]=buff[i];
}
cl = li/2;
li = cl;
for (int i=0; i<cl; i++)
buff[i]=temp[i];
for (int i=0; i<cl; i++)
if(buff[i] == 0) buff[i] = 1000;
}
xe = temp[0];
for (int i=0; i<size;i++)
if (a[i] == xe)
{
a[i] = 1000;
break;
}
}
int main()
{
srand(time(NULL));
int ch,size,l, h, st, li;
cout<<"Please, enter the size of massive to sort!"<<endl;
cin>>size;
cout<<"Please, enter the down border!"<<endl;
cin>>l;
cout<<"Please, enter the up border!"<<endl;
cin>>h;
int a[size];
int vec_sort[size];
st = stTwo(size);
li = (int)pow(2,st);
for(int i=0;i<size;i++)
{
a[i]=l+rand()%(h-l);
}
for (int i=size; i<li;i++)
{
a[i] = 1000;
}
for(int i=0;i<size;i++)
{
cout<<a[i]<<" ";
}
cout << endl << endl;
long time = GetTickCount();
for(int i=0; i<size; i++)
{
TurnirSort(a,size,st,li);
vec_sort[i] = xe;
}
time = GetTickCount()-time;
for(int i=0;i<size;i++)
{
cout<<vec_sort[i]<<" ";
}
cout << endl << endl;
getch();
cout<<"time = "<<time<<endl;
getch();
}
Тестировал я её на масивах в 10 элементов, всё четко работало и работает, а вот, когда перешёл к практике(массив в 100 элементов), возникла ошибка - тупо выкидывает из программы... в чём проблема?
