Quick Sort

class Solution(object): def quickSort(self, array): if len(array) == 0 or len(array) == 1: return array pivot_index = self.partition(array, 0, len(array)-1) # 1) inplace sort and 2) return the correct index of pivot self.quickSort(array, 0, pivot_index-1) # sort left half self.quickSort(array, pivot_index+1, len(array)-1) # sort right half return array def partition(self, a, p, r): """ a: input array p: the starting index of the subarray. This element is included in the subarray. r: the ending index of the subarray. This element is included in the subarray. """ i = p-1 # all elements in a[p, ... i] (both boundary points included) are no greater than x x = a[r] # pivot j = p while(j < r): # all elements in a[i+1, j-1] (both boundary points included) are greater than x # all elements in a[j, ... r-1] (both boundary points included) are not inspected # a[r] is the pivot if a[j] <= x: i += 1 j += 1 else: # swap a[i+1] and a[j] a[i+1], a[j] = a[j], a[i+1] i += 1 j += 1 # j finished traversaling , now j == r # put the pivot to the correct place a[i+1], a[r] = a[r], a[i+1] return i # i is the correct index of the pivot