Golang代码中的未知错误：第二遍插入排序？

Question

I'm new to Go. I'm using go version go1.10.4 linux/amd64. My objective is to ask a single integer input from the user append it to an array and sort it. I'm using insertion sort for this. The program needs to exit on receiving 'X' as input from the user.

This is my code:

package main

import (
    "fmt"
    "strconv"
    //  "sort"
)

func insertionSort(arr []int) []int {
    // Traverse through 1 to len(arr)
    for i, _ := range arr[1:] {
        key := arr[i]
        j := i - 1
        for {
            if j >= 0 && key < arr[j] {
                arr[j+1] = arr[j]
                j = j - 1
            } else {
                break
            }
        }
        arr[j+1] = key
    }

    return arr
}

func main() {
    s := make([]int, 0, 3)
    var x string
    for {
        fmt.Printf("Enter a number: ")
        fmt.Scan(&x)

        if x == "X" {
            break
        }

        xInt, _ := strconv.Atoi(x)
        fmt.Println(xInt)

        s = append(s, xInt)
        //sort.Ints(s)
        s = insertionSort(s)
        fmt.Printf("%v
", s)
    }
    fmt.Printf("%v
", s)
}

I'm getting the following output:

Enter a number: 5
[5]
Enter a number: 4
[5 4]
Enter a number: 3
[4 5 3]
Enter a number: 2
[3 4 5 2]
Enter a number: 1
[2 3 4 5 1]
Enter a number: X
[2 3 4 5 1]

Question:

Why is it getting sorted in 2nd pass? I mean it's first printing the appended array and then for next element, it's printing the sorted array of the previous element. Why? I'm sorting after appending so this should not be the case...

I took (and converted from Python code) insertion sort code from here

Answer 1

Your for loop is wrong. When you do, for i,_ := range arr[1:]{, i becomes 0, not 1. You want to start traversing the array from the second element with pos 1, but when you do arr[1:], your array changes, becomes a slice with one less element and your index still ends up being 0.

To fix it, check the c++ code in the page you posted and implement the for loop that operates on the length of the original array.

The range arr is similar to foreach in other languages and makes it hard to operate with indexes.

Note: I also checked the python code of the page. It also has a for loop for the python code. Long story short, use range arr[1:] with caution :)

The fix :

for i, _ := range arr[1:] => for i:=1;i<len(arr);i++

It is given with a spoiler tag because I don't want to steal your joy of fixing the error.