HOME

TheInfoList



OR:

A tree sort is a sort algorithm that builds a
binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a Rooted tree, rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left ...
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 In computer technology and telecommunications, online indicates a state of connectivity, and offline indicates a disconnected state. In modern terminology, this usually refers to an Internet connection, but (especially when expressed as "on lin ...
: 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 Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
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.


Efficiency

Adding one item to a binary search tree is on average an process (in
big O notation Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
). Adding n items is an process, making tree sorting a 'fast sort' process. Adding an item to an unbalanced binary tree requires time in the worst-case: When the tree resembles a
linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...
( degenerate tree). This results in a worst case of 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. Expected 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 a
self-balancing binary search tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...
. Using such a tree, the algorithm has an worst-case performance, thus being degree-optimal for a
comparison sort A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should oc ...
. However, tree sort algorithms require separate memory to be allocated for the tree, as opposed to in-place algorithms such as
quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
or
heapsort In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that ...
. On most common platforms, this means that
heap memory Memory management (also dynamic memory management, dynamic storage allocation, or dynamic memory allocation) is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dynam ...
has to be used, which is a significant performance hit when compared to
quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
and
heapsort In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that ...
. When using a
splay tree A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal ...
as the binary search tree, the resulting algorithm (called splaysort) has the additional property that it is an
adaptive sort A sorting algorithm falls into the adaptive sort family if it takes advantage of existing order in its input. It benefits from the presortedness in the input sequence – or a limited amount of disorder for various definitions of measures of diso ...
, meaning that its running time is faster than for inputs that are nearly sorted.


Example

The following tree sort algorithm in pseudocode accepts a collection of comparable items and outputs the items in ascending order: In a simple
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
form, the algorithm (in
Haskell Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
) would look something like this: data Tree a = Leaf , Node (Tree a) a (Tree a) insert :: Ord a => a -> Tree a -> Tree a insert x Leaf = Node Leaf x Leaf insert x (Node t y s) , x <= y = Node (insert x t) y s , x > y = Node t y (insert x s) flatten :: Tree a -> flatten Leaf = [] flatten (Node t x s) = flatten t ++ [x] ++ flatten s treesort :: Ord a => [a] -> treesort = flatten . foldr insert Leaf In the above implementation, both the insertion algorithm and the retrieval algorithm have worst-case scenarios.


External links

* *
Tree Sort in C++


References

{{sorting Sorting algorithms Online sorts