Divide Conquer / Quicksort
What divide-conquer technique is used in quicksort? How partitioning works?
Partitioning Technique
Uses a divide-conquer technique called partitioning.
""" Quicksort / Recursive sorting algorithm
Uses a divide-conquer technique called partitioning.
For example, we can have a large number of unordered books.
We can separate the books in two piles A-M and N-Z, so the
the M would be the pivot.
Usually at start the item on the right is choosed as pivot.
We compare the left item with the pivot.
If left < right, we swap the items, and then move the left pointer with +1
When we rich the pivot, we automatically swap the items,
then call the recursion on the two new partitions.
2, 12, 9, 7, 8 / pivot=8, i=0, k=0
2< 8 / swap 2 with itself, i+1
2, 12, 9, 7, 8 / pivot=8, i=1, k=1
7< 8 / swap 7 with 12, i+1
1, 7, 9, 12, 8 / pivot=8, i=2, k=3
8=8 / swap pivot with 9
1, 7, 8, 12, 9
1, 7 / left partition
12, 9 / right partition
continue ...
"""
def quicksort(items, i=0, j=None):
if j == None:
j = len(items) - 1
if i > j:
return # Base case
pivot = items[j]
for k in range(i, j + 1):
if items[k] < pivot:
if i != k:
print(items, f"Swap items", items[k], "with", items[i])
items[i], items[k] = items[k], items[i] # swap items
i = i + 1 # move pointer
if items[k] == pivot:
if i != k:
print(items, "Move the pivot", pivot)
items[i], items[k] = items[k], items[i] # move pivot
print(items, "\n")
print(items[0:i], pivot, items[i+1:j])
quicksort(items, 0, i - 1) # sort left partition
quicksort(items, i + 1, j) # sort right partition
data = [8, 18, 4, 2, 10];
print("Data:", data) # [8, 18, 4, 2, 10]
quicksort(data);
print("Sorted:", data) # [2, 4, 8, 10, 18]
"""
Data: [8, 18, 4, 2, 10]
Sorted: [2, 4, 8, 10, 18]
Data: [8, 18, 4, 2, 10]
[8, 18, 4, 2, 10] Swap items 4 with 18
[8, 4, 18, 2, 10] Swap items 2 with 18
[8, 4, 2, 18, 10] Move the pivot 10
[8, 4, 2, 10, 18]
[8, 4, 2] 10 []
[8, 4, 2, 10, 18] Move the pivot 2
[2, 4, 8, 10, 18]
[] 2 [4]
[2, 4] 8 []
[2] 4 []
[] 2 []
[2, 4, 8, 10] 18 []
[2, 4, 8] 10 []
[2, 4] 8 []
[2] 4 []
[] 2 []
Sorted: [2, 4, 8, 10, 18]
"""
Runtime Comparison
Much slower than native sort(), with a limit around 480 items.
""" Quicksort / Algorithm runtime
Around 480 items maximum
"""
import random
import time
def quicksort(items, i=0, j=None):
if j == None:
j = len(items) - 1
if i > j:
return # Base case
pivot = items[j]
for k in range(i, j + 1):
if items[k] < pivot:
items[i], items[k] = items[k], items[i] # swap items
i = i + 1 # move pointer
if items[k] == pivot:
items[i], items[k] = items[k], items[i] # move pivot
quicksort(items, 0, i - 1) # sort left partition
quicksort(items, i + 1, j) # sort right partition
# Quicksort on 100 items
list = random.sample(range(0, 100), 100)
start = time.time()
quicksort(list)
t1 = time.time() - start
# Quicksort on 480 items (aprox. stack overflow limit)
list = random.sample(range(0, 480), 480)
start = time.time()
quicksort(list)
t2 = time.time() - start
# Python built-in sort
list = random.sample(range(0, 300000), 300000)
start = time.time()
list.sort()
t3 = time.time() - start
# Output times
print("quicksort() 100 items:", t1, "s")
print("quicksort() 480 items:", t2, "s")
print("sort() 300000 items:", t3, "s")
"""
quicksort() 100 items: 0.01451730728149414 s
quicksort() 480 items: 1.3930106163024902 s
sort() 300000 items: 0.06310772895812988 s
"""
