Tree Sort in C\C++ (Algorithm, Pseudocode and output)
Hy guys welcome to Another tutorial of Sorting Algorithms.
Whenever we need to arrange data in a specific order how you sort the data provided is of the utmost importance. However, in C, C++ we use many different types of Sorting Techniques to do this job few of which we have already discussed earlier like Insertion Sort, Bubble Sort and Selection Sort , Shell Sort, Quick Sort, Bucket Sort and today we are going to understand one of the popular sorting technique i.e " Tree Sort ".
So let's get started...
illustration:
A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order. Its typical use is sorting elements online: after each insertion, the set of elements seen so far is available in sorted order.
Tree sort can be used as a one-time sort, but it is equivalent to quicksort as both recursively partition the elements based on a pivot, and since quicksort is in-place and has lower overhead, it has few advantages over quicksort. It has better worst-case complexity when a self-balancing tree is used, but even more overhead.
Algorithm :
Step 1: Take the elements input in an array.
Step 2: Create a Binary search tree by inserting data items from the array into the binary search tree.
Step 3: Perform in-order traversal on the tree to get the elements in sorted order.
Average Case Time Complexity : O(n log n)
Adding one item to a Binary Search tree on average takes O(log n) time. Therefore, adding n items will take O(n log n) time
Worst Case Time Complexity: O(n2).
The worst-case time complexity of Tree Sort can be improved by using a self-balancing binary search tree like Red-Black Tree, AVL Tree. Using self-balancing binary tree Tree Sort will take O(n log n) time to sort the array in the worst case.
Auxiliary Space : O(n)
C Programme - Tree Sort
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node
{
int data;
struct node *left, *right;
};
struct node *root;
void ins(struct node *, int, int);
void inser(struct node *, int);
void display(struct node *);
int main()
{
int choice, no = 0, parentnode;
root = (struct node *) malloc (sizeof(struct node));
printf("\n Enter a number for parent node : ");
scanf("%d",&parentnode);
root -> data = parentnode;
root -> left = root -> right = NULL;
do{
printf("\n 1.Add element");
printf("\n 2.Sort");
printf("\n 3.Exit");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element to insert : \n");
scanf("%d",&no);
inser(root, no);
break;
case 2:
printf("\n Sorted elements are : \n");
display(root);
break;
default:
printf("\n Invalid press...");
exit(0);
}
}while(choice < 3);
return 0;
}
void ins(struct node *n, int value, int opt)
{
struct node *t;
t = (struct node *)malloc (sizeof (struct node));
t -> data = value;
t -> left = t -> right = NULL;
if(opt == 1)
n -> left = t;
else
n -> right = t;
printf("%d is inserted",value);
if(opt == 1)
printf(" at the left \n");
else
printf(" at the right \n");
}
void inser(struct node *t,int x)
{
if(t -> data > x)
if(t -> left == NULL)
ins(t,x,1);
else
inser(t -> left, x);
else if(t -> data < x)
if(t -> right == NULL)
ins(t, x, 2);
else
inser(t -> right,x);
else
printf(" Element is already exist in the list ");
}
void display(struct node *p)
{
if(p != NULL)
{
display(p -> left);
printf("%5d",p -> data);
display(p -> right);
}
}Output:
Enter a number for parent node : 3
1.Add element
2.Sort
3.Exit
Enter your choice : 1
Enter the element to insert :
21
21 is inserted at the right
1.Add element
2.Sort
3.Exit
Enter your choice : 1
Enter the element to insert :
53
53 is inserted at the right
1.Add element
2.Sort
3.Exit
Enter your choice : 1
Enter the element to insert :
22
22 is inserted at the left
1.Add element
2.Sort
3.Exit
Enter your choice : 2
Sorted elements are :
3 21 22 53
C++ Programme - Tree Sort
// C++ program to implement Tree Sort
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node *left, *right;
};
// A utility function to create a new BST Node
struct Node *newNode(int item)
{
struct Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Stores inoder traversal of the BST
// in arr[]
void storeSorted(Node *root, int arr[], int &i)
{
if (root != NULL)
{
storeSorted(root->left, arr, i);
arr[i++] = root->key;
storeSorted(root->right, arr, i);
}
}
/* A utility function to insert a new
Node with given key in BST */
Node* insert(Node* node, int key)
{
/* If the tree is empty, return a new Node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) Node pointer */
return node;
}
// This function sorts arr[0..n-1] using Tree Sort
void treeSort(int arr[], int n)
{
struct Node *root = NULL;
// Construct the BST
root = insert(root, arr[0]);
for (int i=1; i<n; i++)
root = insert(root, arr[i]);
// Store inoder traversal of the BST
// in arr[]
int i = 0;
storeSorted(root, arr, i);
}
// Driver Program to test above functions
int main()
{
//create input array
int arr[] = {5, 4, 7, 2, 11};
int n = sizeof(arr)/sizeof(arr[0]);
treeSort(arr, n);
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}
Output:
2 4 5 7 11
Advantages - Tree Sort
- The main advantage of tree sort algorithm is that we can make changes very easily as in a linked list.
- Sorting in Tree sort algorithm is as fast as quick sort algorithm.
Disadvantages - Tree Sort
- The worst-case occur when the elements in an array are already sorted.
- In the worst case, the running time of the tree sort algorithm is 0 (n2).
No comments
If you have any doubts, please let us Know.