Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted
(→‎{{header|Go}}: added more generic version)
Line 759: Line 759:


import "fmt"
import "fmt"

var a = []int{170, 45, 75, -90, -802, 24, 2, 66}


func main() {
func main() {
a := []int{170, 45, 75, -90, -802, 24, 2, 66}
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
}
}