We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Quicksort 2 - Sorting
  2. Discussions

Quicksort 2 - Sorting

  • ravindravarma887
     + 1 comment

    How's this Quicksort implmentation if we're not doing partition in-place?

    This is my solution, it gives different result than what's expected for this question but this is much more optimal because we don't use any extra auxiliary space.

    def quickSort(arr, start, end):
    if(start < end):
        pIndex = partition(arr, start, end)
        quickSort(arr, start, pIndex - 1)
        quickSort(arr, pIndex + 1, end)
    if(len(arr[start: end + 1]) > 1):
        print(" ".join(arr[start: end + 1]))
def partition(arr, start, end):
    pivot = arr[start]
    pIndex = start + 1
    for i in range(start + 1, end+1):
        if(arr[i] < pivot):
            arr[i], arr[pIndex] = arr[pIndex], arr[i]
            pIndex += 1
            
    arr[start], arr[pIndex-1] = arr[pIndex-1], arr[start]
    return pIndex - 1
    
n = int(input())
arr = input().split()
quickSort(arr, 0, n-1)