Quicksort intermediate list printing Python

Question

The prompt for this HackerRank problem has me stumped. It is essentially a quicksort implemention but as an exception you are required to print the intermediate (or semi-sorted) "original" array in its entirety each iteration.

My working code without printing intermediates. It works as expected.

def quicksort(array):

    if len(array) > 1:
        left = 0
        right = len(array)-2
        pivot = len(array)-1
        while left <= right:
            while array[left] < array[pivot]:
                left +=1
            while array[right] > array[pivot]:
                right -= 1
            if left <= right:
                array[left], array[right] = array[right], array[left]
                left += 1
                right -=1
        array[left], array[pivot] = array[pivot], array[left]

        return quicksort(array[0:left]) + quicksort(array[left::])
    else:
        # return single element arrays
        return array

And below is my attempt at implementing a way to print intermediates. I.e. I am trying to keep the indices separate instead of just passing the spliced list like the above example so that I will always have access to the full array in the first function parameter.

def quicksort2(array, start=0, end=None):
    size = len(array[start:end])


    if size > 1:
        left = start
        right = len(array[start:end])-2
        pivot = len(array[start:end])-1
        print("Print")
        print("left: {}\nright: {}\npivot: {}".format(left, right, pivot))
        while left <= right:
            while array[left] < array[pivot]:
                left +=1
            while array[right] > array[pivot]:
                right -= 1
            if left <= right:
                array[left], array[right] = array[right], array[left]
                left += 1
                right -=1
        array[left], array[pivot] = array[pivot], array[left]
        print(array)
        print("the end is {}".format(end))

        size = len(array[0:left]) # 3

        return quicksort2(array, start=0, end=left) + quicksort2(array, start=left, end=left+(size-len(array)))
    else:
        # return single element arrays
        return array



if __name__ == '__main__':
    size = int(input()) # size is 7
    arr = [int(i) for i in input().split()]
    print(quicksort2(arr, start=0, end=size))

However, now the list are not fully sorted on the second half of the input list so I am sure it has something to do with the end keyword parameter that is passed at the bottom of the quicksort2 definition.

Answer 1

Figured out what I was doing wrong. I really needed to use the Lomuto Partitioning method in order to satisfy the requirements of the print statements.

Code for anyone searching for this in the future

def partition(array, lo, hi):
    pivot_index = hi
    pivot_value = array[pivot_index]
    store_index = lo

    for i in range(lo, hi):
        if array[i] <= pivot_value:
            array[i], array[store_index] = array[store_index], array[i]
            store_index += 1
    array[pivot_index], array[store_index] = array[store_index], array[pivot_index]
    return store_index 


def quicksort(array, lo, hi):
    if lo < hi:
        p = partition(array, lo, hi)
        print(' '.join([str(i) for i in array]))
        quicksort(array, lo, p-1)
        quicksort(array, p+1, hi)

if __name__ == '__main__':
    size = int(input())
    ar = [int(i) for i in input().split()]
    quicksort(ar, 0, size-1)