Partitioning and Sorting Arrays with Many Repeated Entries

In the QuickSort Algorithm, we do the partitioning of the array into smaller arrays. We partition our array into two smaller arrays such that elements of one sub-array are smaller than the pivot element and the elements of the other sub-array are greater than the pivot element.

Algorithm:

1. Create a helper function quickSortHelper() to partition the array, which will have three parameters, given our array, an integer low, and an integer high.
   1. Select any value of the array and name it as “pivot”. Let’s assume the last element of the array(arr[high]) as our pivot.
   2. Make an integer variable named ‘small’ which will have an index of the smallest element i.e low-1.
   3. Then run a loop from low to (high - 1) and for elements check if their value is greater than or less than the pivot. If their value is less, then increment ‘small’ and then swap that element with ‘small’.
   4. After exiting this loop and swapping arr[small+1] with arr[high], return the partitioning index i.e small+1.
2. In the function quickSort, we’ll also have three arguments i.e our array, an integer low, and an integer high.
   1. If low < high, then in order to sort the smaller elements and the greater elements we make an integer variable partitonIndex  = quickSortHelper(arr, low, high).
   2. Then one by one, sort the elements before partition by calling quickSortHelper(arr, low, partitonIndex -1), and after partition by calling quickSortHelper(arr, partitionIndex + 1, high).

The idea is to apply the divide and conquer approach to sort the array. As the name says this algorithm is inspired by the Dutch Flag which is made up of three colors: Red, White, and Blue. With respect to a particular element(‘pivot’), we can put the array elements groups into different groups. The red group will contain all the elements which are lesser than the pivot, the blue group will have elements that are greater than the pivot and finally, and the white group will have elements that are equal to the pivot element.

The algorithm is as follows:

1. Select any value of the array, let’s say this value is “pivot”.
2. We will rearrange the elements of the given array into 3 partitions, and the leftmost partition will consist of all elements less than “pivot”, the middle partition will contain all elements equal to “pivot”, the right partition will contain all elements greater than “pivot”.
3. The steps to partition the given array by using the last element of the array as the  “pivot” are as follows:
   1. Fix the last element of the given array as “pivot”.
   2. Initialize variables “start” and “mid” with the starting index of the array. Also, initialize a variable “end” with the last index of the array.
   3. While “mid” is less than or equal to “end” do the following steps:
      1. If the value at index “mid” is less than “pivot” then swap the values at indices start and mid. Also, increment the value of mid and start by 1.
      2. If the value at index “mid” is greater than “pivot” then swap the values at indices “end” and “mid”. Also, decrement the value of “end” by 1.
      3. If the value at index “mid” is equal to “pivot” then increment the value of “mid” by 1.
4. After partitioning the array, sort the leftmost and the rightmost partitions by recursively calling the function. The middle partition is already sorted since all values in the middle partition are equal.

Similar to the QuickSort algorithm start by making a pivot element. Let’s call the elements that are not visited the ‘notVisited’ elements and as soon as we’re done traversing the array we can visualize our array as a composition of 5 regions.

1. On each of the ends, we will have regions that have values equal to that of the pivot element.
2. In the center will lie our ‘notVisited’ region which will keep on decreasing as we keep visiting the array elements.
3. To the right of this ‘notVisited’ region will lie the greater region which has elements greater than the pivot element.
4. To the left of this ‘notVisited’ region will lie the lesser region which has elements smaller than the pivot element.
5. When we have visited all the elements and we are left with only 4 regions(2 equal regions, the lesser region, and the greater region), we move both the equal regions to the center.
   1. To achieve this, swap the elements in the first equal region(on the left side) with the elements of the lesser region.
   2. Similarly, swap the elements in the second equal region(on the right side) with the elements of the greater region.
6. Now we have 3 partitions, we can apply our sorting algorithm to sort the lesser region and the greater region.

Algorithm:

1. Select any value of the array, let’s call this value as “pivot”.
2. Then we initialize two integer variables named ‘low’, and ’high’, where ‘low’  points to the first index and ‘high’ points to the last index of the array.
3. We also need to keep a count of the equal elements lying on the leftmost and rightmost side of the array. Hence make two integer variables ‘leftCount’ and ‘rightCount’ and initialize both of them equal to 0.
4. Create a helper function quickSortHelper() to partition the array, which will have three parameters, our given array, an integer low, and an integer high.
   1. While the value of ‘low’ is lesser than the pivot element, keep moving in the right direction and incrementing ‘left’ by 1.
   2. While the value of ‘high’ is greater than the pivot element, keep moving in the left direction and decreasing ‘high’ by 1.
   3. At the point where low becomes equal to high and arr[low]=pivot, swap arr[leftCount] with arr[low], and increment both leftCount and low by 1.
   4. After the above operation check if ‘low’ is greater than or equal to ‘high’, if this condition is true, exit the loop, else swap ‘low’ and ‘high’ and move forward.
   5. If arr[low] = pivot, swap arrr[leftCount] wiht arr[low] and similiarly if arr[high] = pivot, swap arrr[rightCount] wiht arr[high]. After checking both these conditions simply increment ‘low’ by 1 and decrease ‘high’ by 1.
5. Also, move the elements equal to the pivot element to the ends of the array and at the same time increment ‘leftCount’ or ‘rightCount’ accordingly.
6. Then move the elements from the left and right ends of the array to the center of the array.
7. In the end, we will recursively call the function to sort the lesser and greater region.