from .pidgeonhole_sortimportpidgeonhole_sort

from .stooge_sortimportstooge_sort

from .cocktail_shaker_sortimportcocktail_shaker_sort

from .tree_sortimporttree_sort

classBinaryTreeNode(object):

def__init__(self,value):

self.value=value

self.left=None

self.right=None

definsert(tree,item):

iftree==None:

tree=BinaryTreeNode(item)

else:

if (item<tree.value):

if (tree.left==None):

tree.left=BinaryTreeNode(item)

else:

insert(tree.left,item)

else:

if (tree.right==None):

tree.right=BinaryTreeNode(item)

else:

insert(tree.right,item)

defin_order_traversal(tree,a):

if (tree.left!=None):

in_order_traversal(tree.left,a)

a.append(tree.value)

if (tree.right!=None):

in_order_traversal(tree.right,a)

deftree_sort(x):

t=insert(None,x[0]);

foriinx[1:]:

insert(t,i)

a= []

in_order_traversal(t,a)

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. It has two phases:

1. Frist is creating a binary search tree using the given array elements.

2. Second phase is traversing the given binary search tree in inorder, thus resulting in a sorted array.

**Performance**

The average number of comparisions for this method is O(nlogn). But in worst case, number of comparisions is reduced by O(n^2), a case which arrives when the tree is skewed.

from allalgorithms.sortingimport tree_sort

arr= [77,2,10,-2,1,7]

print(tree_sort(arr))

-`array`: Unsorted Array

selection_sort,

pigeonhole_sort,

stooge_sort,

cocktail_shaker_sort,

)

deftest_cocktail_shaker_sort(self):

self.assertEqual([-44,1,2,3,7,19],cocktail_shaker_sort([7,3,2,19,-44,1]))

deftree_sort(self):

self.assertEqual([-44,1,2,3,7,19],tree_sort([7,3,2,19,-44,1]))

if__name__=="__main__":