Tree Sort: an online O(n log n) sorting algorithm
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 inorder 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.
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 key;
node* left;
node* right;
node(int i) : key(i), left(nullptr), right(nullptr) { }
};
An inorder traversal places the keys back into the array in sorted order.
void itrinorder(node* h, int a[]) {
stack<node*> sf;
int k = 0;
node* x = h;
while (x) {
sf.push(x);
x = x>left;
}
while (!sf.empty()) {
x = sf.top();
sf.pop();
a[k++] = x>key;
x = x>right;
while (x) {
sf.push(x);
x = x>left;
}
}
}
The main function builds the tree from the array, element by element before calling the recursive inorder function to yield the sorted order:
node* insert(node* h, int k) {
node* x = h;
node* p = x;
while (x != nullptr) {
p = x;
x = (k < x>key) ? x>left:x>right;
}
x = new node(k);
if (k < p>key)
p>left = x;
else
p>right = x;
return h;
}
void treesort(int a[], int l, int r) {
node* root = new node(a[l]);
for (int i = l+1; i <= r; i++)
root = insert(root, a[i]);
itrinorder(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 inorder 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 inorder traversal. Because C inherently passes arrays by reference, thus we don't need an explicit return statement. However, If we so desired, we could return the pointer to the root of the tree we just constructed, facilitating the sorting of future additions to the collection  this is the property which makes it a so called online algorithm.
Lets test tree sort using the follow driver code:
void print(int a[], int n) {
for (int i = 0; i < n; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
}
int main() {
int n = 27;
int a[n];
for (int i = 0; i < n; i++) {
a[i] = rand() % 200;
}
print(a, n);
treesort(a, 0, n  1);
print(a, n);
return 0;
}
Output: [maxsMacBookPro:~]% ./ts 13 37 42 11 7 69 5 108 127 17 5 7 11 13 17 37 42 69 108 127

A Different Take on Merge Sort: Binary Search Trees?

Deleting Entries From OpenAddress Hash tables

Transform any Binary Search Tree in to a Sorted Linked List

From Regular Expressions To NFA by way of Abstract Syntax Trees: Thompsons Construction

Extending Sedgewick's explicit Digraph NFA

Iterative Inorder B Tree Traversal

Simple DB Migration with JDBC

Welcome to CodeBlahger, A Blahging Platform for Programmers.

The Façade Pattern

The Interpreter Pattern: Implementing Interpreters the OOP way
Leave A Comment