How do I fix this Quick sort implemented with python so that it returns the correctly sorted array?

Question

I am trying to program a quick sort but there seems to be a problem with the code as the list outputted is not sorted but I have checked many implementations and mine is very similar so I do not know the issue.

class QuickSort:
    def quickSort(self, list, low, high):
        if (low >= high):
            return 
        else:
            leftPointer = low
            rightPointer = high
            pivot = list[high]
            while (leftPointer < rightPointer):
                while (leftPointer < rightPointer and list[leftPointer] < pivot):
                    leftPointer += 1
                while (leftPointer < rightPointer and list[rightPointer] > pivot):
                    rightPointer -= 1
            list[leftPointer], list[rightPointer] = list[rightPointer], list[leftPointer]
         list[high], list[leftPointer] = list[leftPointer], list[high]
         self.quickSort(list, low, rightPointer - 1)
         self.quickSort(list, rightPointer + 1, high)
       return list


list = [50, 49, 19, 4, 9]
quick = QuickSort()
print(quick.quickSort(list, 0, len(list) - 1))

I tried printing the list before the recursive call and found that the list is actually sorted at one point but the returned list is not correct.

Answer 1

class QuickSort:
    def quickSort(self, input_list, low, high):
        if high - low == 1 and input_list[low] <= input_list[high]:
            return
        if (low >= high):
            return 
        else:
            leftPointer = low
            rightPointer = high - 1
            pivot = input_list[high]
            while (leftPointer < rightPointer):
                while (leftPointer < rightPointer and input_list[leftPointer] < pivot):
                    leftPointer += 1
                while (leftPointer < rightPointer and input_list[rightPointer] > pivot):
                    rightPointer -= 1
                input_list[leftPointer], input_list[rightPointer] = input_list[rightPointer], input_list[leftPointer]
            if input_list[leftPointer] > input_list[high]:
                input_list[leftPointer], input_list[high]  = input_list[high], input_list[leftPointer]
            self.quickSort(input_list, low, leftPointer)
            self.quickSort(input_list, leftPointer+1, high)
        return input_list

list = [50, 49, 19, 4, 9]
quick = QuickSort()
print(quick.quickSort(list, 0, len(list) - 1))
print(quick.quickSort([1,2,3,4,5], 0, 4))
print(quick.quickSort([4, 3, 2,1], 0, 3))
print(quick.quickSort([8,6,7,5,3,0,9], 0, 6))

Changes:

• indented the line that swaps the numbers less than and greater than the pivot
• changed the logic for swapping the pivot number to handle cases where the left pointer is already less than the pivot
• added an extra check at the top to handle cases where len(input_list) == 2 and its already ordered

Answer 2

### Code provided for QuickSort Algorithm (.py)
##### works well even with Duplicate elements, combination of +ve, -ve integers

unsortedArray = [11, 5, 9, 63, 14, 52, 31, -1, 0, -555, -63]

def quickSort(unsortedArray, trgIndex):
    ind = trgIndex
    trg = unsortedArray[ind]

    j = len(unsortedArray) - 1

    for k in range(0, len(unsortedArray)):
        if unsortedArray[k] > trg:
            while j >= k:
                if unsortedArray[j] <= trg:
                    unsortedArray[k], unsortedArray[j] = unsortedArray[j], unsortedArray[k]
                    break
                j -= 1

    unsortedArray[ind], unsortedArray[j] = unsortedArray[j] , unsortedArray[ind]
    return unsortedArray

def initialFunction():
    c = 0
    for itr in range(0, len(unsortedArray) - 1):    
        if unsortedArray[itr] > unsortedArray[itr + 1]:
            getSorted = quickSort(unsortedArray, itr)
            # print(get)

    for itr in range(0, len(unsortedArray) - 1):    
        if unsortedArray[itr] <= unsortedArray[itr + 1]:
            c += 1

    if c != len(unsortedArray) - 1:
        initialFunction()

    elif c == len(unsortedArray) - 1:
        print(getSorted)

initialFunction()

Do not forget to UpVote