I'm trying to implement a 3 way partition quick sort code in Python.

My code takes in 2 lines:

1. The first is the number of integers to be sorted
2. The second is the array of integers to be sorted

My code worked for the following inputs:

1. 8, 1 3 5 4 2 6 4 4
2. 5, 2 3 9 2 2

However, when it is tested with the following input: 10, 10 9 8 7 6 5 4 3 2 1

My code does not sort the array of integers properly?

May I know why my code does not work for the last case?

This is my code:

def partition3(a, l, r):
    #write your code here
    pivot = a[r]
    i = l
    j = l - 1
    iterable_length = r 
        
    while i <= iterable_length:
        if a[i] < pivot:
            j  = 1
            a[i], a[j] = a[j], a[i]
        
        elif a[i] > pivot:
            a[i], a[iterable_length] = a[iterable_length], a[i]
            iterable_length -= 1
            
        i  = 1
        
    return j, iterable_length 1

def randomized_quick_sort(a, l, r):
    if l >= r:
        return
    k = random.randint(l, r)
    a[l], a[k] = a[k], a[l]
    #use partition3
    # m = partition2(a, l, r)
    m1, m2 = partition3(a, l, r)
    randomized_quick_sort(a, l, m1);
    randomized_quick_sort(a, m2, r);


if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    randomized_quick_sort(a, 0, n - 1)
    for x in a:
        print(x, end=' ')

CodePudding user response：

Welcome to StackOverflow. The problem seems to be here:

k = random.randint(l, r)
a[l], a[k] = a[k], a[l]

You are getting a random index k and using it to swap two elements a[l] and a[k] randomly. Removing the two lines should give the correct output only looks right in certain circumstances.

I'm assuming you're looking to create a random pivot point, in which case you should use the random index as a pivot inside the partition3 function.

Edit: The problem was not processing/skipping the new element at a[i] after swapping inside a[i] > pivot:. It should be:

elif a[i] > pivot:
  a[i], a[iterable_length] = a[iterable_length], a[i]
  iterable_length -= 1
  # don't forget to process new element at a[i]
  i -= 1