Quicksort

Posted on:April 15, 2023 at 09:43 PM

Quick sort is an in-place sorting algorithm, meaning it directly transforms the original array and does not need to make copies of it which is good for performance. It uses recursion to break down the array into smaller sub-arrays that get sorted; this makes it fall into the divide-and-conquer category of algorithms. Each sub-array is a part of the original array; sorting them all will eventually lead to a complete solution.

var array = []int{89,60,23,99,10,52,5}
QuickSort(array,0,len(array)-1)

// output:
// [5 10 23 52 60 89 99]

How it works

The exact implementation of the Quick Sort algorithm will be different depending on the variation of the algorithm we choose to use. However, all the variations will have the same three main elements:

In this article, we will implement a variation known as the Hoare Partition Scheme.

Pivot

A pivot is a value inside of the array used to divide it into smaller sub-arrays; It separates the array or sub-array in two parts, elements less than the pivot and elements greater than the pivot.

Choosing the pivot is essential and can directly impact the algorithm’s performance. You could pick the pivot as either the leftmost or the rightmost value on the array; however, this can degrade the algorithm’s performance to the worst-case scenario in already sorted arrays as you would be picking either the lowest or highest value on the array and as such there would not be a good separation of elements. To fix this, we can choose the pivot by picking a random index in the array. Another option is to select the median of the array’s first, middle, and last elements. This method aims to balance the partition while avoiding the worst-case scenario of selecting the smallest or largest element as the pivot.

Partition

The partition is where most of the work happens. While the implementation can vary, the basic idea remains the same. Reorder the elements of the array such that all the values lower than the pivot are to the left and the values higher go to the right of the pivot; elements of equal value can go either way. Finally, return an index to be used as a pivot on the next function call.

Recursion

The Quick Sort function is called again for each sub-array created by the division of all values before the pivot and all values after the pivot. Eventually, no more sub-arrays are left, and the function returns, leaving the final order of the array ready to be used.

Implementation

QickSort Function

Our quick sort function is the entry point and takes in three arguments: the array of integers to be sorted and two integers that will be the start and end indexes of the array or sub-array.

We call the partition function that returns an index that is used as our pivot. Then we call the QuickSort function two times, dividing the array into two sub-arrays, one with the values between low and pivot and the other with the values after pivot and up to high. In our first call to Quicksort these values are the start and end of the array.

Since we are using recursion here, we must have an exit condition. In this case, every time we call QuickSort, we pass two integers that determine the start and end of the sub-arrays within the original array. If the values passed are the same, it tells us that the sub-array has only one element in it, and as such, there is nothing left to sort, so we do nothing and exit out of the function.

func QuickSort(array []int, low, high int) {
  if low < high {
    pivot := partition(array,low,high)

    QuickSort(array,low,pivot)
    QuickSort(array,pivot+1,high)
  }
}

The Partition

The partition function takes the same three values as the QuickSort function, an array of integers, a low value, and a high value. A pivot is then chosen based on requirements and preferences. Here we will select the first element in the array for the sake of simplicity.

func partition(array []int, low, high int){
  pivot := array[low]

  // ...
}

Pointers

Hoare’s partition scheme uses two pointers that start at both ends of the array, then move towards each other. All values lower than the pivot must go to the left of it, and all values higher than the pivot must go to the right. If the element to the left of the pivot has a greater value than the pivot and the element to the right of the pivot has a lower value than the pivot, the positions of these elements are swapped.

First, we declare the pointers with low and high as our initial values. Inside an infinite loop, we add the logic for the movement of each pointer:

// ...
left := low
right := high

for {
  // we move the left pointer to the right by adding 1 to it
  for array[left] < pivot {
    left++
  }

  // we move the right pointer to the left by subtracting one from it
  for array[right] > pivot {
    right--
  }

  // when the pointers meet or cross, we return
  if left >= right {
    return right
  }

  // swap the elements at the left and right of the pivot
  array[left],array[right] = array[right],array[left]
}

Final solution

The complete code looks like this:

func QuickSort(arr []int, low, high int) {
  if low < high {
    pivot := partition(arr, low, high)

    QuickSort(arr, low, pivot)
    QuickSort(arr, pivot+1, high)
  }
}

func partition(arr []int, low, high int) int {
  pivot := arr[low]

  left := low
  right := high

  for {
    // we move the left pointer to the right by adding 1 to it
    for arr[left] < pivot {
      left++
    }

    // we move the right pointer to the left by subtracting one from it
    for arr[right] > pivot {
      right--
    }

    // when the pointers meet or cross, we return
    if left >= right {
      return right
    }

    // swap the elements at the left and right
    arr[left], arr[right] = arr[right], arr[left]
  }
}

Our initial call to QuickSort looks like this:

package main

func main() {
  var arr = []int{89,60,23,99,10,52,5}
  QuickSort(arr, 0, len(arr)-1)
}

// output:
// [5 10 23 52 60 89 99]

Additional Resources

QuickSort - Wikipedia

Overview of quick sort - Khan Academy

Comparison Sorting Algorithms - University of San Francisco