Just a post for reviewing QuickSort. Every time you prepare interviews, you will need to review this classic sorting algorithm.
Code
#
class QuickSort():
def sort(self, arr):
self.sort_helper(arr, 0, len(arr) - 1)
return arr
def sort_helper(self, arr, left, right):
if left >= right + 1:
return
pivot = left
for i in xrange(left, right):
if arr[i] < arr[right]:
arr[i], arr[pivot] = arr[pivot], arr[i]
pivot += 1
arr[right], arr[pivot] = arr[pivot], arr[right]
self.sort_helper(arr, left, pivot - 1)
self.sort_helper(arr, pivot + 1, right)
if __name__ == "__main__":
print QuickSort().sort([4, 3, 2, 3, 4, 5])
Idea
Use a pointer pivot to act as a delimiter: elements before pivot are smaller than pivot and those after pivot are larger than pivot. It is essentially a divide-and-conquer idea. Imagine pivot will be finally set to arr[right], i.e., elements smaller than arr[right] and larger than arr[right] are going to be separated. To do so, we initialize pivot to be arr[left] (line 12). You can think of current pivot as the first element larger than arr[right] during the loop in line 14~17. At line 19, you set the pivot as arr[right].
Note that QuickSort can happen in place. In worst case, you repeatedly get skewed partitions before and after `pivot`. Therefore you can get as many as $latex n$ (the original array size) recursive calls of `sort_helper`. So the time complexity of QuickSort is $latex O(n^2)$ in the worst case but on average it should be $latex O(nlogn)$.
The space complexity in the worst case is $latex O(n)$ as you can have as many as $latex n$ recursive calls, each taking up one stack frame. There is some trick to make the space complexity $latex O(logn)$ even under the worst case. To do so, you only recur sort_helper on the smaller partition and sort the other (larger) partition in an iterative way:
#
class QuickSort():
def sort(self, arr):
self.sort_helper(arr, 0, len(arr) - 1)
return arr
def sort_helper(self, arr, left, right):
while left < right:
pivot = left
for i in xrange(left, right):
if arr[i] < arr[right]:
arr[i], arr[pivot] = arr[pivot], arr[i]
pivot += 1
arr[right], arr[pivot] = arr[pivot], arr[right]
if pivot - 1 - left + 1 < right - (pivot + 1) + 1:
self.sort_helper(arr, left, pivot - 1)
left = pivot + 1
else:
self.sort_helper(arr, pivot+1, right)
right = pivot -1
if __name__ == "__main__":
print QuickSort().sort([4, 3, 2, 3, 4, 5, 1])
Reference:
http://www.geeksforgeeks.org/quicksort-tail-call-optimization-reducing-worst-case-space-log-n/