Now that we’ve seen an example of how quicksort works, let’s walk through the pseudocode of a quicksort function. The function itself is very simple, as shown below.
function QUICKSORT(ARRAY, START, END) (1) # base case size <= 1 if START >= END then (2) return (3) end if (4) PIVOTINDEX = PARTITION(ARRAY, START, END) (5) QUICKSORT(ARRAY, START, PIVOTINDEX – 1) (6) QUICKSORT(ARRAY, PIVOTINDEX + 1, END) (7) end function (8)
This implementation of quicksort uses a simple base case on lines 2 through 4 to check if the array is either empty, or contains one element. It does so by checking if the
START index is greater than or equal to the
END index. If so, it can assume the array is sorted and just return it without any additional changes.
The recursive case is shown on lines 5 – 7. It simply uses a helper function called
partition on line 5 to partition the array based on a pivot value. That function returns the location of the pivot value, which is stored in
pivotIndex. Then, on lines 6 and 7, the quicksort function is called recursively on the two partitions of the array, before and after the
pivotIndex. That’s really all there is to it!
Let’s look at one way we could implement the
partition function, shown below in pseudocode.
function PARTITION(ARRAY, START, END) (1) PIVOTVALUE = ARRAY[END] (2) PIVOTINDEX = START (3) loop INDEX from START to END (4) if ARRAY[INDEX] <= PIVOTVALUE (5) TEMP = ARRAY[INDEX] (6) ARRAY[INDEX] = ARRAY[PIVOTINDEX] (7) ARRAY[PIVOTINDEX] = TEMP (8) PIVOTINDEX = PIVOTINDEX + 1 (9) end if (10) end loop (11) return PIVOTINDEX – 1 (12)
This function begins on lines 2 and 3 by setting initial values for the
pivotValue by choosing the last element in the array, and then setting the
pivotIndex to 0. Then, the loop on lines 4 through 11 will look at each element in the array, determine if it is less than or equal to
pivotValue, and swap that element with the element at
pivotIndex if so, incrementing
pivotIndex after each swap.
At the end, the value that was originally at the end of the array will be at location
pivotIndex – 1, so we will return that value back to the
quicksort function so it can split the array into two parts based on that value.