Introduction
One of the most basic sorting algorithms is the insertion sort. It is also relatively easy to understand as it closely mimics a common sorting strategy that humans normally use when sorting playing cards in their hand.
Even though its time complexity is O(n2) for the worst case, it still performs well for small input sizes.
Below is an illustration of the steps taken to perform a insertion sort:
Implementation
The main two parts of the code below are the two for
loops. In the first one, we go through every element of the initial slice, starting with the second (see (a) above) and we compare it iteratively backwards with the previous elements. Whenever the previous element is greater than the current one, we move it one position forward. Once the inner loop reaches the condition to stop, we assign the value of the current element to precede the last element that was moved forward. By doing this, we end up with a sorted slice.
func Sort(a []int) []int {
// creating a new slice of a size equal to the original
result := make([]int, len(a))
// copying elements from the original slice to the new slice
copy(result, a)
// iterating through all elements of the slice starting with the second
for i := 1; i < len(result); i++ {
// key holds the current value
key := result[i]
// j holds the index of the previous value
j := i - 1
// we iterate backwards starting with the previous value and compare it with the current value
for j >= 0 && result[j] > key {
// if the previous value is greater then we move it forward one position
result[j+1] = result[j]
// we decrement the index for the previous value so that we check the next value backwards
j--
}
// at the end of the inner loop we want to potentially move the current value of the main loop to a new position (if anything was shifted above)
result[j+1] = key
}
// returning the sorted slice
return result
}
Go specific decisions
As Go does not make a copy of the slice after it has been passed into a function, we had to make sure that we are no mutating the underlying array of the original slice and therefore had to create a new slice of the size of the original and copy into it the numbers.
Source code
dorin131 / go-algorithms
A collection of algorithms implemented in Go
Please feel free to make PRs with improvements
More algorithms are coming soon!
Video
Top comments (2)
Good article but there's typo at
Below is an illustration of the steps taken to perform a merge sort:
Thanks for spotting this! Fixed now :)