This is the video I am referring to: https://youtu.be/ywWBy6J5gz8

This is the code that I have tried in python:

def partition(arr, low, high):
 
    pivot = arr[low]
    i = low   1
    j = high

    switch = True

    while (True):
        while switch == True:
            while arr[j] >= pivot and i < j:
                j -= 1
            pos = arr.index(pivot)
            arr[j] , arr[pos] = arr[pos], arr[j]
            switch = False

        while switch == False:
            while arr[i] <= pivot and i < j:
                i  = 1
            pos2 = arr.index(pivot)
            arr[i] , arr[pos2] = arr[pos2], arr[i]
            switch = True

        if i >= j:
            return j
 

def quickSort(arr, low, high):

    if high - low >= 1:
        pivot = partition(arr, low, high)
        quickSort(arr, low, pivot - 1)
        quickSort(arr, pivot   1, high)


arr = [3, 1, 5, 7, 6, 2, 4]
quickSort(arr, 0, len(arr) - 1)
print("Sorted array:")
print(arr)

Output: Sorted array: [1, 2, 3, 6, 4, 5, 7]

What am I doing wrong??

CodePudding user response：

There are a few issues in your code:

• In the video the pivot is one of the two persons that are stepped forward, the one with the dark hat (without the light decoration). There is no third person in this process, yet you define i and j as separate indices from the index where the pivot resides. To harmonise your code with the video you should initialise i to low. The two persons that stepped forward represent i and j in your code.

• The partitioning should really end when i >= j, yet if this condition occurs in the first block, then the second block still executes and performs an undesired swap there. You should immediately exit the function when i >= j. If you code it like that, you don't need this switch anymore either.

• The call of arr.index(pivot) is not required, nor efficient, nor suggested by the video. You already know where the pivot is, as it is one of the two persons that are stepped forward (dark hat), so i or j.

Here is the corrected code:

def partition(arr, low, high):
    pivot = arr[low]
    i = low
    j = high

    while True:
        while arr[j] >= pivot:
            j -= 1
            if i >= j:
                return i
        arr[j], arr[i] = pivot, arr[j]
        while arr[i] <= pivot:
            i  = 1
            if i >= j:
                return j
        arr[i], arr[j] = pivot, arr[i]

This now implements what is shown in the video.