Quick Sort

quicksort.py

'''
From Python Algorithms - Mastering Basic Algorithms in the Python Language Book
'''
def partition(seq):
    pi, seq = seq[0], seq[1:]         # Pick and remove the pivot
    lo = [x for x in seq if x <= pi]  # All the small elements
    hi = [x for x in seq if x > pi]   # All the large ones
    return lo, pi, hi                 # pi is "in the right place"


def quicksort(seq):
    if len(seq) <= 1:                            # Base case
        return seq
    lo, pi, hi = partition(seq)                  # pi is in its place
    return quicksort(lo) + [pi] + quicksort(hi)  # Sort lo and hi separately

from random import randrange
seq = [randrange(1000) for i in range(100000)]
import cProfile
cProfile.run('quicksort(seq)')

quicksort_hoare_like.py

def partition(A, p, r):
    i = p
    j = r
    m = A[i]
    while True:
        while A[j] > m and i < j:
            j -= 1
        if i < j:
            A[i], A[j] = A[j], A[i]
            i += 1
        while A[i] < m and i < j:
            i += 1
        if i < j:
            A[i], A[j] = A[j], A[i]
            j -= 1
        if i == j:
            break
    return i

def quicksort(A, p, r):
    # print(A, p, r, p < r)
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)


from random import randrange
seq = [randrange(100000) for i in range(100000)]
import cProfile
cProfile.run('quicksort(seq, 0, len(seq)-1)')

quicksort_N_Lomuto.py

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1


def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q - 1)
        quicksort(A, q + 1, r)


from random import randrange
seq = [randrange(1000) for i in range(100000)]
import cProfile
cProfile.run('quicksort(seq, 0, len(seq) - 1)')

randomized_quicksort.py

from random import randint


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1


def randomized_partition(A, p, r):
    i = randint(p, r)
    A[r], A[i] = A[i], A[r]
    return partition(A, p, r)


def randomized_quicksort(A, p, r):
    if p < r:
        q = randomized_partition(A, p, r)
        randomized_quicksort(A, p, q - 1)
        randomized_quicksort(A, q + 1, r)


from random import randrange
seq = [randrange(1000) for i in range(100000)]
import cProfile
cProfile.run('randomized_quicksort(seq, 0, len(seq) - 1)')