Insertion Sort
2020-03-07
もう一回おさらいということで プログラミングコンテスト攻略のためのアルゴリズムとデータ構造を購入しました。
AIZU ONLINE JUDGEの Insertion Sortです。
package main
import (
"fmt"
"strings"
)
func scanInput() (n int, slice []int) {
fmt.Scanf("%d", &n)
slice = make([]int, n)
for i := 0; i < n; i++ {
fmt.Scanf("%d", &slice[i])
}
return
}
func printSlice(slice []int) {
fmt.Println(strings.Trim(strings.Join(strings.Fields(fmt.Sprint(slice)), " "), "[]"))
}
func main() {
_, slice := scanInput()
printSlice(slice)
solve(slice)
}
func solve(nums []int) {
l := len(nums)
for i := 1; i < l; i++ {
v := nums[i]
j := i - 1
for j >= 0 && nums[j] > v {
nums[j+1] = nums[j]
j--
}
nums[j+1] = v
printSlice(nums)
}
}
ロジックよりも、入力を受け取る実装で戸惑いました。
プログラミングパズルは言語の筋トレにもなっていいですね。
参考
https://stackoverflow.com/questions/37532255/one-liner-to-transform-int-into-string