Sorting complete binary search tree in an array in O(n)

#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");
}
Advertisements

2 thoughts on “Sorting complete binary search tree in an array in O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s