Quicksort Python

qsort.py

"""
A practice of different implementations of Quicksort
Programming Pearls: column 11
"""

import random
import time
import sys
sys.setrecursionlimit(15000)


def median(lst, i, j, k):
    if (lst[i] - lst[j]) * (lst[j] - lst[k]) >= 0:
        return j
    elif (lst[i] - lst[k]) * (lst[k] - lst[j]) >= 0:
        return k
    else:
        return i


def swap(lst, i, j):
    lst[i], lst[j] = lst[j], lst[i]


def isort(lst, l, u):
    for i in range(l, u+1):
        for j in range(i, l, -1):
            if lst[j] < lst[j-1]:
                swap(lst, j-1, j)
            else:
                break


def qsort1(lst, l, u):
    # sort elements in lst in range [l, u]
    if l >= u:
        return
    m = lst[l]
    j = l + 1  # j is the first position of elements >= m
    for i in range(l+1, u+1):
        if lst[i] < m:
            swap(lst, i, j)
            j += 1
        else:
            pass

    swap(lst, l, j-1)  # move m to pos j-1
    
    qsort1(lst, l, j-2)
    qsort1(lst, j, u)


def qsort2(lst, l, u):
    # avoid quadratic runtime on degenerated input like list of equal items
    if l >= u:
        return
    m = lst[l]
    # adjust i and j to compensate for the do-while loop
    i = l
    j = u + 1
    while True:
        while True:
            i += 1
            if i >= j or lst[i] >= m:
                break
        while True:
            j -= 1
            if i >= j or lst[j] <= m:
                break
        if i >= j:
            break
        swap(lst, i, j)

    # when the loop ends, i is either
    # 1. at u+1 if lst[l+1 .. u] < m
    # 2. pointing at the first item >= m

    # move m to i-1
    swap(lst, l, i-1)

    qsort2(lst, l, i-2)
    qsort2(lst, i, u)


def qsort3(lst, l, u):
    # randomize to improve avg runtime of worst case of sorted input
    if l >= u:
        return
    r = random.randint(l, u)  # randint outputs in range [a, b]
    swap(lst, l, r)
    m = lst[l]
    i = l
    j = u + 1
    while True:
        while True:
            i += 1
            if i >= j or lst[i] >= m:
                break
        while True:
            j -= 1
            if i >= j or lst[j] <= m:
                break
        if i >= j:
            break
        swap(lst, i, j)

    swap(lst, l, i-1)

    qsort3(lst, l, i-2)
    qsort3(lst, i, u)


def qsort4(lst, l, u):
    # use insertion sort if length is shorter than cutoff
    if l >= u:
        return
    if u - l < 8:
        isort(lst, l, u)
        return
    r = random.randint(l, u)
    swap(lst, l, r)
    m = lst[l]
    i = l
    j = u + 1
    while True:
        while True:
            i += 1
            if i >= j or lst[i] >= m:
                break
        while True:
            j -= 1
            if i >= j or lst[j] <= m:
                break
        if i >= j:
            break
        swap(lst, i, j)

    swap(lst, l, i-1)

    qsort4(lst, l, i-2)
    qsort4(lst, i, u)


def qsort_mo3(lst, l, u):
    # use median-of-3 instead of randomization
    if l >= u:
        return
    mid = l + (u - l) // 2
    r = median(lst, l, mid, u)
    swap(lst, l, r)
    m = lst[l]
    i = l
    j = u + 1
    while True:
        while True:
            i += 1
            if i >= j or lst[i] >= m:
                break
        while True:
            j -= 1
            if i >= j or lst[j] <= m:
                break
        if i >= j:
            break
        swap(lst, i, j)

    swap(lst, l, i-1)

    qsort3(lst, l, i-2)
    qsort3(lst, i, u)


def _sort(lst, *args):
    lst.sort()


for sort in [isort, qsort1, qsort2, qsort3, qsort_mo3, qsort4, _sort]:
    for size in [100, 1000, 10000]:
        lists = [[random.randint(1, 100) for i in range(size)],
                 [random.uniform(1, 100) for i in range(size)],
                 [1] * size,
                 list(range(size)),
                 list(reversed(range(size)))]
        for i, lst in enumerate(lists):
            t = time.time()
            sort(lst, 0, len(lst) - 1)
            print('%s\t%-5d\t%d\t%.6f' % (sort, size, i, time.time() - t))
            assert lst == sorted(lst)
    print('---')

