Skip to content

Instantly share code, notes, and snippets.

@adonese
Created March 22, 2016 09:25
Show Gist options
  • Save adonese/4bf34d5b57ee0358626c to your computer and use it in GitHub Desktop.
Save adonese/4bf34d5b57ee0358626c to your computer and use it in GitHub Desktop.
Quicksort 3-way partition algorithm
def partition3(A, l, r):
"""
partition3: A partition for quicksort algorithm. We'll use the 3-way to handle few equal elements in array (happens
a lot in practical use.)
This function is called from the main function quick_sort.
"""
lt = l # We initiate lt to be the part that is less than the pivot
i = l # We scan the array from left to right
gt = r # The part that is greater than the pivot
pivot = A[l] # The pivot, chosen to be the first element of the array, that why we'll randomize the first elements position
# in the quick_sort function.
while i <= gt: # Starting from the first element.
if A[i] < pivot:
A[lt], A[i] = A[i], A[lt]
lt += 1
i += 1
elif A[i] > pivot:
A[i], A[gt] = A[gt], A[i]
gt -= 1
else:
i += 1
return lt, gt
def quick_sort(A, l, r):
"""
quick_sort: One of the most used sorting algorithm.
It makes to recursive calls. One to sort the left part separately, other for sorting the right part.
The partition key is chosen randomly via ``random.randint(l, r)`` and it's between the ``l, r``.
PARAMETERS:
-----------
A: Array or the sequence that we want to sort.
l: The lower bound of the array that we want to sort. It's not very important we might replace it by a wrapper function
that only takes in an array as input. In this case it's the first element in the left part of the array.
r: It's the same as l, only differs as it's the first element from the end.
RETURNS:
-------
Sorted list A.
"""
if l >= r:
return
k = random.randint(l, r)
A[k], A[l] = A[l], A[k]
lt, gt = partition3(A, l, r)
quick_sort(A, l, lt - 1)
quick_sort(A, gt + 1, r)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment