How does the presence of identical elements in a sortable sequence affect quicksort?

Question

Programming

How does the presence of identical elements in a sortable sequence affect quicksort? on the number of assignments, and in general?

Answer 1

Let's say all the elements of the array are the same (forgive me, but in our collective farm, sequences are not sorted).
Then any division of the array into two sortable subarrays goes crookedly: all array elements get off on one side (to the left, to the right - it depends on the implementation) from the median.
Total: sorting time of the order of n^2 instead of the coveted n*log(n). The number of assignments is fucking n-1 (how many times the median is chosen) - as opposed to the number of comparisons.
Have a good session.

Answer 2

It depends on how to write sorting - it all depends on small details.
If you do not remember that the elements can be the same, it is easy to fall into O (n ^ 2).
It can be written in such a way that the number of comparisons does not change, but the same elements will be swapped with each other for nothing.
You can be afraid at every step that the same elements may meet, and divide the array into three parts - less than the reference, equal to it and greater than it. Then, with a large number of identical elements, it will work quickly, but when there are no identical elements, then the number of comparisons will be 1.6 times greater.
When splitting, you can see if at least one element was equal to the reference one, and separate equal ones only if it was. Then it will be bad when each element occurs exactly twice.
There are other ways. And all this will be quicksort. If everything is written correctly, then the more identical elements, the faster the sorting will be.