Quicksort
p96 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]
"""
Timer
Much slower than native sort(), with a limit around 480 items.
""" Quicksort / Algorithm runtime
Around 480 items maximum
"""
import random
import time
start, end = 0, 0
def timer(func):
def wrapper(*args, **kwargs):
global start, end
if start == 0:
start = time.time()
result = func(*args, **kwargs)
end = time.time()
return result
return wrapper
@timer
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
@timer
def native_sort(items):
return items.sort()
# Time
lst = random.sample(range(0, 100), 100)
start, end = 0, 0
quicksort(lst); t1 = end - start
lst = random.sample(range(0, 480), 480) # stack overlow limit
start, end = 0, 0
quicksort(lst); t2 = end - start
lst = random.sample(range(0, 300000), 300000)
start, end = 0, 0
native_sort(lst); t3 = end - start
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
"""
➥ Questions