How do you implement Quick Sort in Swift?

Quick Sort (also called Partition-Exchange Sort) is an efficient divide and conquer algorithm developed by Tony Hoare in 1959. In worst case it takes O(n²) time but on average Quick Sort takes O(n log n) time and outperforms Merge and Heap Sort.

Define a method interface to call recursively

numbers is an array of unsorted Int s. Your target is to implement a Quick Sort algorithm for any array with items conform Comparable protocol.

To make in-place changes instead of returning a new array after each call array parameter is marked inout

Divide the problem into subproblems

To divide the problem into smaller subproblems you need to define a partition function. partition function uses a pivot value to separate the array into 2 subarrays and returns the index of the item which has a value higher than the items with lower index and lower than the items with higher index. Let’s don’t think about the partition function for now, it just enables us to divide the problem into 2 smaller subproblems.

Decide on the base case to stop recursion

Actually when you have a startIndex == endIndex you have a one element array and you can’t divide it into smaller arrays further.

Conquer the problem by implementing partition function

[2, 8, 1, 3, 7, 5, 4, 9, 6] — > you might set the right most value 6 as the pivot (You can pick the pivot element in different ways, implementation slightly changes)

partition function makes in-place changes on the array to separate the array into lower and higher subarrays.

Create a better interface for usage

Just to make usage of the quickSort function easier, you can supply a better interface.

And we are done implementing Quick Sort.

Download QuickSort.playground to see the full source code in action.