smoothsort
Sign in to saveIn computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of operations (see big O notation). Like heapsort, smoothsort is not a stable sort. The advantage of smoothsort is that it comes closer to time if the input is already sorted to some degree, whereas heapsort averages regardless of the initial sorted state.
Key facts
- Algorithm.name
- Smoothsort
- Algorithm.class
- Sorting algorithm
- Algorithm.image
- |alt=An animation depicting smoothsort's operation, showing the heap being built and then disassembled,
- Algorithm.caption
- Smoothsort operating on an array which is mostly in order. The bars across the top show the tree structure.
- Algorithm.data
- Array
- Algorithm.space
- total, auxiliary
- Algorithm.optimal
- When the data is already sorted
via Wikipedia infobox
Wikidata facts
- Image
- Smoothsort.gif
Show 1 more fact
- time of discovery or invention
- 1981-00-00
Sources (1)
via Wikidata · CC0
~12 min read
Article
12 sectionsContents
- Overview
- Operations
- Sifting down
- Growing the heap region by incorporating an element to the right
- Optimization
- Shrinking the heap region by separating the rightmost element from it
- Optimization
- Analysis
- Poplar sort
- Applications
- References
- External links
In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of operations (see big O notation). Like heapsort, smoothsort is not a stable sort. The advantage of smoothsort is that it comes closer to time if the input is already sorted to some degree, whereas heapsort averages regardless of the initial sorted state.
==Overview== Like heapsort, smoothsort organizes the input into a priority queue and then repeatedly extracts the maximum. Also like heapsort, the priority queue is an implicit heap data structure (a heap-ordered implicit binary tree), which occupies a prefix of the array. Each extraction shrinks the prefix and adds the extracted element to a growing sorted suffix. When the prefix has shrunk to nothing, the array is completely sorted.