"""
<function isort at 0x7ff36509c158>	100  	0	0.000532
<function isort at 0x7ff36509c158>	100  	1	0.000510
<function isort at 0x7ff36509c158>	100  	2	0.000029
<function isort at 0x7ff36509c158>	100  	3	0.000029
<function isort at 0x7ff36509c158>	100  	4	0.001014
<function isort at 0x7ff36509c158>	1000 	0	0.059944
<function isort at 0x7ff36509c158>	1000 	1	0.060971
<function isort at 0x7ff36509c158>	1000 	2	0.000355
<function isort at 0x7ff36509c158>	1000 	3	0.000361
<function isort at 0x7ff36509c158>	1000 	4	0.110460
<function isort at 0x7ff36509c158>	10000	0	5.960896
<function isort at 0x7ff36509c158>	10000	1	5.964972
<function isort at 0x7ff36509c158>	10000	2	0.003444
<function isort at 0x7ff36509c158>	10000	3	0.003497
<function isort at 0x7ff36509c158>	10000	4	11.710843
---
<function qsort1 at 0x7ff36509c1e0>	100  	0	0.000132
<function qsort1 at 0x7ff36509c1e0>	100  	1	0.000137
<function qsort1 at 0x7ff36509c1e0>	100  	2	0.000381
<function qsort1 at 0x7ff36509c1e0>	100  	3	0.000232
<function qsort1 at 0x7ff36509c1e0>	100  	4	0.000545
<function qsort1 at 0x7ff36509c1e0>	1000 	0	0.001723
<function qsort1 at 0x7ff36509c1e0>	1000 	1	0.001862
<function qsort1 at 0x7ff36509c1e0>	1000 	2	0.022117
<function qsort1 at 0x7ff36509c1e0>	1000 	3	0.022699
<function qsort1 at 0x7ff36509c1e0>	1000 	4	0.057847
<function qsort1 at 0x7ff36509c1e0>	10000	0	0.037839
<function qsort1 at 0x7ff36509c1e0>	10000	1	0.023128
<function qsort1 at 0x7ff36509c1e0>	10000	2	2.217233
<function qsort1 at 0x7ff36509c1e0>	10000	3	2.350833
<function qsort1 at 0x7ff36509c1e0>	10000	4	6.198187
---
<function qsort2 at 0x7ff36509c268>	100  	0	0.000114
<function qsort2 at 0x7ff36509c268>	100  	1	0.000114
<function qsort2 at 0x7ff36509c268>	100  	2	0.000124
<function qsort2 at 0x7ff36509c268>	100  	3	0.000340
<function qsort2 at 0x7ff36509c268>	100  	4	0.000335
<function qsort2 at 0x7ff36509c268>	1000 	0	0.002503
<function qsort2 at 0x7ff36509c268>	1000 	1	0.001900
<function qsort2 at 0x7ff36509c268>	1000 	2	0.001861
<function qsort2 at 0x7ff36509c268>	1000 	3	0.034884
<function qsort2 at 0x7ff36509c268>	1000 	4	0.034567
<function qsort2 at 0x7ff36509c268>	10000	0	0.023675
<function qsort2 at 0x7ff36509c268>	10000	1	0.025189
<function qsort2 at 0x7ff36509c268>	10000	2	0.026697
<function qsort2 at 0x7ff36509c268>	10000	3	3.428645
<function qsort2 at 0x7ff36509c268>	10000	4	3.427722
---
<function qsort3 at 0x7ff36509c2f0>	100  	0	0.000204
<function qsort3 at 0x7ff36509c2f0>	100  	1	0.000219
<function qsort3 at 0x7ff36509c2f0>	100  	2	0.000259
<function qsort3 at 0x7ff36509c2f0>	100  	3	0.000178
<function qsort3 at 0x7ff36509c2f0>	100  	4	0.000188
<function qsort3 at 0x7ff36509c2f0>	1000 	0	0.002608
<function qsort3 at 0x7ff36509c2f0>	1000 	1	0.002712
<function qsort3 at 0x7ff36509c2f0>	1000 	2	0.002628
<function qsort3 at 0x7ff36509c2f0>	1000 	3	0.002180
<function qsort3 at 0x7ff36509c2f0>	1000 	4	0.002317
<function qsort3 at 0x7ff36509c2f0>	10000	0	0.032483
<function qsort3 at 0x7ff36509c2f0>	10000	1	0.031766
<function qsort3 at 0x7ff36509c2f0>	10000	2	0.033661
<function qsort3 at 0x7ff36509c2f0>	10000	3	0.024567
<function qsort3 at 0x7ff36509c2f0>	10000	4	0.024413
---
<function qsort_mo3 at 0x7ff36509c400>	100  	0	0.000216
<function qsort_mo3 at 0x7ff36509c400>	100  	1	0.000230
<function qsort_mo3 at 0x7ff36509c400>	100  	2	0.000226
<function qsort_mo3 at 0x7ff36509c400>	100  	3	0.000180
<function qsort_mo3 at 0x7ff36509c400>	100  	4	0.000167
<function qsort_mo3 at 0x7ff36509c400>	1000 	0	0.002490
<function qsort_mo3 at 0x7ff36509c400>	1000 	1	0.002840
<function qsort_mo3 at 0x7ff36509c400>	1000 	2	0.002647
<function qsort_mo3 at 0x7ff36509c400>	1000 	3	0.001860
<function qsort_mo3 at 0x7ff36509c400>	1000 	4	0.001944
<function qsort_mo3 at 0x7ff36509c400>	10000	0	0.032109
<function qsort_mo3 at 0x7ff36509c400>	10000	1	0.033564
<function qsort_mo3 at 0x7ff36509c400>	10000	2	0.034924
<function qsort_mo3 at 0x7ff36509c400>	10000	3	0.024981
<function qsort_mo3 at 0x7ff36509c400>	10000	4	0.026833
---
<function qsort4 at 0x7ff36509c378>	100  	0	0.000160
<function qsort4 at 0x7ff36509c378>	100  	1	0.000158
<function qsort4 at 0x7ff36509c378>	100  	2	0.000132
<function qsort4 at 0x7ff36509c378>	100  	3	0.000101
<function qsort4 at 0x7ff36509c378>	100  	4	0.000131
<function qsort4 at 0x7ff36509c378>	1000 	0	0.002065
<function qsort4 at 0x7ff36509c378>	1000 	1	0.002181
<function qsort4 at 0x7ff36509c378>	1000 	2	0.002009
<function qsort4 at 0x7ff36509c378>	1000 	3	0.001389
<function qsort4 at 0x7ff36509c378>	1000 	4	0.001644
<function qsort4 at 0x7ff36509c378>	10000	0	0.024966
<function qsort4 at 0x7ff36509c378>	10000	1	0.028642
<function qsort4 at 0x7ff36509c378>	10000	2	0.029702
<function qsort4 at 0x7ff36509c378>	10000	3	0.017914
<function qsort4 at 0x7ff36509c378>	10000	4	0.020895
---
<function _sort at 0x7ff36509c488>	100  	0	0.000015
<function _sort at 0x7ff36509c488>	100  	1	0.000016
<function _sort at 0x7ff36509c488>	100  	2	0.000002
<function _sort at 0x7ff36509c488>	100  	3	0.000002
<function _sort at 0x7ff36509c488>	100  	4	0.000002
<function _sort at 0x7ff36509c488>	1000 	0	0.000162
<function _sort at 0x7ff36509c488>	1000 	1	0.000140
<function _sort at 0x7ff36509c488>	1000 	2	0.000008
<function _sort at 0x7ff36509c488>	1000 	3	0.000010
<function _sort at 0x7ff36509c488>	1000 	4	0.000010
<function _sort at 0x7ff36509c488>	10000	0	0.001828
<function _sort at 0x7ff36509c488>	10000	1	0.001842
<function _sort at 0x7ff36509c488>	10000	2	0.000086
<function _sort at 0x7ff36509c488>	10000	3	0.000088
<function _sort at 0x7ff36509c488>	10000	4	0.000090
---
"""