Sorting: Faster is Better
Tree sort is one of the less discussed sorting algorithms. The three elementary sorting Algorithms bubble sort, insertion sort, and selection sort are all worst case quadratic time algorithms.
Many sorting Algorithms with better than quadratic worst case running times have been discovered, many of which have an average and worst case complexity of O(n log n). Merge sort, Quicksort, and Heapsort are all well known examples of these faster sorting Algorithms. The subject of this Article is Tree Sort, which is another O(n log n) sorting algorithm.
Tree Sort
Tree sort takes advantage of the ordered property of Binary Search Trees and the fact that an in order traversal of said tree naturally yields the data it contains in sorted ascending order. It works by taking an array and building a binary search tree from the data held in that array. An in-order traversal of the tree is then performed, where the node processing step is placing each nodes data into an array, which yields a sorted array of the original data set.
Implementation Notes
I’m going to be using the C language for this example for the purpose of showing that the creation of and insertion into BSTs can be accomplished easily and quickly. The algorithm can be easily adapted to take advantage of the OOP features of languages like C++ and Java. For those who may be interested in that exercise i recommend taking a look at my article Binary Search Trees Part 1 as it covers the necessary operations on BSTs with examples in C++.
The code
The following two functions form the meat and potatoes of Tree Sort. Take a look through and then I’ll discuss whats going on here.
We need to define a typical binary tree node structure:
struct node {
int data;
struct node* l;
struct node* r;
};
We also will use the standard recursive version of an inorder tree
traversal for copying the contents of the tree into an array, we define
outputIndex as a global variable to keep things simple:
int outputIndex;
void treeToArr(struct node* t, int A[])
{
if (t != NULL)
{
treeToArr(t->l, A);
A[outputIndex++] = t->data;
treeToArr(t->r, A);
}
}
The main function builds the tree from the array, element by element
before calling the recursive inorder function to yield the sorted order:
void treesort(int A[], int sz)
{
struct node* root = NULL;;
struct node* t, *itr, *p;
for (int i = 0; i < sz; i++)
{
t = malloc(sizeof(struct node));
t->data = A[i];
t->l = t->r = NULL;
if (root == NULL)
{
root = t;
} else {
for (itr = root; itr != NULL; itr = (A[i] < itr->data) ? itr->l:itr->r)
p = itr;
if (A[i] < p->data) p->l = t;
else p->r = t;
}
}
outputIndex = 0;
treeToArr(root, A);
}
As you can see, it works by looping through the elements of the unsorted array and inserting each element into a binary search tree. An in-order depth first traversal of the tree we just created is conducted in order to exploit the property that a binary search tree yields the data sorted in ascending order when subjected to an in-order traversal. Because C inherently passes arrays by reference, thus we don’t need an explicit return statement.
Lets test tree sort using the follow driver code:
void printArr(int A[], int sz)
{
for (int i = 0; i < sz; i++)
printf("%d ", *(A+i));
printf("\n");
}
int main()
{
int A[] = { 13, 37, 42, 11, 7, 69, 5, 108, 127, 17};
int sz = sizeof(A)/sizeof(A[0]);
printArr(A, sz);
treesort(A, sz);
printArr(A, sz);
return 0;
}
Output:
[maxs-MacBook-Pro:~]% ./ts
13 37 42 11 7 69 5 108 127 17
5 7 11 13 17 37 42 69 108 127
All of the source code shown in this example is available on my github:
