Teaching Kids Programming – QuickSort Algorithm Simply Explained (Python)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Quicksort is a well-known sorting algorithm – as the name suggests, it sorts quickly.

The idea of QuickSort algorithm is to first pick a pivot number (which can be first, last, middle, or random). Then, we go through the list to partition the list into three parts. The smaller elements, the equal parts, and the bigger parts.

Then, we call the quicksort function to sort the smaller and bigger parts, and the final sorted list would be the concatenation of smaller, equal, and the bigger parts.

If the pivot number is not picked wisely, for example, if we always pick the smallest or largest element in the list, and the quick sorting algorithm will sort 1 element at a time O(N) and it needs N iterations, which degenerate the algorithm to O(N^2) quadratic.

However, if everytime the pivot element roughtly splits the smaller and larger parts into similar sizes, then the complexity of QuickSort will be O(NLogN) average.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import random
 
def quickSort(n):
    if len(n) <= 1:
        return n
    pivot = random.choice(n)
    eq, smaller, larger = [], [], []
    for i in n:
        if i == pivot:
            eq += [i]
        elif i > pivot:
            larger += [i]
        else:
            smaller += [i]
    return quickSort(smaller) + eq + quickSort(larger)

import random

def quickSort(n):
    if len(n) <= 1:
        return n
    pivot = random.choice(n)
    eq, smaller, larger = [], [], []
    for i in n:
        if i == pivot:
            eq += [i]
        elif i > pivot:
            larger += [i]
        else:
            smaller += [i]
    return quickSort(smaller) + eq + quickSort(larger)

We can use the list comprehension in Python to make the implementation look Pythonic Nicer!

1
2
3
4
5
6
7
8
9
10

import random
 
def quickSort(n):
    if len(n) <= 1:
        return n
    pivot = random.choice(n)
    eq = [x for x in n if x == pivot]
    smaller = [x for x in n if x < pivot]
    larger = [x for x in n if x > pivot]
    return quickSort(smaller) + eq + quickSort(larger)

import random

def quickSort(n):
    if len(n) <= 1:
        return n
    pivot = random.choice(n)
    eq = [x for x in n if x == pivot]
    smaller = [x for x in n if x < pivot]
    larger = [x for x in n if x > pivot]
    return quickSort(smaller) + eq + quickSort(larger)

You may also read this: How to Implement Quicksort Algorithm in Python – the Pythonic Way

The quick sorting algorithm is not stable – as the keys of same values after sorting may not keep their original order.

Sorting Algorithms (Teaching Kids Programming Tutorials)

• Teaching Kids Programming – Bubble Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – MergeSort Simply Explained
• Teaching Kids Programming – QuickSort Algorithm Simply Explained
• Teaching Kids Programming – Selection Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – Insertion Sort in Python (Simple Sorting Algorithm)
• Teaching Kids Programming – Counting Sort Algorithm in Python

–EOF (The Ultimate Computing & Technology Blog) —