Function quicksort

tools/python-3.11.9-amd64/Tools/demo/sortvisu.py:414–473

(array)

    array.message("Sorted")

def quicksort(array):
    size = array.getsize()
    array.reset("Quicksort")
    try:
        stack = [(0, size)]
        while stack:
            first, last = stack[-1]
            del stack[-1]
            array.show_partition(first, last)
            if last-first < 5:
                array.message("Insertion sort")
                for i in range(first+1, last):
                    j = i-1
                    while j >= first:
                        if array.compare(j, j+1) <= 0:
                            break
                        array.swap(j, j+1)
                        j = j-1
                continue
            array.message("Choosing pivot")
            j, i, k = first, (first+last) // 2, last-1
            if array.compare(k, i) < 0:
                array.swap(k, i)
            if array.compare(k, j) < 0:
                array.swap(k, j)
            if array.compare(j, i) < 0:
                array.swap(j, i)
            pivot = j
            array.show_pivot(pivot)
            array.message("Pivot at left of partition")
            array.wait(1000)
            left = first
            right = last
            while True:
                array.message("Sweep right pointer")
                right = right-1
                array.show_right(right)
                while right > first and array.compare(right, pivot) >= 0:
                    right = right-1
                    array.show_right(right)
                array.message("Sweep left pointer")
                left = left+1
                array.show_left(left)
                while left < last and array.compare(left, pivot) <= 0:
                    left = left+1
                    array.show_left(left)
                if left > right:
                    array.message("End of partition")
                    break
                array.message("Swap items")
                array.swap(left, right)
            array.message("Swap pivot back")
            array.swap(pivot, right)
            n1 = right-first
            n2 = last-left
            if n1 > 1: stack.append((first, right))
            if n2 > 1: stack.append((left, last))
        array.message("Sorted")