2 min read
Quick Sort With Python
Last Update: 2 October, 2022Quick sort is yet another divide and conquer algorithm that we can use to sort our arrays / lists. First of all we pick a pivot point. After choosing this pivot point (or value) we will put the smaller values to it's left and the greater values to it's right. We will divide our array / list by this pivot point and call our sorting algorithm recursively until we have sorted list.
§We Shall Begin
We can choose the pivot point in multiple ways. We can pick the first, last or middle value as our pivot as well as picking it randomly from our list. Picking the pivot won't matter a lot in our examples but in the future in order to avoid the worst case time complexity go ahead and pick the middle as the pivot. If you wanna learn more about the analysis just go ahead and watch this awesome video on the analysis of this algorithm.
§First Approach
As I just said there are multiple ways to create the same functionality and I actually will show 2 here in this post. In one of the algorithms we will have two indexes that will go through the array. They will start from different ends of the array. One will look for a value smaller than the pivot another will look for a value greater than the pivot. In both examples we will sort the arrays in ascending order (min to max).
This is the code for the first approach:
def partition(arr, low, high):
pivot = arr[high]
l = low
h = high - 1
while True:
while l <= h and arr[h] >= pivot:
h = h - 1
while l <= h and arr[l] <= pivot:
l = l + 1
if l <= h:
arr[l], arr[h] = arr[h], arr[l]
else:
break
arr[high], arr[l] = arr[l], arr[high]
return h
def quick_sort(arr, l, h):
if l < h:
p = partition(arr, l, h)
quick_sort(arr, l, p)
quick_sort(arr, p + 1, h)
if __name__ == "__main__":
data = [30, 20, 70, 10, 50, 90, 40]
print("Unsorted Array: ")
print(data)
size = len(data)
quick_sort(data, 0, size - 1)
print('Sorted Array in Ascending Order: ')
print(data)
§Second Approach
In the second way that I like to create the same algorithm is actaully much more popular than the first. In this one we pick the last value as the pivot. There are two indexes that will look for a greater and smaller value than the pivot. We will loop through the array looking for a value smaller than the pivot and when we find it we will increment the second index and swap them. When we are done with the iteration we last one in the array and the value smaller than the index and return the swapped value.
This the code for the second approach:
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSort(array, low, high):
if low < high:
pi = partition(array, low, high)
quickSort(array, low, pi - 1)
quickSort(array, pi + 1, high)
data = [30, 20, 70, 10, 50, 90, 40]
print("Unsorted Array: ")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order: ')
print(data)
§Complexity of Quick Sort
Worst case time complexity for this algorithm is O(N²) but as long as you don't have a sorted array you won't see this. To avoid having worst case O(N²) pick the pivot as median, random or as the middle. Average time complexity will be O(NlogN). N of the iteration of the array and logn for dividing the array into smaller arrays to sort. I suggest that you check out this video as I think this is the simplest, most understandble explanation I could find.
Each recursive call will use O(1). As we are not using any auxiliary arrays etc. for this algorithm our space complexity will depend on the height of the tree created by the recursions. So we can say that it's at least logn. In the worst case we will create as many stacks as the length of the array. In the worst case space complexity will be O(N). This worst case is also explained deeper in the video I left the link for right above.
Keep on learning!
Ilker AkbiyikTable of Contents
Related Posts
