Insertion Sort Algorithm : Go-lang and Python implementation.

The Insert-Sort Algorithm

In the case of an array based sequence. We start with the first element in the array.An array that only has a single
element by itself is already sorted by default.

Lets now add an arbitrary second element of the same type(let use integers in this case), if the second element that we add to our array is smaller than the first element we had previously added , we swap them such that the smaller second element goes to first position while the larger first element is relegated to the second position.

Lets now add a third element that we want to add, To settle this third element in its right position in our array that is already populated by two element, then this third element will have to be compared to the two elements already populating our array:

It will go like this;

1 - Is this third element smaller than the second element, if it is we move it to second position and the element that had been previously occupying that 2nd position is relegated to third position. If not smaller than the second position element(i.e if its the largest of the three array elements then we let if occupy the third position)

2 - If the third element was smaller than the second element, it now occupies the second position after displacing the originally second element. We now compare it to the first element, if its smaller than the first element, it goes into the first position as the smallest element, displacing the originally smallest element into second position.

3 - The above steps are repeated for each new addition to the array in-order to find the correct position for that element.

We can express the above describe algorithm as pseudo-code below

Algorithm InsertSort(Arr):
    input: an Array Arr of n comparable elements
    Output: The array Arr with elements rearranged in nondecreasing order
    for k from 1 to n - 1 do
        Insert Arr[k] at its proper location within Arr[0],Arr[1],...Arr[k]

The implementation of this Algorithm in python is shown below:

def InsertSort(Arr):
    for k in range(1, len(Arr)):
        currval = Arr[k]
        j = k
        while j > 0 and Arr[j-1] > currval:
            Arr[j] = Arr[j-1]
            j -= 1
        Arr[j] = currval    
    return Arr

In the above code we use an outer loop to consider each element in turn, and an inner loop that moves a newly considered element to its proper location relative to the
(sorted) sub-array of elements that are to its left.

The above implementation in python when translated line for line, logic for logic to Go-lang results in the code below,
Also note the input into the go-lang function is a Slice.In Go-lang a slice is a segment of dynamic arrays that can grow and shrink as you see fit.Like arrays,slices are index-able and have a length.Slices have a capacity and length property.

func InsertSort(Arr []int) []int{
    var x = len(items)
    for n := 1;n < x;n++ {
        v := n
        for v > 0 {
            if Arr[v-1] > Arr[v] {
               Arr[v-1], Arr[v] = Arr[v], Arr[v-1]
            }
         v = v - 1
        }
    }
   return Arr
}

Goodbye, see you soon.