Insertion sort similar to card ordering. Imagine that you are playing a card game. You're holding the cards in your hand, and these cards are sorted. The dealer hands you exactly one new card. You have to put it into the correct place so that the cards you're holding are still sorted. In selection sort, each element that you add to the sorted subarray is no smaller than the elements already in the sorted subarray. But in our card example, the new card could be smaller than some of the cards you're already holding, and so you go down the line, comparing the new card against each card in your hand, until you find the place to put it. You insert the new card in the right place, and once again, your hand holds fully sorted cards. Then the dealer gives you another card, and you repeat the same procedure. Then another card, and another card, and so on, until the dealer stops giving you cards.
Time Complexity
The time complexity for this algorithm is O(N^2) and Best case time complexity is O(n) when the list is already sorted.
Implementation
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
insertionSort(slice)
fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func insertionSort(items []int) {
var n = len(items)
for i := 1; i < n; i++ {
j := i
for j > 0 {
if items[j-1] > items[j] {
items[j-1], items[j] = items[j], items[j-1]
}
j = j - 1
}
}
}
Result:
Other Topics:
How to build NGINX RTMP module, Setup Live Streaming with NGINX RTMP module, Publishing Stream with Open Broadcaster Software (OBS), Create Adaptive Streaming with NGINX RTMP, Implementing Filtergraph in Streaming with NGINX RTMP, How to Implement Running Text in Streaming with NGINX RTMP, How to build OpenSceneGraph with Code::Blocks, How to build OpenSceneGraph with Visual Studio 2010, Building Geometry Model, How to run OpenSceneGraph with Netbean IDE 8.2 C++, Rendering Basic Shapes, Using OSG Node to Load 3D Object Model, Rendering 3D Simulator with OpenSceneGraph, How to compile wxWidgets with Visual Studio 2010, How to Setup Debugging in Golang with Visual Code
