This is the fifth post in the Data Structures and Algortihms today I will be learning about another sorting algorithm called Quick Sort. Quick Sort is another sorting algorithm just like the Merge Sort that is based on divide and conquer technique. Quick sort is faster than some other sorting algorithms like Merge sort and Heap Sort. It is one of the most popular and most implemented sorting algorithm in the world.
Image Courtesy: Wikipedia
Quick Sort uses partition just like Merge Sort uses merge to sort the list. Partition is a way of separating list of elements around a single element. Let this element be "x". This algorithm will separate elements such that the elements on the left are smaller than x and the elements on the right are bigger than x.
nums = [4, 3, 2, 5, 6, 9, 8, 7, 1, 0]
partition(nums, pivot, low, high)
# [1, 0, 3, 2, 4, 5, 6, 9, 8, 7]
# This is ^ Pivot
# [1, 0, 3, 2] smaller than pivot
# [5, 6, 9, 8, 7] larger than pivot
Now we can see how Quick Sort works.
How Quick Sort Works?
Quick Sort works by selecting a single element as a pivot and sort all other elements according to the pivot such that every element that is smaller than the pivot is placed on the left side of the pivot element and every element that is bigger than the pivot is placed on the right side of the pivot element.
This forms a list where every element on the left of pivot is smaller than the pivot and every element on the right side of the pivot is bigger than the pivot after that it runs recursively on the left side of the list and on the right side of the list to sort those sides and then thier smaller lists and so on and on until the whole list is sorted.
1. [4, 3, 2, 5, 6, 9, 8, 7, 1, 0]
2. [[3, 2, 1, 0], 4, [5, 6, 9, 8, 7]]
3. [[[2, 1, 0], 3], 4, [5, [6, 9, 8, 7]]]
4. [[[1, 0], 2], 3], 4, [5, [6, 9, 8, 7]]]
5. [[[[0], 1], 2], 3], 4, [5, [6, [9, 8, 7]]]]
6. [[[[0], 1], 2], 3], 4, [5, [6, [7, [9, 8]]]]]
7. [[[[0], 1], 2], 3], 4, [5, [6, [7, [8, [9]]]]]]
8. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In most of the implementations the first element of the list is selected as the pivot element but you can also selec pivot as:
- The last element of the list
- Random element from the list
- Some element that is already in the sorted position
Complexity
Quick Sort is a very efficient algorithm for sorting a large sets of data with only having the time complexity of O(n^2) in the Worst Case. In Best Case it has a time complexity of O(n*log(n)) and the same goes for the Average Case.
zainsci