Quick Sort

class Solution(object): def quickSort(self, array): if len(array) == 0 or len(array) == 1: return array # pdb.set_trace() pivot_index = self.partition(array, 0, len(array)-1) # 1) inplace sort and 2) return the correct index of pivot array[0: pivot_index] = self.quickSort(array[0: pivot_index]) # sort left half array[pivot_index+1: len(array)] = self.quickSort(array[pivot_index+1: len(array)]) # 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 for j in range(p, 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 # swap a[i+1] and a[j] a[i], a[j] = a[j], a[i] # 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+1 # i is the correct index of the pivot