Anonymous user
Sorting algorithms/Insertion sort: Difference between revisions
→{{header|Go}}
Line 735:
import "fmt"
func insertionSort(a []int) {
for i := 1; i < len(a); i++ {
for j >= 0 && a[j] > value {
a[j+1] = a[j]
j = j - 1
}▼
a[j+1] = value
}
}
func main() {
fmt.Println("unsorted:", list)
fmt.Println("sorted! ", list)
}</lang>
Output:
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted! [23 26 31 41 53 58 59 84 93 97]
</pre>
A generic version that takes any container that conforms to <code>sort.Interface</code>:
<lang go>package main
import (
"fmt"
"sort"
)
func insertionSort(a sort.Interface) {
for i := 1; i < a.Len(); i++ {
for j := i; j > 0 && a.Less(j, j-1); j-- {
a.Swap(j-1, j)
}
}
}
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
fmt.Println("unsorted:", list)
insertionSort(sort.IntSlice(list))
fmt.Println("sorted! ", list)
}</lang>
Output:
<pre>
unsorted: [31 41 59 26 53 58 97 93 23 84]
sorted! [23 26 31 41 53 58 59 84 93 97]
</pre>
Using binary search to locate the place to insert:
<lang go>package main
import (
"fmt"
"sort"
)
func insertionSort(a
for i := 1; i < len(a); i++ {
value := a[i]
j := sort.Search(i,
▲ j = j - 1
▲ }
▲ a[j+1] = value
}
}
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
fmt.Println("unsorted:", list)
insertionSort(list)
fmt.Println("sorted! ", list)
}</lang>
Output:
| |||