#include <stdio.h>

inline void swap(int a[], int i, int j)

{

int tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

/*

* position of an element of right subtree of root in sorted array is parent postion + number of elements in its left subtree + 1

* position of an element of left subtree of root in sorted array is number of elements in its left subtree + 1

*/

int completeBinSearchTreeSort(int a[], int n, int i, int pos)

{

int left = (i << 1) + 1;

if(left < n)

pos = completeBinSearchTreeSort(a, n, left, pos) + 1;

if((i < pos && a[i] > a[pos]) || (i > pos && a[i] < a[pos]))

swap(a, i, pos);

int right = left + 1;

if(right < n)

pos = completeBinSearchTreeSort(a, n, right, pos + 1);

return pos;

}

int main()

{

int a[] = {11, 5, 15, 2, 9, 13, 25, 1, 4, 7};

int n = sizeof(a)/sizeof(int);

completeBinSearchTreeSort(a, n, 0, 0);

int i;

for(i = 1; i < n; ++i)

if(a[i-1] > a[i])

swap(a, i -1, i);

for(i = 0; i < n; ++i)

printf("%d ", a[i]);

printf("\n");

}

### Like this:

Like Loading...

*Related*

Didnt work on the following input10 5 15 2 9 13 25 1 4 7

Has to be a complete Binary search tree.