Hello, curious learner! You've made it more than halfway through our learning path, and today, we will embark on a journey through the Quick Sort world. Picture yourself organizing various items — like toys or books — by size or color. That's what Quick Sort does with spectacular speed. Are you ready to explore further? Fantastic! Let's get started.

Quick Sort is a clever little algorithm invented by a British computer scientist named Tony Hoare in 1959. It uses a strategy called divide-and-conquer to put elements in order. Quick Sort takes an array, selects a particular "pivot" element, and then places everything smaller than the pivot on one side and everything larger on the other.

Quick Sort has a three-step process:

1. Pick a random "pivot" element from the array.
2. Move all elements smaller than the pivot to one side and bigger ones to the other. This operation effectively divides the array into two parts, guaranteeing that all the elements will be kept within their part until the end of the sorting process.
3. Repeat steps 1 and 2 for each part until there are no more unsorted elements.

For example, let's say we have nine marbles with numbers: [3, 9, 4, 7, 5, 1, 6, 2, 8].

We choose a marble, called the pivot, to help us sort the others. For this example, let's pick 7 as the pivot.

After the first round of sorting, we rearrange the marbles so that all marbles smaller than 7 are on the left, and all marbles larger than 7 are on the right.

The result would look like this: [3, 4, 5, 1, 6, 2, 7, 9, 8].

At first, this might seem like a small change, but notice that the pivot (7) is now in its correct position in the sorted array! The important part is that now we can treat the left side [3, 4, 5, 1, 6, 2] and the right side [9, 8] as separate sections. These sections will never change or mix again, because the pivot is already in its place.

The Quick Sort algorithm requires two main functions to implement: Partition and QuickSort. Let's delve into each of them.

Go
Copy to clipboard
1func Partition(arr []int, start, end int) int {
2    pivot := arr[end] // choosing the last element as pivot
3    i := start - 1  // marking the index of the smaller element
4
5    for j := start; j < end; j++ {
6        // checking if the current element is smaller than the pivot
7        if arr[j] <= pivot {
8            i++
9            // swap arr[i] and arr[j]
10            arr[i], arr[j] = arr[j], arr[i]
11        }
12    }
13    // Swap arr[i+1] and arr[end] (or pivot)
14    arr[i+1], arr[end] = arr[end], arr[i+1]
15
16    return i + 1 // return the partition point
17}

The Partition function is responsible for splitting the array into elements lesser and greater than a chosen pivot element. Here, the pivot is the last element of the section defined by start and end. The index i tracks the position of the last element less than or equal to the pivot. As the function iterates through the array using index j, it compares each element to the pivot. If an element is smaller or equal, i is incremented, and the element at arr[j] is swapped with arr[i]. Finally, the pivot is swapped into its rightful position at i+1, and this index is returned, providing a point to divide the array for further sorting.

Next, we will cover the QuickSort function:

Go
Copy to clipboard
1func QuickSort(arr []int, start, end int) {
2    if start < end {
3        pivotIndex := Partition(arr, start, end) // find the pivot index
4        QuickSort(arr, start, pivotIndex - 1) // sort left part
5        QuickSort(arr, pivotIndex + 1, end)   // sort right part
6    }
7}

The QuickSort function is the main component that orchestrates the sorting process. It takes an array arr with two indices, start and end, marking the section of the array to work on. When start is less than end, the section is divided with the Partition function, determining the pivotIndex. After partitioning, QuickSort is recursively applied to the left part (start to pivotIndex - 1) and right part (pivotIndex + 1 to end). This recursive approach continues until all elements are sorted.

The efficiency or time complexity of Quick Sort varies. When sorting items, usually the more unique items, the quicker it is. In the best and average situations, Quick Sort works like a charm with a time complexity of $O(n \cdot \log(n))$. However, in the worst situation, where many items are the same (like a pile of identical blocks), it may take more time, resulting in a time complexity of $O(n^2)$.

Great job! We've untangled the concept of Quick Sort, broken it down piece by piece, and implemented it in Go. Now comes the fun part: we will reinforce what you've learned with practical exercises. Ready to dive in?