How to Write Insertion Sort in Go

insert

The post How to Write Insertion Sort in Go first appeared on Qvault.

Insertion sort builds a final sorted list one item at a time. It’s much less efficient on large lists than more advanced algorithms like quicksort or merge sort. Insertion sort is a simple algorithm that works just like you would arrange playing cards in your hands. A slice is first split into sorted and unsorted sections, then values from the unsorted section are inserted into the correct position in the sorted section.

insertionsort

Full example of the insertion sort algorithm



func insertionSort(arr []int) []int { for i := 0; i < len(arr); i++ { for j := i; j > 0 && arr[j-1] > arr[j]; j-- { arr[j], arr[j-1] = arr[j-1], arr[j] } } return arr }


Code language: Go (go)














Sorry to interrupt! I just wanted to mention that you should check out my new free Go course. It’s designed to teach you all the fundamentals of my favorite coding language.














Learn Golang Now















As you can see, the insertionSort() function starts by iterating over the entire slice in a nested for loop. The job of the inner for loop is to consume one value for each repetition, and grow the sorted output list, which are all the elements before index i. At each repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted first section, and inserts it there. It repeats until no input elements remain.


Using insertion sort in code




func main() { fmt.Println(insertionSort([]int{5,3,2,1,0,4)) // prints // [0, 1, 2, 3, 4, 5] }


Code language: Go (go)


Why use insertion sort?


Insertion sort has a Big O complexity of O(n^2), because that is its worst-case complexity. The outer loop of insertion sort executes n times, while the inner loop depends on the input. In the worst case (a reverse sorted array) the inner loop executes n times as well. In the best case (a sorted array) the inner loop immediately breaks resulting in a total complexity of O(n).


Like bubble sort, the algorithm is just too slow for general-purpose production use, but can be a great learning tool. Here are some additional properties of insertion sort.


    

  • Simple implementation, easy to write
    • 

  • Fast for very small data sets
    • 

  • Faster than other simple sorting algorithms like Bubble Sort
    • 

  • Adaptive: Faster for partially sorted data sets
    • 

  • Stable: Does not change the relative order of elements with equal keys
    • 

  • In-Place: Only requires a constant amount of memory
    • 

  • Online: Can sort a list as it receives it
    • 



Some production sorting implementations use merge sort for very small inputs under a certain threshold (very small, like 10-ish). Insertion sort is better for very small lists than some of the faster algorithms because:


    

  • There is no recursion overhead
    • 

  • Tiny memory footprint
    • 

  • It’s a stable sort as described above
    • 















Ready to take action and get coding?


Try out our coding courses for free






Join our Discord community















Have questions or feedback?


Follow and hit me up on Twitter @q_vault if you have any questions or comments. If I’ve made a mistake in the article be sure to let me know so I can get it corrected!









source https://qvault.io/golang/insertion-sort-golang/






































Comments











Post a Comment























Popular posts from this blog









Why is Exclusive Or (XOR) Important in Cryptography?




















Image







    If you are getting into cryptography, or just trying to understand the fundamentals, you may have noticed that the exclusive-or operation is used quite often, especially in ciphers.  What is XOR ( ⊕ )?  XOR, or “exclusive or” operates on binary data. It returns true if both of its inputs are opposites (one false and one true), otherwise, it returns false.     An example in go code would be something like:  func exclusiveOr(a bool, b bool) bool {         return a != b }  XOR Cipher – The Perfect Cipher  The XOR operation can be used as a simple cipher for encrypting and decrypting messages with a single key. This is known as symmetric encryption.  It is interesting to note that if:   The key is the same size as the message  The key is kept secret and generated truly randomly   Then the cipher is impossible  to crack. This is known as a one time pad . However, a simple XOR shouldn’t be used in production due to the key length needing to be too long to be practical.  Cipher Example  A...








Read more










Base64 vs Base58 Encoding




















Image







 By Lane Wagner –  @wagslane  on Twitter   Base64 is one of the most popular encoding formats for representing data. Have some binary data? Base64 encode it for convenient readability and parsing. Base58 is just another encoding format (with 58 characters instead of 64, and has gained popularity largely due to Bitcoin and other cryptocurrencies.  When it comes to data encoding, there is typically a trade-off made between:   Human Readability: Do humans have a good idea of what is being represented at a glance?  Efficient data compression: How many bytes are used to represent the same data?   Let’s rank Base58, Base64, and ASCII encoding against each other using these metrics!  First: A Note on Binary  All data is stored in a raw binary format on computers. These encoding formats (Base64, Base58, and ASCII) are just different ways of reading and writing binary data. For example, in Base64 the binary code 000000  represents the letter A , but in ASCII the binary 00000000  repres...








Read more










(Very) Basic Intro to Hash Functions (SHA-256, MD-5, etc)




















Image







 This is going to be a basic introduction to hash functions. I will assume most of my audience is here to gain an understanding of why hash functions are used and the basic idea of why they work. My goal is to explain it in a general sense, I will be omitting proofs and implementation details and instead focusing on the high-level principles.     Why Use A Hash Function?  Hash functions are used all over the internet in order to securely store passwords, find duplicate records, quickly store and retrieve data, and more. For example,  Qvault  uses hashes to extend master passwords into private encryption keys.  A longer list of uses here:  https://en.wikipedia.org/wiki/Hash_function#Uses  I want to focus on several important features of hash functions, arguably the most important features.   Hash functions scramble data deterministically  No matter the input, the output of a hash function always has the same size  The original data can not be retrieved from the scrambled d...








Read more