Python Program for Quicksort

QuickSort is an in-place sorting operation that follows the divide and conquers method. In this tutorial, we will perform a QuickSort operation to sort an array.

QuickSort - A basic Introduction

The QuickSort algorithm operates by picking a pivot element from the array and splitting the other items into two sub-arrays based on whether they are bigger or less than the pivot.

Let us have a rough understanding of how this algorithm works:

1. A pivot element is used to split an array into subarrays.
2. The pivot element should be positioned in such a way that items less than the pivot are maintained on the left side of the pivot and elements bigger than the pivot are kept on the right side of the pivot while splitting the array.
3. The same method is used to split the left and right subarrays.
4. This method is repeated until each subarray has just one element.
5. The components have already been sorted at this stage. The items are finally merged to produce a sorted array.

The below diagram will help you for understanding better:

Algorithm

As of now, we have a rough understanding of the QuickSort operation. Let's have a look at the Algorithm followed by code for a better understanding:

1. Create a function partition()
2. Pass three parameters arr, low, high
3. Select rightmost element as pivot
4. declare pointer for greater element
5. traverse through all elements and compare them with pivot
6. If the smaller element is found swap them with pivot
7. Return the index position
8. Create a function QuickSort()
9. Pass three parameters arr, low, high
10. Find the pivot element
11. Do Recursive call on the left pivot and right pivot
12. The array is now sorted
13. Print the sorted array

Program for QuickSort

As discussed above in the algorithm, let us now dive into the programming part of the QuickSort operation influenced by the algorithm.

def partition(arr, low, high):
  # rightmost element as pivot
  pivot = arr[high]

  # pointer 
  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 the position 
  return i + 1

# QickSort
def QuickSort(arr, low, high):
  if low < high:
    # find pivot element 
    pivot = partition(arr, low, high)
    quickSort(arr, low, pivot - 1)
    quickSort(arr, pivot + 1, high)

# Driver Code
array = [9, 1, 8, 2, 7, 3, 5, 6, 4]
print("The Original Array:", array)

size = len(array)
quickSort(array, 0, size - 1)
print('The Sorted Array:', array)

The Original Array: [9, 1, 8, 2, 7, 3, 5, 6, 4]
The Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Conclusion

In this tutorial, we have performed a QuickSort operation in python to sort an array. We can use quick sort when time and space complexity matters. The best and average-case time complexity is O(n*log n) and the space complexity of quicksort is O(log n).