3 way Quick Sort in Python

Question

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

My code takes in 2 lines:

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

My code worked for the following inputs:

8, 1 3 5 4 2 6 4 4
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=' ')

Dharman · Accepted Answer · 2024-02-02 16:37:35Z

1

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

edited Feb 2, 2024 at 16:37

Dharman♦

33.9k27 gold badges106 silver badges157 bronze badges

answered Apr 17, 2022 at 11:39

A.H.M. Annur

1101 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Young42 Over a year ago

Thanks for your help! My code did work after removing the 2 lines. However, the randomized_quick_sort function was provided in the question and the only part I was supposed to edit was the partition3 function. Hence, I would like to clarify the following: 1. Would there be another way to resolve the issue? 2. Regarding your suggestion about using the random index as a pivot, do you mean letting the pivot = a[l] rather than pivot = a[r] in the first line of my partition3 function? That would make sense to me actually, as I'm implementing a random pivot!

A.H.M. Annur Over a year ago

I now see that the problem. It doesn't matter what random stuff happens to the array before you sort it. So here's my second attempt: 1) The problem was that when elif a[i] > pivot: is true you are swapping with the iterable_length and incrementing i without ever processing it. So adding i-=1 at the end of 'elif a[i] > pivot:` should solve this issue. 2) No, Using a random pivot will mean that you are actually using pivot = a[k]; where, k is a random index from l to r. Here's the link to the code (with random pivot) : Replit code link

Young42 Over a year ago

Thanks for your help! Could i clarify whats the purpose of tracking k using the code if j == k: k = i, considering how 'k' is not referenced anymore after creating the pivot?

A.H.M. Annur Over a year ago

Yes, I should have said, in the case of 3-way partition you don't actually need to use it, because you are processing everything but the pivot. In 2-way partition though, you would absolutely need to keep track of it as you are processing either larger or smaller numbers depending on ascending or descending order. As at the end of each partition you would have a final swap of the key and pivot which is: a[j+1], a[k] = a[k], a[j+1]. Again, in 3-way it isn't necessary. Just finding the random pivot will do. I like to keep track of it as it is the one I mess up the most.

Collectives™ on Stack Overflow

3 way Quick Sort in Python

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related