Sorting algorithms/Heapsort: Difference between revisions
m (formatting) |
(→Tcl: Added implementation) |
||
| Line 2: | Line 2: | ||
Write a function to sort a collection of integers using heapsort. |
Write a function to sort a collection of integers using heapsort. |
||
=={{header|Tcl}}== |
|||
Based on the algorithm from Wikipedia:<br> |
|||
{{works with|Tcl|8.5}} |
|||
<lang tcl>package require Tcl 8.5 |
|||
proc heapsort {list {count ""}} { |
|||
if {$count eq ""} { |
|||
set count [llength $list] |
|||
} |
|||
for {set i [expr {$count/2 - 1}]} {$i >= 0} {incr i -1} { |
|||
siftDown list $i [expr {$count - 1}] |
|||
} |
|||
for {set i [expr {$count - 1}]} {$i > 0} {} { |
|||
swap list $i 0 |
|||
incr i -1 |
|||
siftDown list 0 $i |
|||
} |
|||
return $list |
|||
} |
|||
proc siftDown {varName i j} { |
|||
upvar 1 $varName a |
|||
while true { |
|||
set child [expr {$i*2 + 1}] |
|||
if {$child > $j} { |
|||
break |
|||
} |
|||
if {$child+1 <= $j && [lindex $a $child] < [lindex $a $child+1]} { |
|||
incr child |
|||
} |
|||
if {[lindex $a $i] >= [lindex $a $child]} { |
|||
break |
|||
} |
|||
swap a $i $child |
|||
set i $child |
|||
} |
|||
} |
|||
proc swap {varName x y} { |
|||
upvar 1 $varName a |
|||
set tmp [lindex $a $x] |
|||
lset a $x [lindex $a $y] |
|||
lset a $y $tmp |
|||
}</lang> |
|||
Demo code: |
|||
<lang tcl>puts [heapsort {1 5 3 7 9 2 8 4 6 0}]</lang> |
|||
Output: |
|||
<pre>0 1 2 3 4 5 6 7 8 9</pre> |
|||
Revision as of 12:22, 17 July 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
Heapsort is an in-place sorting algorithm with worst case and average complexity of O(n logn). The basic idea is to turn the array into a binary heap structure, which has the property that it allows efficient retrieval and removal of the maximal element. We repeatedly "remove" the maximal element from the heap, thus building the sorted list from back to front. See Heapsort for more details and pseudocode. Heapsort requires random access, so can only be used on an array-like data structure.
Write a function to sort a collection of integers using heapsort.
Tcl
Based on the algorithm from Wikipedia:
<lang tcl>package require Tcl 8.5
proc heapsort {list {count ""}} {
if {$count eq ""} {
set count [llength $list]
}
for {set i [expr {$count/2 - 1}]} {$i >= 0} {incr i -1} {
siftDown list $i [expr {$count - 1}]
}
for {set i [expr {$count - 1}]} {$i > 0} {} {
swap list $i 0 incr i -1 siftDown list 0 $i
} return $list
} proc siftDown {varName i j} {
upvar 1 $varName a
while true {
set child [expr {$i*2 + 1}] if {$child > $j} { break } if {$child+1 <= $j && [lindex $a $child] < [lindex $a $child+1]} { incr child } if {[lindex $a $i] >= [lindex $a $child]} { break } swap a $i $child set i $child
}
} proc swap {varName x y} {
upvar 1 $varName a set tmp [lindex $a $x] lset a $x [lindex $a $y] lset a $y $tmp
}</lang> Demo code: <lang tcl>puts [heapsort {1 5 3 7 9 2 8 4 6 0}]</lang> Output:
0 1 2 3 4 5 6 7 8 9