Search code examples
algorithmsortingcomputer-sciencequicksort

What if Elements Being Compared in Hoare's Quicksort Are the Same?


Consider an unsorted list 9,3,5,3,9, with 5 being the pivot. When the elements at index 0 and index 4 are compared, their values are equal to each other, and both are greater than the pivot value. What would happen in this case? They can't be swapped, because there would still be a 9 in the 'less than' section. Is one of the 9's just moved over to the other side. And the same goes for the 3's. What happens to them?


Solution

  • Those elements are not compared to each other. In Hoare partition scheme, the array is scanned from the left for the first element > pivot, and then scanned from the right for the first element < pivot. That means that the first swap will be for array[0] = 9 with array [3] = 3. After that no more swaps occur. Depending on Hoare partition implementation and data pattern, the pivot element can end up as the last element of the left partition or as the first element of the right partition. Elements equal to pivot are left in place in either left or right partition, and dealt with in later recursions.