tree sort Algorithm
Tree Sort Algorithm is a sorting technique that follows a binary search tree data structure, a tree-based algorithm used for sorting elements in a specific order. It is a comparison-based sorting method, where the elements are organized in a hierarchical structure called the binary search tree. In this structure, each node has at most two children, and the left child node has a value less than or equal to its parent, while the right child node has a value greater than or equal to its parent. The basic idea behind the Tree Sort Algorithm is to insert elements from the input array into a binary search tree, and then traverse the tree in an inorder manner to obtain the sorted elements.
To implement the Tree Sort Algorithm, first, the elements are inserted one by one into a binary search tree. This is done by comparing the incoming element with the value of the current node, and if it is less than or equal to the current node's value, it is inserted into the left subtree, otherwise, it is inserted into the right subtree. This process is repeated until all the elements from the input array have been inserted into the tree. After the insertion is completed, an inorder traversal of the binary search tree is performed, which gives the sorted elements in an ascending order. During the inorder traversal, the algorithm visits the left subtree, the current node, and then the right subtree recursively, thus producing a sorted sequence of elements. The time complexity of the Tree Sort Algorithm is O(n log n) for balanced trees, but it can be as bad as O(n^2) for skewed trees, making it less efficient for certain cases.
#include <iostream>
using namespace std;
struct Node
{
int key;
struct Node *left, *right;
};
struct Node *newNode(int item)
{
struct Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
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);
}
}
Node* insert(Node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key){
node->left = insert(node->left, key);
}else if (key > node->key) {
node->right = insert(node->right, key);
}
return node;
}
void treeSort(int arr[], int n)
{
struct Node *root = NULL;
root = insert(root, arr[0]);
for (int i=1; i<n; i++){
insert(root, arr[i]);
}
int i = 0;
storeSorted(root, arr, i);
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Given array is ";
for (int i=0; i<n; i++){
cout << arr[i] << " ";
}
treeSort(arr, n);
cout << "\nSorted array is ";
for (int i=0; i<n; i++){
cout << arr[i] << " ";
}
return 0;
}
