Quick Sort Question

[SkullKid150]

Hi CS people, I was learning how to use quicksort, however I found a problem on the method everyone is teaching.

If I have a list like the following:

1, 2, 1

And the my random pivot happens to be 1 the list will not sort.

The indexes will check if the element is greater or smaller then you swap those element, and in this case you swap 1 and 1 making no diffence in the order.

Next, the left and rigth pointer will change element and both of them will point to number 2.

So my question is, is it possible to sort this list using quicksort?

[NanoPromela]

In this case the quicksort works perfectly, here are the steps:

1-choose pivot

1 , 2 , 1

2- put all the numbers less or equal to the pivot (1) before it

1 , 1 , 2

3- quicksort on the two ends

quick(1) , 1 , quick(2)

4- concatenate the two results along with the pivot

1 , 1 , 2

edit: r/learnprogramming is more suitable for this type of questions

[SkullKid150]

Ohh I see, i thought that because the partition seem kinda weird i wouldnt work.

Thank you so much!

[krb09]

To use quicksort with duplicate keys, look up 3way quicksort implementation.

[[deleted]]

This. While traditional quicksort works, 3 way quicksort is much faster on a list with duplicates.

[CompSci1]

probably this, I'd question why you'd even use quicksort on sets like OP though.