quicksort

quicksort.py

input_file = open("QuickSort.txt")
input_array = []
for line in input_file:
    input_array.append(int(line))


def partition(A, l, r):
    if r - l <= 0:
        return 0

    first = A[l]
    middle = A[int((r +l) / 2)]
    last = A[r]

    largest = max(first, middle, last)
    smallest = min(first, middle, last)

    if smallest < last < largest:
        A[l], A[r] = A[r], A[l]
    elif smallest < middle < largest:
        A[l], A[int((r + l) / 2)] = A[int((r + l) / 2)], A[l]

    p = A[l]

    i = l + 1
    for j in range(l + 1, r + 1):
        if A[j] < p:
            A[i], A[j] = A[j], A[i]
            i += 1

    A[l], A[i - 1] = A[i - 1], A[l]

    return r - l + partition(A, l, i - 2) + partition(A, i, r)


times = partition(input_array, 0, len(input_array) - 1)
print(times)