Tree sort
Tree sort is a sorting algorithm that works by building a binary search tree from the elements to be sorted, and then traversing the tree in-order to obtain the sorted sequence. The algorithm was first proposed by J. W. S. Williams in 1964.
Here is an overview of how the tree sort algorithm works:
Insert all the elements to be sorted into a binary search tree. Each element is inserted in such a way that it satisfies the binary search tree property, which means that the left child of a node is always less than its parent, and the right child is always greater than or equal to its parent.
Traverse the binary search tree in-order, which means visiting the left subtree first, then the root, and then the right subtree. This traversal will visit all the nodes of the tree in sorted order, and hence the output will be the sorted sequence of elements.
Remove the elements from the binary search tree as they are visited during the in-order traversal.
The time complexity of tree sort depends on the shape of the binary search tree, which in turn depends on the order in which the elements are inserted. In the best case, the binary search tree is balanced, and the time complexity is O(n log n). In the worst case, the binary search tree can degenerate into a linear chain, and the time complexity becomes O(n^2). However, the average case time complexity is O(n log n) for random input data.
Here given code implementation process.
// C Program
// Sort array elements by using tree sort
#include <stdio.h>
#include <stdlib.h>
//Structure of Binary Search Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//Adding a new node in binary search tree
void add(struct Node **root, int data)
{
//Create a dynamic node of binary search tree
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL; //Initially node right-pointer is NULL
if ( *root == NULL)
{
//When adds a first node in binary tree
*root = new_node;
}
else
{
struct Node *find = *root;
//add new node to proper position
while (find != NULL)
{
if (find->data >= data)
{
if (find->left == NULL)
{
find->left = new_node;
break;
}
else
{
//visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
}
//Function which is display arr elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
//Add sorted order elements into array
struct Node *inorder_sort(struct Node *root, int arr[], int *location)
{
if (root != NULL)
{
root->left = inorder_sort(root->left, arr, location);
//insert tree elements into array
arr[ *location] = root->data;*location = *location + 1;
root->right = inorder_sort(root->right, arr, location);
//Safely remove tree element
if (root->left == NULL && root->right == NULL)
{
//When leaf node found then remove current element
free(root);
root = NULL;
}
}
return root;
}
//Executing the tree sort in given array
void tree_sort(int arr[], int size)
{
int i = 0;
struct Node *root = NULL;
for (i = 0; i < size; ++i)
{
add( & root, arr[i]);
}
i = 0;
root = inorder_sort(root, arr, & i);
}
int main()
{
//Define an array of integers
int arr1[] = {
3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
};
//Get the size of arr
int size = sizeof(arr1) / sizeof(arr1[0]);
//Before sort
printf("\n Before Sort :\n");
display(arr1, size);
//Sort element
tree_sort(arr1, size);
//After sort
printf("\n After Sort :\n");
display(arr1, size);
int arr2[] = {
8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
};
//Get the size of arr
size = sizeof(arr2) / sizeof(arr2[0]);
//Before sort
printf("\n Before Sort :\n");
display(arr2, size);
//Sort element
tree_sort(arr2, size);
//After sort
printf("\n After Sort :\n");
display(arr2, size);
return 0;
}
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
/*
Java Program
Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
// Data value
public int data;
// Indicates left and right subtree
public Node left;
public Node right;
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class MySort
{
public Node root;
public int location;
public MySort()
{
this.root = null;
this.location = 0;
}
//Function which is display arr elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
//insert a node in BST
public void add(int data)
{
//Create a dynamic node of binary search tree
Node new_node = new Node(data);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in tree
this.root = new_node;
}
else
{
Node find = this.root;
//add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = new_node;
return;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
return;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
System.out.print("\nMemory Overflow\n");
}
}
//Add sorted order elements into array
public Node inorder_sort(Node head, int[] arr)
{
if (head != null)
{
head.left = inorder_sort(head.left, arr);
//insert tree elements into array
arr[location] = head.data;
this.location = this.location + 1;
head.right = inorder_sort(head.right, arr);
//Safely remove tree element
if (head.left == null && head.right == null)
{
//When leaf node found then remove current element
head = null;
}
}
return head;
}
//Executing the tree sort in given array
public void tree_sort(int[] arr, int size)
{
int i = 0;
for (i = 0; i < size; ++i)
{
add(arr[i]);
}
this.location = 0;
this.root = inorder_sort(root, arr);
}
public static void main(String[] args)
{
MySort obj = new MySort();
//Define an array of integers
int[] arr1 = {
3,
6,
2,
5,
-7,
2,
1,
4,
7,
8,
2
};
//Get the size of arr
int size = arr1.length;
System.out.print("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.tree_sort(arr1, size);
System.out.print("\n After Sort :\n");
obj.display(arr1, size);
int[] arr2 = {
8,
2,
9,
-6,
3,
2,
31,
41,
2,
1,
67,
32
};
//Get the size of arr
size = arr2.length;
System.out.print("\n Before Sort :\n");
obj.display(arr2, size);
//Sort element
obj.tree_sort(arr2, size);
System.out.print("\n After Sort :\n");
obj.display(arr2, size);
}
}
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
//Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
public:
// Data value
int data;
// Indicates left and right subtree
Node * left;
Node * right;
Node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class MySort
{
public: Node * root;
int location;
MySort()
{
this->root = NULL;
this->location = 0;
}
//Function which is display arr elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
//insert a node in BST
void add(int data)
{
//Create a dynamic node of binary search tree
Node * new_node = new Node(data);
if (new_node != NULL)
{
if (this->root == NULL)
{
//When adds a first node in tree
this->root = new_node;
}
else
{
Node * find = this->root;
//add new node to proper position
while (find != NULL)
{
if (find->data >= data)
{
if (find->left == NULL)
{
find->left = new_node;
return;
}
else
{
//visit left sub-tree
find = find->left;
}
}
else
{
if (find->right == NULL)
{
find->right = new_node;
return;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}
else
{
cout << "\nMemory Overflow\n";
}
}
//Add sorted order elements into array
Node * inorder_sort(Node * head, int arr[])
{
if (head != NULL)
{
head->left = this->inorder_sort(head->left, arr);
//insert tree elements into array
arr[this->location] = head->data;
this->location = this->location + 1;
head->right = this->inorder_sort(head->right, arr);
//Safely remove tree element
if (head->left == NULL && head->right == NULL)
{
//When leaf node found then remove current element
head = NULL;
}
}
return head;
}
//Executing the tree sort in given array
void tree_sort(int arr[], int size)
{
int i = 0;
for (i = 0; i < size; ++i)
{
this->add(arr[i]);
}
this->location = 0;
this->root = this->inorder_sort(this->root, arr);
}
};
int main()
{
MySort obj = MySort();
int arr1[] = {
3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
};
//Get the size of arr
int size = sizeof(arr1) / sizeof(arr1[0]);
cout << "\n Before Sort :\n";
obj.display(arr1, size);
//Sort element
obj.tree_sort(arr1, size);
cout << "\n After Sort :\n";
obj.display(arr1, size);
int arr2[] = {
8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
};
//Get the size of arr
size = sizeof(arr2) / sizeof(arr2[0]);
cout << "\n Before Sort :\n";
obj.display(arr2, size);
//Sort element
obj.tree_sort(arr2, size);
cout << "\n After Sort :\n";
obj.display(arr2, size);
return 0;
}
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
//Include namespace system
using System;
/*
C# Program
Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
// Data value
public int data;
// Indicates left and right subtree
public Node left;
public Node right;
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class MySort
{
public Node root;
public int location;
public MySort()
{
this.root = null;
this.location = 0;
}
//Function which is display arr elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//insert a node in BST
public void add(int data)
{
//Create a dynamic node of binary search tree
Node new_node = new Node(data);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in tree
this.root = new_node;
}
else
{
Node find = this.root;
//add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = new_node;
return;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
return;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
Console.Write("\nMemory Overflow\n");
}
}
//Add sorted order elements into array
public Node inorder_sort(Node head, int[] arr)
{
if (head != null)
{
head.left = inorder_sort(head.left, arr);
//insert tree elements into array
arr[location] = head.data;
this.location = this.location + 1;
head.right = inorder_sort(head.right, arr);
//Safely remove tree element
if (head.left == null && head.right == null)
{
//When leaf node found then remove current element
head = null;
}
}
return head;
}
//Executing the tree sort in given array
public void tree_sort(int[] arr, int size)
{
int i = 0;
for (i = 0; i < size; ++i)
{
add(arr[i]);
}
this.location = 0;
this.root = inorder_sort(root, arr);
}
public static void Main(String[] args)
{
MySort obj = new MySort();
int[] arr1 = {
3 , 6 , 2 , 5 , -7 , 2 , 1 , 4 , 7 , 8 , 2
};
//Get the size of arr
int size = arr1.Length;
Console.Write("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.tree_sort(arr1, size);
Console.Write("\n After Sort :\n");
obj.display(arr1, size);
int[] arr2 = {
8 , 2 , 9 , -6 , 3 , 2 , 31 , 41 , 2 , 1 , 67 , 32
};
//Get the size of arr
size = arr2.Length;
Console.Write("\n Before Sort :\n");
obj.display(arr2, size);
//Sort element
obj.tree_sort(arr2, size);
Console.Write("\n After Sort :\n");
obj.display(arr2, size);
}
}
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
<?php
/*
Php Program
Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
// Data value
public $data;
// Indicates left and right subtree
public $left;
public $right;
function __construct($data)
{
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class MySort
{
public $root;
public $location;
function __construct()
{
$this->root = null;
$this->location = 0;
}
//Function which is display arr elements
public function display($arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo " ". $arr[$i];
}
echo "\n";
}
//insert a node in BST
public function add($data)
{
//Create a dynamic node of binary search tree
$new_node = new Node($data);
if ($new_node != null)
{
if ($this->root == null)
{
//When adds a first node in tree
$this->root = $new_node;
}
else
{
$find = $this->root;
//add new node to proper position
while ($find != null)
{
if ($find->data >= $data)
{
if ($find->left == null)
{
$find->left = $new_node;
return;
}
else
{
//visit left sub-tree
$find = $find->left;
}
}
else
{
if ($find->right == null)
{
$find->right = $new_node;
return;
}
else
{
//visit right sub-tree
$find = $find->right;
}
}
}
}
}
else
{
echo "\nMemory Overflow\n";
}
}
//Add sorted order elements into array
public function inorder_sort($head, & $arr)
{
if ($head != null)
{
$head->left = $this->inorder_sort($head->left, $arr);
//insert tree elements into array
$arr[$this->location] = $head->data;
$this->location = $this->location + 1;
$head->right = $this->inorder_sort($head->right, $arr);
//Safely remove tree element
if ($head->left == null && $head->right == null)
{
//When leaf node found then remove current element
$head = null;
}
}
return $head;
}
//Executing the tree sort in given array
public function tree_sort( & $arr, $size)
{
$i = 0;
for ($i = 0; $i < $size; ++$i)
{
$this->add($arr[$i]);
}
$this->location = 0;
$this->root = $this->inorder_sort($this->root, $arr);
}
}
function main()
{
$obj = new MySort();
//Define an array of integers
$arr1 = array(3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2);
//Get the size of arr
$size = count($arr1);
echo "\n Before Sort :\n";
$obj->display($arr1, $size);
//Sort element
$obj->tree_sort($arr1, $size);
echo "\n After Sort :\n";
$obj->display($arr1, $size);
$arr2 = array(8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32);
//Get the size of arr
$size = count($arr2);
echo "\n Before Sort :\n";
$obj->display($arr2, $size);
//Sort element
$obj->tree_sort($arr2, $size);
echo "\n After Sort :\n";
$obj->display($arr2, $size);
}
main();
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
/*
Node Js Program
Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
// Data value
// Indicates left and right subtree
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class MySort
{
constructor()
{
this.root = null;
this.location = 0;
}
//Function which is display arr elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//insert a node in BST
add(data)
{
//Create a dynamic node of binary search tree
var new_node = new Node(data);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in tree
this.root = new_node;
}
else
{
var find = this.root;
//add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = new_node;
return;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
return;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
process.stdout.write("\nMemory Overflow\n");
}
}
//Add sorted order elements into array
inorder_sort(head, arr)
{
if (head != null)
{
head.left = this.inorder_sort(head.left, arr);
//insert tree elements into array
arr[this.location] = head.data;
this.location = this.location + 1;
head.right = this.inorder_sort(head.right, arr);
//Safely remove tree element
if (head.left == null && head.right == null)
{
//When leaf node found then remove current element
head = null;
}
}
return head;
}
//Executing the tree sort in given array
tree_sort(arr, size)
{
var i = 0;
for (i = 0; i < size; ++i)
{
this.add(arr[i]);
}
this.location = 0;
this.root = this.inorder_sort(this.root, arr);
}
}
function main()
{
var obj = new MySort();
//Define an array of integers
var arr1 = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2];
//Get the size of arr
var size = arr1.length;
process.stdout.write("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.tree_sort(arr1, size);
process.stdout.write("\n After Sort :\n");
obj.display(arr1, size);
var arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32];
//Get the size of arr
size = arr2.length;
process.stdout.write("\n Before Sort :\n");
obj.display(arr2, size);
//Sort element
obj.tree_sort(arr2, size);
process.stdout.write("\n After Sort :\n");
obj.display(arr2, size);
}
main();
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
# Python 3 Program
# Sort array elements by using tree sort
# Binary Search Tree Node
class Node :
# Data value
# Indicates left and right subtree
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class MySort :
def __init__(self) :
self.root = None
self.location = 0
# Function which is display arr elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
# insert a node in BST
def add(self, data) :
# Create a dynamic node of binary search tree
new_node = Node(data)
if (new_node != None) :
if (self.root == None) :
# When adds a first node in tree
self.root = new_node
else :
find = self.root
# add new node to proper position
while (find != None) :
if (find.data >= data) :
if (find.left == None) :
find.left = new_node
return
else :
# visit left sub-tree
find = find.left
else :
if (find.right == None) :
find.right = new_node
return
else :
# visit right sub-tree
find = find.right
else :
print("\nMemory Overflow\n", end = "")
# Add sorted order elements into array
def inorder_sort(self, head, arr) :
if (head != None) :
head.left = self.inorder_sort(head.left, arr)
# insert tree elements into array
arr[self.location] = head.data
self.location = self.location + 1
head.right = self.inorder_sort(head.right, arr)
# Safely remove tree element
if (head.left == None and head.right == None) :
# When leaf node found then remove current element
head = None
return head
# Executing the tree sort in given array
def tree_sort(self, arr, size) :
i = 0
i = 0
while (i < size) :
self.add(arr[i])
i += 1
self.location = 0
self.root = self.inorder_sort(self.root, arr)
def main() :
obj = MySort()
# Define an array of integers
arr1 = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2]
# Get the size of arr
size = len(arr1)
print("\n Before Sort :\n", end = "")
obj.display(arr1, size)
# Sort element
obj.tree_sort(arr1, size)
print("\n After Sort :\n", end = "")
obj.display(arr1, size)
arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32]
# Get the size of arr
size = len(arr2)
print("\n Before Sort :\n", end = "")
obj.display(arr2, size)
# Sort element
obj.tree_sort(arr2, size)
print("\n After Sort :\n", end = "")
obj.display(arr2, size)
if __name__ == "__main__": main()
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
# Ruby Program
# Sort array elements by using tree sort
# Binary Search Tree Node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
# Data value
# Indicates left and right subtree
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end
end
class MySort
# Define the accessor and reader of class MySort
attr_reader :root, :location
attr_accessor :root, :location
def initialize()
self.root = nil
self.location = 0
end
# Function which is display arr elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
# insert a node in BST
def add(data)
# Create a dynamic node of binary search tree
new_node = Node.new(data)
if (new_node != nil)
if (self.root == nil)
# When adds a first node in tree
self.root = new_node
else
find = self.root
# add new node to proper position
while (find != nil)
if (find.data >= data)
if (find.left == nil)
find.left = new_node
return
else
# visit left sub-tree
find = find.left
end
else
if (find.right == nil)
find.right = new_node
return
else
# visit right sub-tree
find = find.right
end
end
end
end
else
print("\nMemory Overflow\n")
end
end
# Add sorted order elements into array
def inorder_sort(head, arr)
if (head != nil)
head.left = self.inorder_sort(head.left, arr)
# insert tree elements into array
arr[@location] = head.data
self.location = self.location + 1
head.right = self.inorder_sort(head.right, arr)
# Safely remove tree element
if (head.left == nil && head.right == nil)
# When leaf node found then remove current element
head = nil
end
end
return head
end
# Executing the tree sort in given array
def tree_sort(arr, size)
i = 0
i = 0
while (i < size)
self.add(arr[i])
i += 1
end
self.location = 0
self.root = self.inorder_sort(@root, arr)
end
end
def main()
obj = MySort.new()
# Define an array of integers
arr1 = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2]
# Get the size of arr
size = arr1.length
print("\n Before Sort :\n")
obj.display(arr1, size)
# Sort element
obj.tree_sort(arr1, size)
print("\n After Sort :\n")
obj.display(arr1, size)
arr2 = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32]
# Get the size of arr
size = arr2.length
print("\n Before Sort :\n")
obj.display(arr2, size)
# Sort element
obj.tree_sort(arr2, size)
print("\n After Sort :\n")
obj.display(arr2, size)
end
main()
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
/*
Scala Program
Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node(var data: Int,
var left: Node,
var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class MySort(var root: Node,
var location: Int)
{
def this()
{
this(null, 0);
}
//Function which is display arr elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
//insert a node in BST
def add(data: Int): Unit = {
//Create a dynamic node of binary search tree
var new_node: Node = new Node(data);
if (new_node != null)
{
if (this.root == null)
{
//When adds a first node in tree
this.root = new_node;
}
else
{
var find: Node = this.root;
//add new node to proper position
while (find != null)
{
if (find.data >= data)
{
if (find.left == null)
{
find.left = new_node;
return;
}
else
{
//visit left sub-tree
find = find.left;
}
}
else
{
if (find.right == null)
{
find.right = new_node;
return;
}
else
{
//visit right sub-tree
find = find.right;
}
}
}
}
}
else
{
print("\nMemory Overflow\n");
}
}
//Add sorted order elements into array
def inorder_sort(head: Node, arr: Array[Int]): Node = {
if (head != null)
{
var temp : Node = head;
head.left = inorder_sort(head.left, arr);
//insert tree elements into array
arr(this.location) = head.data;
this.location = this.location + 1;
head.right = inorder_sort(head.right, arr);
//Safely remove tree element
if (head.left == null && head.right == null)
{
//When leaf node found then remove current element
temp = null;
return temp;
}
}
return head;
}
//Executing the tree sort in given array
def tree_sort(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
i = 0;
while (i < size)
{
add(arr(i));
i += 1;
}
this.location = 0;
this.root = inorder_sort(root, arr);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MySort = new MySort();
//Define an array of integers
var arr1: Array[Int] = Array(3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2);
//Get the size of arr
var size: Int = arr1.length;
print("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.tree_sort(arr1, size);
print("\n After Sort :\n");
obj.display(arr1, size);
var arr2: Array[Int] = Array(8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32);
//Get the size of arr
size = arr2.length;
print("\n Before Sort :\n");
obj.display(arr2, size);
//Sort element
obj.tree_sort(arr2, size);
print("\n After Sort :\n");
obj.display(arr2, size);
}
}
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
/*
Swift Program
Sort array elements by using tree sort
*/
//Binary Search Tree Node
class Node
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
class MySort
{
var root: Node? ;
var location: Int;
init()
{
self.root = nil;
self.location = 0;
}
//Function which is display arr elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//insert a node in BST
func add(_ data: Int)
{
//Create a dynamic node of binary search tree
let new_node: Node? = Node(data);
if (new_node != nil)
{
if (self.root == nil)
{
//When adds a first node in tree
self.root = new_node;
}
else
{
var find: Node? = self.root;
//add new node to proper position
while (find != nil)
{
if (find!.data >= data)
{
if (find!.left == nil)
{
find!.left = new_node;
return;
}
else
{
//visit left sub-tree
find = find!.left;
}
}
else
{
if (find!.right == nil)
{
find!.right = new_node;
return;
}
else
{
//visit right sub-tree
find = find!.right;
}
}
}
}
}
else
{
print("\nMemory Overflow\n", terminator: "");
}
}
//Add sorted order elements into array
func inorder_sort(_ head: Node? , _ arr : inout[Int]) -> Node?
{
if (head != nil)
{
head!.left = self.inorder_sort(head!.left, &arr);
//insert tree elements into array
arr[self.location] = head!.data;
self.location = self.location + 1;
head!.right = self.inorder_sort(head!.right, &arr);
//Safely remove tree element
if (head!.left == nil && head!.right == nil)
{
return nil;
}
}
return head;
}
//Executing the tree sort in given array
func tree_sort(_ arr: inout[Int], _ size: Int)
{
var i: Int = 0;
i = 0;
while (i < size)
{
self.add(arr[i]);
i += 1;
}
self.location = 0;
self.root = self.inorder_sort(self.root, &arr);
}
}
func main()
{
let obj: MySort = MySort();
//Define an array of integers
var arr1: [Int] = [3, 6, 2, 5, -7, 2, 1, 4, 7, 8, 2];
//Get the size of arr
var size: Int = arr1.count;
print("\n Before Sort :\n", terminator: "");
obj.display(arr1, size);
//Sort element
obj.tree_sort(&arr1, size);
print("\n After Sort :\n", terminator: "");
obj.display(arr1, size);
var arr2: [Int] = [8, 2, 9, -6, 3, 2, 31, 41, 2, 1, 67, 32];
//Get the size of arr
size = arr2.count;
print("\n Before Sort :\n", terminator: "");
obj.display(arr2, size);
//Sort element
obj.tree_sort(&arr2, size);
print("\n After Sort :\n", terminator: "");
obj.display(arr2, size);
}
main();
Output
Before Sort :
3 6 2 5 -7 2 1 4 7 8 2
After Sort :
-7 1 2 2 2 3 4 5 6 7 8
Before Sort :
8 2 9 -6 3 2 31 41 2 1 67 32
After Sort :
-6 1 2 2 2 3 8 9 31 32 41 67
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment