Quick Sort in Golang

quick

The post Quick Sort in Golang first appeared on Qvault.

Quicksort is an efficient sorting algorithm that’s widely used in production sorting implementations. Like merge sort, quick sort is a divide and conquer algorithm. True to its name, quicksort is one of the fastest sorting algorithms, that said, you need to be careful with the implementation details because if you’re not careful the speed can degrade quickly.

Sorry to interrupt! I just wanted to mention that you should check out my new free algorithms course. You’ll learn the basics of Big O notation while writing awesome code in the Go programming language.

Learn Big O Algorithms Now

Divide

  • Select a pivot element that will preferably end up close to the center of the sorted pack
  • Move everything onto the “greater than” or “less than” side of the pivot
  • The pivot is now in its final position
  • Recursively repeat the operation on both sides of the pivot

Conquer

  • Return a sorted array after all elements have been through the pivot operation

Quicksort Pseudocode

Partition() function in Golang

Quicksort actually makes use of two functions, the main quicksort() function as well as the partition() function. The meat of the algorithm counter-intuitively lives in the partition() function. It’s responsible for finding the pivot and moving everything to the correct side of the pivot.

partition function

In Go, the complete code would look like this.



func partition(arr []int, low, high int) ([]int, int) { pivot := arr[high] i := low for j := low; j < high; j++ { if arr[j] < pivot { arr[i], arr[j] = arr[j], arr[i] i++ } } arr[i], arr[high] = arr[high], arr[i] return arr, i }


Code language: Go (go)


QuickSort() function in Golang


The quickSort() function is really just a wrapper around the partition function, and it handles the recursive nature of the algorithm.




quicksort animation






func quickSort(arr []int, low, high int) []int { if low < high { var p int arr, p = partition(arr, low, high) arr = quickSort(arr, low, p-1) arr = quickSort(arr, p+1, high) } return arr }


Code language: Go (go)


Example of using Quicksort in real code




fmt.Println(quickSortStart([]int{5, 6, 7, 2, 1, 0)) // prints // [0, 1, 2, 5, 6, 7]


Code language: Go (go)


Why use Quicksort?


On average, quicksort has a Big O of O(n*log(n)). In the worst case, and assuming we don’t take any steps to protect ourselves, it can break down to O(n^2). The partition() function has a single for-loop that ranges from the lowest index to the highest index in the array. By itself, the partition() function is O(n). The overall complexity of quicksort is dependent on how many times partition() is called.


In the worst case, the input is already sorted. An already sorted array results in the pivot being the largest or smallest element in the partition each time. When this is the case, partition() is called a total of n times. In the best case, the pivot is the middle element of each sublist which results in log(n) calls to partition().


Quick sort has the following properties.


    

  • Very fast in the average case
    • 

  • In-Place: Saves on memory, doesn’t need to do a lot of copying and allocating
    • 

  • More complex implementation
    • 

  • Typically unstable: changes the relative order of elements with equal keys
    • 



Ensuring a fast runtime in Quicksort


While the version of quicksort that we implemented is almost always able to perform at speeds of O(n*log(n)), it’s Big O complexity is still technically O(n^2). We can fix this by altering the algorithm slightly. There are two approaches:


    

  • Shuffle input randomly before sorting. This can trivially be done in O(n) time.
    • 

  • Actively find the median of a sample of data from the partition, this can be done in O(1) time.
    • 



Random shuffling optimization


The random approach is easy to code, works practically all of the time, and as such is often used. The idea is to quickly shuffle the list before sorting it. The likelihood of shuffling into a sorted list is astronomically unlikely, and is also more unlikely the larger the input.


Finding the median optimization


One of the most popular solutions is to use the “median of three” approach. Three elements (for example: the first, middle, and last elements) of each partition are chosen and the median is found between them. That item is then used as the pivot. This approach has the advantage that it can’t break down to O(n^2) time because we are guaranteed to never use the worst item in the partition as the pivot. That said, it can still be slower because a true median isn’t used.










Ready to get coding?


Try our coding courses 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/quick-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