Recursive quick sort algorithm

demo.py

import os
import random
import sys


def main(env, prog, argv):
    # Set the seed constant, we will have the same result every time
    random.seed(1)
    elements = generate_unsorted_elements(10)
    deep = 0
    print(elements)
    quicksort(deep, 0, len(elements) - 1, elements)
    print(elements)


def quicksort(deep, left, right, elements):
    print(
        ' ' * deep * 4,
        'quicksort({!r}, {!r}, {!r}, {!r})'.format(deep, left, right, elements[left:right+1])
    )

    if left < right:
        p = partition(deep + 1, elements, left, right)
        quicksort(deep + 1, left, p - 1, elements)
        quicksort(deep + 1, p + 1, right, elements)
    print(
        ' ' * deep * 4,
        ' <- {!r}'.format(elements[left:right+1])
    )


def partition(deep, elements, left, right):
    pivot = elements[right]
    i = left - 1
    for j in range(left, right):
        if elements[j] < pivot:
            i += 1
            swap(elements, i, j)
    if elements[right] < elements[i+1]:
        swap(elements, i + 1, right)
    return i + 1


def swap(elements, index1, index2):
    tmp = elements[index1]
    elements[index1] = elements[index2]
    elements[index2] = tmp


def generate_unsorted_elements(n=100):
    elements = list(range(n))
    random.shuffle(elements)
    return elements


if __name__ == '__main__':
    main(os.environ, sys.argv[0], sys.argv[1:])

output_for_10_elements.txt

[6, 8, 9, 7, 5, 3, 0, 4, 1, 2]
 quicksort(0, 0, 9, [6, 8, 9, 7, 5, 3, 0, 4, 1, 2])
     quicksort(1, 0, 1, [0, 1])
         quicksort(2, 0, 0, [0])
          <- [0]
         quicksort(2, 2, 1, [])
          <- []
      <- [0, 1]
     quicksort(1, 3, 9, [7, 5, 3, 6, 4, 8, 9])
         quicksort(2, 3, 8, [7, 5, 3, 6, 4, 8])
             quicksort(3, 3, 7, [7, 5, 3, 6, 4])
                 quicksort(4, 3, 3, [3])
                  <- [3]
                 quicksort(4, 5, 7, [7, 6, 5])
                     quicksort(5, 5, 4, [])
                      <- []
                     quicksort(5, 6, 7, [6, 7])
                         quicksort(6, 6, 6, [6])
                          <- [6]
                         quicksort(6, 8, 7, [])
                          <- []
                      <- [6, 7]
                  <- [5, 6, 7]
              <- [3, 4, 5, 6, 7]
             quicksort(3, 9, 8, [])
              <- []
          <- [3, 4, 5, 6, 7, 8]
         quicksort(2, 10, 9, [])
          <- []
      <- [3, 4, 5, 6, 7, 8, 9]
  <- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

output_for_20_elements.txt

[11, 5, 17, 19, 9, 0, 16, 1, 15, 6, 10, 13, 14, 12, 7, 3, 8, 2, 18, 4]
 quicksort(0, 0, 19, [11, 5, 17, 19, 9, 0, 16, 1, 15, 6, 10, 13, 14, 12, 7, 3, 8, 2, 18, 4])
     quicksort(1, 0, 3, [0, 1, 3, 2])
         quicksort(2, 0, 1, [0, 1])
             quicksort(3, 0, 0, [0])
              <- [0]
             quicksort(3, 2, 1, [])
              <- []
          <- [0, 1]
         quicksort(2, 3, 3, [3])
          <- [3]
      <- [0, 1, 2, 3]
     quicksort(1, 5, 19, [11, 16, 5, 15, 6, 10, 13, 14, 12, 7, 17, 8, 19, 18, 9])
         quicksort(2, 5, 8, [5, 6, 7, 8])
             quicksort(3, 5, 7, [5, 6, 7])
                 quicksort(4, 5, 6, [5, 6])
                     quicksort(5, 5, 5, [5])
                      <- [5]
                     quicksort(5, 7, 6, [])
                      <- []
                  <- [5, 6]
                 quicksort(4, 8, 7, [])
                  <- []
              <- [5, 6, 7]
             quicksort(3, 9, 8, [])
              <- []
          <- [5, 6, 7, 8]
         quicksort(2, 10, 19, [10, 13, 14, 12, 11, 17, 15, 19, 18, 16])
             quicksort(3, 10, 15, [10, 13, 14, 12, 11, 15])
                 quicksort(4, 10, 14, [10, 13, 14, 12, 11])
                     quicksort(5, 10, 10, [10])
                      <- [10]
                     quicksort(5, 12, 14, [14, 12, 13])
                         quicksort(6, 12, 12, [12])
                          <- [12]
                         quicksort(6, 14, 14, [14])
                          <- [14]
                      <- [12, 13, 14]
                  <- [10, 11, 12, 13, 14]
                 quicksort(4, 16, 15, [])
                  <- []
              <- [10, 11, 12, 13, 14, 15]
             quicksort(3, 17, 19, [19, 18, 17])
                 quicksort(4, 17, 16, [])
                  <- []
                 quicksort(4, 18, 19, [18, 19])
                     quicksort(5, 18, 18, [18])
                      <- [18]
                     quicksort(5, 20, 19, [])
                      <- []
                  <- [18, 19]
              <- [17, 18, 19]
          <- [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
      <- [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
  <- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]