Sorting in Go

by Bautista Bambozzi — 15 min

In the course of this article, we'll do a no-fluff implementation of QuickSort in Go. We'll start off with some theory, and dive into the implementation. This article is intended for beginners.

QuickSort

QuickSort is a divide-and-conquer sorting algorithm that recursively divides an array into smaller sub-arrays based on a chosen pivot element, and then sorts these sub-arrays independently. It's able to do this comparison by relying on a pivot element. This pivot will be used as a point of reference to compare the values in the array (is this element larger? or smaller?) There is much debate regarding pivot selection in the stability of QuickSort. That is beyond the scope of the article, and is left as an exercise to the reader. We'll start of by creating a simple wrapper to the quickSort function that will hold the logic.


package quicksort

func Sort(arr []int) {
	quickSort(arr, 0, len(arr)-1) // TODO: Implement.
}

Let us then continue by building the function signature and the base-case.


func quickSort(arr []int, start int, endInclusive int) {
    if start >= endInclusive {
        return
    }
	// TODO select pivot
	// TODO iterate and update
	// TODO swap the pivot with the leftmost greater element
	// TODO recursively call the left and right subarrays
}

We'll start off by selecting the pivot and storing the index of the rightmost element that is smaller than the pivot. We'll update this as we iterate in the next section.


func quickSort(arr []int, start int, endInclusive int) {
    if start >= endInclusive {
		return
	}
	pivot := arr[endInclusive]
	lessThanPivotIdx := start
	// TODO iterate and update
	// TODO swap the pivot with the leftmost greater element
	// TODO recursively call the left and right subarrays
}

We then proceed to iterate the array and put all elements that are less than the pivot to the left of the lessThanPivotIdx.



func quickSort(arr []int, start int, endInclusive int) {
	if start >= endInclusive {
		return
	}
	pivot := arr[endInclusive]
	lessThanPivotIdx := start
	for i := start; i <= endInclusive; i++ {
		value := arr[i]
		if value < pivot {
			arr[i], arr[lessThanPivotIdx] = arr[lessThanPivotIdx], arr[i] // swap
			lessThanPivotIdx++
		}
	}
	// TODO swap the pivot with the leftmost greater element
	// TODO recursively call the left and right subarrays
}

Finally, we swap the pivot with the leftmost greater element. We can then guarantee that every element to the left of this index is now smaller than the pivot. This allows us to obtain two 'subarrays' which, while they aren't sorted yet, are guaranteed to be less and greater than the pivot, respectively.



    func quickSort(arr []int, start int, endInclusive int) {
	if start >= endInclusive {
		return
	}
	pivot := arr[endInclusive]
	lessThanPivotIdx := start
	for i := start; i <= endInclusive; i++ {
		value := arr[i]
		if value < pivot {
			arr[i], arr[lessThanPivotIdx] = arr[lessThanPivotIdx], arr[i] // swap
			lessThanPivotIdx++
		}
	}
	arr[lessThanPivotIdx], arr[endInclusive] = arr[endInclusive], arr[lessThanPivotIdx]
	// TODO recursively call the left and right subarrays
}

After we've finished the sorting logic, only one step is left to finish off the sort: recursively sorting the left and right subarrays!



    func quickSort(arr []int, start int, endInclusive int) {
	if start >= endInclusive {
		return
	}
	pivot := arr[endInclusive]
	lessThanPivotIdx := start
	for i := start; i <= endInclusive; i++ {
		value := arr[i]
		if value < pivot {
			arr[i], arr[lessThanPivotIdx] = arr[lessThanPivotIdx], arr[i] // swap
			lessThanPivotIdx++
		}
	}
	arr[lessThanPivotIdx], arr[endInclusive] = arr[endInclusive], arr[lessThanPivotIdx]
	quickSort(arr, start, lessThanPivotIdx-1)
	quickSort(arr, lessThanPivotIdx+1, endInclusive)
}