quicksort.py

# Quicksort Algorithm - sort a sequence in place, for additional convenience
# returns the sequence.
# Time complexity: nlgn (average case) and n^2 (worst case)
 
# Script is intended to be run with Python3, but is Python2 compatible.
# If running the script with Python2, range() function will return a list.
# Consider changing it to xrange(), if running with Python2.


def quicksort(seq, start, end):
    if start < end:
        pivot = partition(seq, start, end)
        quicksort(seq, start, pivot-1)
        quicksort(seq, pivot+1, end)
        return seq


def partition(seq, start, end):
    pivot = seq[end]
    i = start - 1
    for j in range(start, end):
        if seq[j] <= pivot:
            i += 1
            seq[i], seq[j] = seq[j], seq[i]
    seq[i+1], seq[end] = seq[end], seq[i+1]
    return i + 1


if __name__ == '__main__':
    seq = [2, 8, 7, 1, 3, 5, 6, 4]
    print(quicksort(l, 0, len(seq) - 1))