 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Tree sort" – news ·newspapers ·books ·scholar ·JSTOR(June 2022) (Learn how and when to remove this message) |
.png) | |
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-caseperformance | O(n²) (unbalanced)O(n logn) (balanced) |
| Best-caseperformance | O(n logn)[citation needed] |
| Averageperformance | O(n logn) |
| Worst-casespace complexity | Θ(n) |
| Optimal | Yes, if balanced |
Atree sort is asort algorithm that builds abinary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order.[1] Its typical use is sorting elementsonline: 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 toquicksort as both recursively partition the elements based on a pivot, and since quicksort is in-place and has lower overhead, tree sort has few advantages over quicksort. It has better worst case complexity when a self-balancing tree is used, but even more overhead.
Adding one item to a binary search tree is on average anO(logn) process (inbig O notation). Adding n items is anO(n logn) process, making tree sorting a 'fast sort' process. Adding an item to an unbalanced binary tree requiresO(n) time in the worst-case: When the tree resembles alinked list (degenerate tree). This results in a worst case ofO(n²) time for this sorting algorithm.This worst case occurs when the algorithm operates on an already sorted set, or one that is nearly sorted, reversed or nearly reversed. ExpectedO(n logn) time can however be achieved by shuffling the array, but this does not help for equal items.
The worst-case behaviour can be improved by using aself-balancing binary search tree. Using such a tree, the algorithm has anO(n logn) worst-case performance, thus being degree-optimal for acomparison sort. However, tree sort algorithms require separate memory to be allocated for the tree, as opposed to in-place algorithms such asquicksort orheapsort. On most common platforms, this means thatheap memory has to be used, which is a significant performance hit when compared toquicksort andheapsort[citation needed]. When using asplay tree as the binary search tree, the resulting algorithm (calledsplaysort) has the additional property that it is anadaptive sort, meaning that its running time is faster thanO(n logn) for inputs that are nearly sorted.
The following tree sort algorithm in pseudocode accepts acollection of comparable items and outputs the items in ascending order:
STRUCTUREBinaryTreeBinaryTree:LeftSubTreeObject:NodeBinaryTree:RightSubTreePROCEDUREInsert(BinaryTree:searchTree,Object:item)IFsearchTree.NodeISNULLTHENSETsearchTree.NodeTOitemELSEIFitemISLESSTHANsearchTree.NodeTHENInsert(searchTree.LeftSubTree,item)ELSEInsert(searchTree.RightSubTree,item)PROCEDUREInOrder(BinaryTree:searchTree)IFsearchTree.NodeISNULLTHENEXITPROCEDUREELSEInOrder(searchTree.LeftSubTree)EMITsearchTree.NodeInOrder(searchTree.RightSubTree)PROCEDURETreeSort(Collection:items)BinaryTree:searchTreeFOREACHindividualItemINitemsInsert(searchTree,individualItem)InOrder(searchTree)
In a simplefunctional programming form, the algorithm (inHaskell) would look something like this:
dataTreea=Leaf|Node(Treea)a(Treea)insert::Orda=>a->Treea->TreeainsertxLeaf=NodeLeafxLeafinsertx(Nodetys)|x<=y=Node(insertxt)ys|x>y=Nodety(insertxs)flatten::Treea->[a]flattenLeaf=[]flatten(Nodetxs)=flattent++[x]++flattenstreesort::Orda=>[a]->[a]treesort=flatten.foldrinsertLeaf
In the above implementation, both the insertion algorithm and the retrieval algorithm haveO(n²) worst-case scenarios.
