Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
(→{{header|Go}}: added more generic version) |
|||
Line 759: | Line 759: | ||
import "fmt" |
import "fmt" |
||
⚫ | |||
func main() { |
func main() { |
||
⚫ | |||
fmt.Println("before:", a) |
fmt.Println("before:", a) |
||
heapSort() |
heapSort(a) |
||
fmt.Println("after: ", a) |
fmt.Println("after: ", a) |
||
} |
} |
||
func heapSort() { |
func heapSort(a []int) { |
||
for start := (len(a) - 2) / 2; start >= 0; start-- { |
for start := (len(a) - 2) / 2; start >= 0; start-- { |
||
siftDown(start, len(a)-1) |
siftDown(a, start, len(a)-1) |
||
} |
} |
||
for end := len(a) - 1; end > 0; end-- { |
for end := len(a) - 1; end > 0; end-- { |
||
a[end], a[0] = a[0], a[end] |
a[end], a[0] = a[0], a[end] |
||
siftDown(0, end-1) |
siftDown(a, 0, end-1) |
||
} |
} |
||
} |
} |
||
func siftDown(start, end int) { |
func siftDown(a []int, start, end int) { |
||
for root := start; root*2+1 <= end; { |
for root := start; root*2+1 <= end; { |
||
child := root*2 + 1 |
child := root*2 + 1 |
||
Line 789: | Line 788: | ||
} |
} |
||
a[root], a[child] = a[child], a[root] |
a[root], a[child] = a[child], a[root] |
||
root = child |
|||
} |
|||
}</lang> |
|||
More generic version that sorts anything that implements <code>sort.Interface</code>: |
|||
<lang go>package main |
|||
import ( |
|||
"sort" |
|||
"fmt" |
|||
) |
|||
func main() { |
|||
a := []int{170, 45, 75, -90, -802, 24, 2, 66} |
|||
fmt.Println("before:", a) |
|||
heapSort(sort.IntArray(a)) |
|||
fmt.Println("after: ", a) |
|||
} |
|||
func heapSort(a sort.Interface) { |
|||
for start := (a.Len() - 2) / 2; start >= 0; start-- { |
|||
siftDown(a, start, a.Len()-1) |
|||
} |
|||
for end := a.Len() - 1; end > 0; end-- { |
|||
a.Swap(0, end) |
|||
siftDown(a, 0, end-1) |
|||
} |
|||
} |
|||
func siftDown(a sort.Interface, start, end int) { |
|||
for root := start; root*2+1 <= end; { |
|||
child := root*2 + 1 |
|||
if child+1 <= end && a.Less(child, child+1) { |
|||
child++ |
|||
} |
|||
if !a.Less(root, child) { |
|||
return |
|||
} |
|||
a.Swap(root, child) |
|||
root = child |
root = child |
||
} |
} |