When exploring a programming language, it is always a good idea to get familiar with syntax by implementing general data structures and algorithms. Quicksort is one of the best options. It is a practical and widely used sorting algorithm because of its excellent average complexity of O(n log n). However, we also note that in the worst case, it has O(n^2) complexity, though this behavior is rare.

Quicksort only has two basic operations, which are swapping items and partitioning a section of the array. We will first implement these two operations and then put them into our final quicksort function.

Swapping

swap function swaps two items within a given array by providing their indexes.

def swap(arr, index1, index2):
	arr[index1], arr[index2] = arr[index2], arr[index1]

Partitioning

The goal for partitioning is to divide an array into two sections separated by pivot item, and all items within left section are smaller than pivot item, while the right section contain all the items that are larger than pivot item. Here are basic steps to partition an array:

  1. Pick up a pivot item in the array, then swap it with the first item.
  2. Create two pointers (left and right) at the second and last items in the array respectively.
  3. While the left pointer has the value that is less than pivot value, move it to the right by adding 1. If the left pointer has the value that is not less than pivot value or reach the last item, then stop and move to next step.
  4. While the right pointer has the value that is larger than or equal to pivot value, move it to the left by subtracting 1. If the right pointer has the value that is not larger than pivot value or reach the first item, then stop and move to next step.
  5. If the left pointer is less than to the right pointer, then swap two items which are pointing by them.
  6. Move left pointer to right by adding 1, and move right pointer to left by subtracting 1.
  7. If the left pointer is not equal to or larger then right pointer, then go to step 1. Otherwise, swap the first item with item pointing by right pointer, and finish partition.
 1 def partition(arr, first, last):
 2 	# step 1
 3 	pivot = first + int((first - last) / 2)
 4 	swap(arr, first, pivot)
 5 
 6 	# step 2
 7 	left = first + 1
 8 	right = last
 9 
10 	while True:
11 		# step 3
12 		while arr[left] < arr[first]:
13 			if left == last:
14 				break
15 			left += 1
16 
17 		# step 4
18 		while arr[right] >= arr[first]:
19 			if right == first:
20 				break
21 			right -= 1
22 
23 		# step 7
24 		if left >= right:
25 			break
26 
27 		# step 5
28 		swap(arr, left, right)
29 
30 		# step 6
31 		left += 1
32 		right -= 1
33 
34 	# step 7
35 	swap(arr, first, right)
36 	return right

Quicksort

Quicksort is based on the Divide and Conquer algorithm design paradigm. Following the Divide and Conquer paradigm, we first partition the whole array, and then divide it into a left section and a right section of the pivot item. After that, we recursively partition all sections which produce sub-sections of sections until all those sub-sections contain only no more than one item. Now each item within the array has all smaller items on their left and larger items on their right, in other words, the array is in ascending order.

 1 def quick_sort(arr, first=None, last=None):
 2 	if arr is None:
 3 		return arr
 4 
 5 	if first is None:
 6 		first = 0
 7 
 8 	if last is None:
 9 		last = len(arr)-1
10 
11 	if first < last:
12 		pivot = partition(arr, first, last)
13 		quick_sort(arr, first, pivot-1)
14 		quick_sort(arr, pivot+1, last)
15 
16 	return arr

What do you think?

What if we want to return the array in descending order?