Quick Sort Program in Python - Examples

Python - Quick Sort

In this tutorial, we will implement the Quick Sort Algorithm in Python. Quick Sort is a highly efficient sorting algorithm and is based on the divide-and-conquer principle. It works by selecting a 'pivot' element and partitioning the list into two sub-lists, one containing elements smaller than the pivot and the other containing elements greater than the pivot. The sub-lists are then sorted recursively.

Quick Sort Algorithm

The algorithm for Quick Sort is as follows:

  1. Pick an element from the list as a pivot (commonly the last element or the first element).
  2. Partition the list into two sub-lists: one containing elements smaller than the pivot, and the other containing elements greater than the pivot.
  3. Recursively apply the same process to the two sub-lists until the base case is reached (i.e., when a sub-list has zero or one element, indicating it is already sorted).

Python Program

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]  # last element as pivot
    left = [x for x in arr[:-1] if x < pivot]
    right = [x for x in arr[:-1] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

#input list
alist = [12, 11, 13, 5, 6]
print('Input List\n', alist)

#sort list
sorted_list = quick_sort(alist)
print('Sorted List\n', sorted_list)

Explanation:

  1. The base case checks if the list has only one or zero elements and returns the list itself, as it is already sorted.
  2. The pivot element is chosen as the last element of the list.
  3. The left sublist contains elements smaller than the pivot, and the right sublist contains elements greater than or equal to the pivot.
  4. The quick_sort function is called recursively on the left and right sublists.
  5. The final result is a concatenation of the left sublist, the pivot, and the right sublist.

Output

Input List
 [12, 11, 13, 5, 6]
Sorted List
 [5, 6, 11, 12, 13]

Optimizing Quick Sort

Although Quick Sort is a very efficient algorithm with an average time complexity of O(n log n), its performance can degrade to O(n^2) in the worst case when the pivot element is poorly chosen (e.g., the smallest or largest element). To avoid this, we can use techniques like randomized pivot selection or median-of-three pivoting.

Optimized Python Program (Randomized Pivot Selection)

import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)  # randomly choose a pivot
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

#input list
alist = [12, 11, 13, 5, 6]
print('Input List\n', alist)

#sort list
sorted_list = quick_sort(alist)
print('Sorted List\n', sorted_list)

Explanation of Optimization:

  1. The pivot is randomly chosen from the list using the random.choice function, which helps avoid the worst-case scenario where the pivot is always the smallest or largest element.
  2. This helps to improve the algorithm's performance and make it more reliable in practice.

Output

Input List
 [12, 11, 13, 5, 6]
Sorted List
 [5, 6, 11, 12, 13]

Summary

In this tutorial, we learned how to implement the Quick Sort algorithm in Python. We discussed how the algorithm works using the divide-and-conquer approach, and we implemented both a basic version and an optimized version using randomized pivot selection. Additionally, we demonstrated how Quick Sort can handle lists containing negative values.

Python Libraries