53 lines
1.1 KiB
Go
53 lines
1.1 KiB
Go
package aud
|
|
|
|
import "fmt"
|
|
|
|
func InsertionSort(list []int) []int {
|
|
|
|
fmt.Println(list)
|
|
|
|
for round := 1; round < len(list); round++ {
|
|
// Element to sort is list[round]
|
|
// Elements that are already sorted are list[0:round-1]
|
|
// Elements that are unsorted are list[round+1:len(list)]
|
|
|
|
element_to_insert := list[round]
|
|
|
|
// Find the first position where an element in bigger than the
|
|
// one we want to insert
|
|
position_to_insert := round
|
|
for i := 0; i < round; i++ {
|
|
if list[i] > element_to_insert {
|
|
position_to_insert = i
|
|
break
|
|
}
|
|
}
|
|
|
|
fmt.Sprintf("Insert element at %v", position_to_insert)
|
|
|
|
for i := round; i > position_to_insert; i-- {
|
|
list[i] = list[i-1]
|
|
}
|
|
|
|
list[position_to_insert] = element_to_insert
|
|
|
|
fmt.Println(list)
|
|
}
|
|
|
|
return list
|
|
|
|
}
|
|
|
|
func TheOtherInsertionSort(list []int) []int {
|
|
for round := 1; round < len(list); round++ {
|
|
element_to_insert := list[round]
|
|
pos := round
|
|
for pos > 0 && element_to_insert < list[pos-1] {
|
|
list[pos] = list[pos-1]
|
|
pos--
|
|
}
|
|
list[pos] = element_to_insert
|
|
}
|
|
return list
|
|
}
|