Quick Sort¶

Temporal complexity: nlog(n)¶


QuickSort is a sorting algorithm that uses a pivot value. It is a recursive algorithm that called a helper function called QuickSelect.¶


QuickSelect¶

QuickSelect takes a list in argument and outputs the list with one element (called the pivot) at its right position with elements smaller than it at its left and elements greater than it at its right.¶
1) Chooses an arbitrary pivot (generally 1st or last value of the array)¶
2) If the pivot is not the last element, swap the pivot with last element¶
3) Initialize the delimiter to the 1st element : it represents the limit between elements smaller and greater than the pivot (at the end of the loop it is the index of the first element greter than the pivot)¶
4) Iterate over every elements with i, for every element smaller than the pivot make sure it is one the left on the delimiter:¶
a) swap the positions of the delimiter and i ie the current element¶
b) note that the element ant the delimiter index is greater than the pivot except when i is equal to the delimiter (at this stage it means we still havent check the element) but in this case swapping does not change anything¶
5) At the end of the loop the delimiter index contains the first element greater than the pivot and delimiter-1 contains the last element smaller than the pivot¶
6) Finally just swap the delimiter and the pivot value: the pivot is at its right position.¶


Visualisation from Wikipedia of the QuickSelect algorithm¶


QuickSort¶

1) Calls QuickSelect to place one element at its right place and split the array in two¶
2) Recursively calls QuickSort on the left array with elements smaller than the pivot and on the right array with elements greater than the pivot¶
3) Stop when the array the stop are of length less than 1¶


Implementation¶

In [20]:
def quickselect(left, right, nums):
    # Last element will be the pivot and the first element the initial delimiter
    pivot, delimiter = nums[right], left
    
    for i in range(left, right):
        if nums[i] <= pivot:
            # Swapping values smaller than the pivot to the front
            nums[i], nums[delimiter] = nums[delimiter], nums[i] # 'nums[i]' is now at the index 'delimiter'
            delimiter += 1 # 'nums[i]' is now on the left of the delimiter
            
    # Finally swapping the last element with the pointer indexed number
    nums[delimiter], nums[right] = nums[right], nums[delimiter]
    return delimiter

def quicksort_helper(left, right, nums):
    # Call the algorithm if left < right ie there are elements to sort; otherwise the elements are already sorted
    if left < right:
        pivot = quickselect(left, right, nums)
        quicksort_helper(left, pivot-1, nums)  # Recursively sorting the left values
        quicksort_helper(pivot+1, right, nums)  # Recursively sorting the right values
    return nums

def quicksort(nums):
    return quicksort_helper(0, len(nums)-1, nums)
In [21]:
quicksort([2, 5, 6, 1, 4, 6, 2, 4, 7, 8])
Out[21]:
[1, 2, 2, 4, 4, 5, 6, 6, 7, 8]