Сортировка - турнир с выбыванием

Действия напоминают процесс разыгрывания некоторого турнира, где его участники состязаются друг с другом для определения наилучшего игрока.

Рассмотрим, например, последовательность из восьми чисел: 25,57,48,37,20,92,86,33. Предположим, что при встрече двух чисел побеждает большее. Тогда после проведения встреч мы получим следующее дерево (рис), отображающее ход турнира.

Расположим узлы этого дерева в массиве, состоящем в данном случае из 15 элементов. В общем случае исходный массив состоит из n ? size =2 k чисел и количество его элементов n дополняется до 2 k добавлением достаточно малых чисел. Мы будем добавлять числа, равные -32768. В общем случае для хранения узлов турнирного дерева достаточно массива, состоящего из 2 k +1 -1 чисел. Определим его как

int tree [2* size ];

Нумерация элементов этого массива будет начинаться с 1 , элемент tree [0] не используется, поэтому число его элементов равно 2 k +1 =2 size .

Исходный сортируемый массив расположим в узлах

tree[size], tree[size+1], ..., tree[2*size-1].

Каждый элемент массива tree будет рассматриваться как узел дерева. Отцом элемента tree [ i ] является элемент tree [ i /2] ( i /2 - целая часть дроби ) , а сыновьями – элементы tree [2 i ] и tree [2 i +1].

В узлах дерева tree [ i ] при 1 ? i ? size -1 запишем индекс большего из сыновей.

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

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

После первого этапа известен наибольший элемент. В нашем примере этим элементом будет tree [13]=92. Далее будем выявлять наибольший среди оставшихся. Он будет наибольшим среди тех, которые сравнивались с числом tree [13]. Поэтому для его нахождения достаточно сравнить между собой те элементы, которые сравнивались с tree [13] , эти элементы будут являться сыновьями узлов, в которых значения равны 13 . Следовательно, нужно сначала изменить tree [6]=12 , а затем, на протяжении единственного пути, соединяющего tree [6] и tree [1] , сравнивать сыновей узлов tree [ i ] , изменяя счетчик i с помощью операции i = i /2 перехода к индексу отцовского узла.

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

Таким образом, второй этап будет состоять из цикла, в котором k пробегает значения k = n , n -1,...,2 . Цикл состоит из операции x [ k ]= tree [ tree [1]] присваивания x [ k ] наибольшему среди рассмотренных элементов («участвующих во встречах») и переупорядочивания дерева вдоль пути, соединяющего узел i = tree [1] с корнем. После завершения цикла x [1] будет равен tree [ tree [1]]. Получим отсортированный массив x [1], x [2],..., x [ n ] .

В нашем примере после первой итерации цикла дерево преобразуется в дерево, показанное на рис. Значение узла 6 изменяется на 12, в узле 3 – на 14, в узле 1 – на 14.

Разработаем подпрограмму void Tourtament ( int n , int * x ) сортировки описанным методом. Она будет состоять из двух частей, соответствующих первому и второму этапам алгоритма «турнир с выбыванием».

В первой части вычисляется наименьшая степень двойки size =2 k такая, что n ? size . А затем вызывается подпрограмма инициализации

void Initialize(int n,int size,int small,int *x,int *tree);

которая заполняет элементами массива x узлы tree [ size ], tree [ size +1], ..., tree [ size + n -1] и дополняет их числами small  = -32768 , а потом проводит «турнир», в результате которого выявляется наибольший элемент, и индекс этого элемента записывается в tree [1].

Вторая часть состоит из цикла

for ( k = n ; k >1; k --)

{

i = tree [1]; //индекс наибольшего числа

x [ k ]= tree [ i ]; //запись наибольшего числа в массив

tree [ i ]= small ; //замена наибольшего достаточно малым числом

ReadJust ( i , tree );//переупорядочивание вдоль пути от i к 1

}

и присваивания x [1]= tree [ tree [1]].

Приведем окончательный текст программы

#include <iostream.h>

#include <conio.h>

void Initialize (int n, int size, int small, int *x, int *tree)

{ int i,j,k;

for (i=1; i<=n; i++) tree [size+i-1]=x[i];

for (i=size+n; i<=2*size-1; i++) tree[i]=small;

for (j=size; j<=2*size-1; j+=2)

if (tree[j]>=tree[j+1]) tree[j/2]=j; else tree[j/2]=j+1;

k=size/2;

while (k>0)

{

for (j=k; j<=2*k-1; j+=2)

if (tree[tree[j]]>=tree[tree[j+1]]) tree[j/2]=tree[j];

else tree[j/2]=tree[j+1];

k/=2;

}

}

void ReadJust(int i, int *tree)

{

int j;

if (i%2==0) tree[i/2]=i+1;

else tree[i/2]=i-1;

i=i/2;

while(i>1)

{

if (i%2==0) j=i+1;

else j=i-1;

if (tree[tree[i]]>tree[tree[j]])

tree[i/2]= tree[i];

else tree[i/2]=tree[j];

i=i/2;

}

}

void Tourtament (int n, int *x)

{ int i, k, size, small, tree[1023];

size=1; small=-32768;

while (size<n) size*=2;

Initialize (n, size, small, x, tree);

for (k=n; k>1; k--)

{ i=tree[1];

x[k]=tree[i];

tree[i]=small;

ReadJust (i, tree);

} x[1]=tree[tree[1]];

}

void main ()

{ int x[]={0, 45, 23,12, 34, 1, 87, 42, 11, 5, 36, 12, 3, 5, 8, 99, 2 }, n=16;

clrscr ();

cout<<"До сортировки:"<<endl;

for (int i=1; i<=n; i++) cout << x[i] << " ";

Tourtament (n, x);

cout<<endl<<" После сортировки :"<<endl;

for (i=1; i<=n; i++) cout << x[i] << " ";

getch ();

}

Результаты работы программы

До сортировки:

45 23 12 34 1 87 42 11 5 36 12 3 5 8 99 2

После сортировки:

1 2 3 5 5 8 11 12 12 23 34 36 42 45 87 99