Question

Describe the tournament sort using pseudocode.

Short answer

The value of a vertex is the list element currently there,and the label is the name (i.e., location) of the leaf responsiblefor that value.

Step-by-step solution

We need to write the pseudocode for tournament sorting.

In tournament sorting, all the items to be sorted from the leaf nodes of a tree and two items taken at a time are compared from left to right and the greater item is put as the internal node of the next upper level.

Again, the comparisons are repeated in this upper level in the same fashion. This is repeated until a rooted binary tree of height log IT is formed,

where n is the number of items in the list to be sorted.

The root will be the biggest element and now repeat the procedure with the root element excluded and the value at the location of the biggest element (leaf location) is replaced with -8.

The procedure tournament sort gives tournament sorting. The value of a vertex is the value of the item and the label indicates the location of the leaf node which carried the value of the item. at an are the n items to be sorted. In the pseudocode initially, a binary tree of height log n is formed and then values of the items to be sorted are inserted into the leaves.

Final conclusion, the pseudocode is as follows

Procedure tournament sort \(\left( {{a_1},\,{a_2},\,...,\,{a_n}} \right)\)

\(k: = \left\lceil {logn} \right\rceil \)

build a binary tree of height k

for\(i: = 1\)to n {initially all leaf nodes carry the value of the items}

set the value of the ith leaf to be ai and its label to be itself

for\(i: = n + 1\) to \({2^k}\) {this makes the number of items to be sorted a power of 2}

set the value of the ith leaf to be -8 and its label to {value inserted as -8 to extra items} be itself

for\(i: = k - 1\)down to 0 {taking the biggest value from a pair to its higher level} for each vertex v at level I set the value of v to the larger of the values of its children and its label to be the label of the larger child.

for\(i: = 1\) to n

\({c_i}: = \)value at the root {stores the value of the root in a list c, ci will be the ith largest item})

let v be the label of the root (setting the value of the root as -8 at its location} set the value of v to be -8 while the label at the root is still v (making the next biggest element as root value}

v: = parent(v) set the value of v to the larger of the values of its children and its label to be the label of the larger child.

{\(\left( {c1,\,c2,\,...,\,cn} \right)\)is the list in nonincreasing order}