2

I have this past year question based on the following scenario:

When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are equal to the pivot to the middle and then we recursively QuickSort those values on the left and those values on the right. Make the necessary changes to the partition method to achieve that.

Here's the implementation currently used:

// Quick Sort algorithm
public class QuickSort {

    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length-1);
    }

    private static void quickSort(int[] a, int i, int j) {
        if (i < j) {
            int pivotIdx= partition(a, i, j);
            quickSort(a, i, pivotIdx-1);
            quickSort(a, pivotIdx+1, j);
        }
    }

    private static void swap(int[] a, int pos1, int pos2) {
        int temp = a[pos1];
        a[pos1] = a[pos2];
        a[pos2] = temp;
    }

    private static int partition(int[] a, int i, int j) {
        // partition data items in a[i..j]
        int p = a[i]; // p is the pivot, the i-th item
        int m = i;    // Initially S1 and S2 are empty

        for (int k=i+1; k<=j; k++) { // process unknown region
            if (a[k] < p) { // case 2: put a[k] to S1
                m++;
                swap(a,k,m);
            }
        }

        swap(a,i,m); // put the pivot at the right place
        return m;    // m is the pivot's final position
    }

    public static void printArray(int[] a) {
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 7, 12, 3, 5, -6, 3, 8, 2, 10, -3 };

        printArray(arr);
        quickSort(arr);
        printArray(arr);
    }
}

I have some basic understanding of the quicksort algorithm introduced here, but I don’t really understand if the question actually gave me a hint on how to implement the algorithm, because in my opinion quicksort has to iterate through the list to make 2 partitions and dynamically decide position X where to put the pivot, which in this implementation is chosen to be the leftmost element of the input array. If this position X is dynamically decided, how exactly do you “group elements equal to pivot” to middle, and how exactly does it improve the algorithm?

1

2 Answers 2

1

The main idea is to solve this problem using a three-way partitioning strategy. See Dutch National Flag Problem for more details.

If you have a lot of duplicate elements, then your quicksort will try to place the each of the duplicate element separately at it's correct position. But you don't need to do that.

Let us see an example for what I claimed in the above statement:

Suppose you have an array like {4,6,4,3,4,2,5,4,1,4}. In this array you have the element 4 repeating 5 times. And when applying quick sort, and placing 4 at it's correct position, you will partition the array into 2 parts such that the left part contains all the elements smaller than or equal to 4 (but in no specific order) and the right part contains all the elements greater than 4. But that' the naive approach.

Let's see how can we improve this (given we have lot of duplicate elements)

When your quick sort finds 4 and it partitions the array to place this 4 in it's correct position, you can also keep track of all the equal elements (other elements of the array that are equal to 4) along with the smaller on left and greater on right.

So when partitioning instead of having 2 indices left and right (sub-array 0 to left contains all the elements lesser than or equal to the pivot and sub-array left to right contains all the elements greater than pivot and right to len(array)-1 are the elements yet to explored), you can have 3 indices which are described as below:

  • [0,left) - sub-array with elements lesser than pivot
  • [left, mid) - sub-array with elements equal to pivot
  • [mid, right] - sub-array with elements greater than pivot
  • [right, len(array)) - elements yet to be explored.

In this way your modified quicksort will take pivot only a lesser number of times (specifically saying, equal to count of unique elements in the array). And because of this there will be lesser number of recursive calls.

So this solution exploits the case for specific inputs where there are many duplicates (and so the more duplicate elements you have in your array, the better this modified variant of quicksort will perform)

Show me some code.

import java.util.Arrays;
import java.util.stream.IntStream;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 4, 1, 2, 4, 3, 5, 6, 2, 2, 2, 1, 1, 1};
        quickSort(arr);
        System.out.print("Sorted array: ");
        Arrays.stream(arr).forEach(i -> System.out.print(i + " "));
        System.out.println();
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start > end)
            return; // base condition

        System.out.print("Recursive call on: ");
        IntStream
                .rangeClosed(start, end)
                .map(i -> arr[i])
                .forEach(i -> System.out.print(i + " "));
        System.out.println();

        int n = arr.length;
        if (start < 0 || start >= n || end < 0 || end >= n)
            throw new IllegalArgumentException("the indices of the array are not valid");

        int pivot = arr[end];
        /*
            [start,left) - sub-array with elements lesser than pivot
            [left, mid) - sub-array with elements equal to pivot
            [mid, right] - sub-array with elements greater than pivot
            [right, end) - elements yet to be explored.
         */
        int left = start, mid = start, right = start;

        while (right != end) {
            if (arr[right] < pivot) {
                swap(arr, left, right);
                swap(arr, mid, right);
                left++;
                right++;
                mid++;
            } else if (arr[right] == pivot) {
                swap(arr, mid, right);
                mid++;
                right++;
            } else if (arr[right] > pivot) {
                right++;
            }
        }

        swap(arr, mid, right);
        System.out.println("Placed " + pivot + " at it's correct position");
        System.out.println();
        quickSort(arr, start, left - 1);
        quickSort(arr, mid + 1, end);
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

The output of the above code is:

Recursive call on: 2 3 4 1 2 4 3 5 6 2 2 2 1 1 1 
Placed 1 at it's correct position

Recursive call on: 2 4 3 5 6 2 2 2 3 4 2 
Placed 2 at it's correct position

Recursive call on: 4 3 5 3 4 6 
Placed 6 at it's correct position

Recursive call on: 4 3 5 3 4 
Placed 4 at it's correct position

Recursive call on: 3 3 
Placed 3 at it's correct position

Recursive call on: 5 
Placed 5 at it's correct position

Sorted array: 1 1 1 1 2 2 2 2 2 3 3 4 4 5 6 

The above output clearly shows that after placing the pivot at it's correct position, we recurse over two different arrays, but none of these 2 arrays have the previous pivot in them. (This is the optimization)

3
  • Thanks for your answer, I think theoretically it works, but I don't know how to implement it yet with actual code. There seems to be quite a few cases involving what kind of swaps that needs to be done to go to the "middle" position. My current idea is just initialising position of mid to be the middle of the array, which should increase as we fit more things in that region, so I'm not too convinced how my idea works. Feb 25, 2019 at 4:58
  • I've edited the answer to add the code of exactly the thing that I explained in words. Feb 25, 2019 at 17:02
  • Answer was very helpful (solved my problem and helped me to understand). But there is a small error in the implementation. Your code gives wrong output for array {-4, 0, 7, 4, 9, -5, -5, 1, -7, -1}. Because in case of (arr[right] < pivot): if left and mid are equal, you are swapping arr[right] back to the arr[right]. Instead, you should perform swap(arr, mid, right) then swap(arr, left, mid), gradually moving right element to mid first then to the left.
    – unlut
    Mar 1, 2023 at 19:38
0

Hi I tried to recreate it in python, hope this help

class Position:
    def __init__(self, val=0):
        self.val = val


def quickSort(start, end, arr):

    n = len(arr)

    start = (
        Position(start.val) if isinstance(start, Position) else Position(start)
    )
    left = (
        Position(start.val) if isinstance(start, Position) else Position(start)
    )
    right = (
        Position(start.val) if isinstance(start, Position) else Position(start)
    )
    mid = (
        Position(start.val) if isinstance(start, Position) else Position(start)
    )
    end = Position(end.val) if isinstance(end, Position) else Position(end)

    if start.val > end.val:
        return
    pivot = Position(arr[end.val])

    if start.val < 0 or start.val >= n or end.val < 0 or end.val >= n:
        raise AssertionError

    while right.val != end.val:

        if arr[right.val] < pivot.val:
            # left, right
            arr[left.val], arr[right.val] = arr[right.val], arr[left.val]
            # mid, right
            arr[mid.val], arr[right.val] = arr[right.val], arr[mid.val]
            left.val += 1
            right.val += 1
            mid.val += 1
        elif arr[right.val] == pivot.val:
            # mid, right
            arr[mid.val], arr[right.val] = arr[right.val], arr[mid.val]
            mid.val += 1
            right.val += 1
        elif arr[right.val] > pivot.val:
            right.val += 1

        # mid, right
        arr[mid.val], arr[right.val] = arr[right.val], arr[mid.val]
        start = start if isinstance(start, Position) else Position(start)
        left = left if isinstance(left, Position) else Position(left)
        mid = mid if isinstance(mid, Position) else Position(mid)
        end = end if isinstance(end, Position) else Position(end)


        quickSort(start.val, left.val - 1, arr)
        quickSort(mid.val + 1, end.val, arr)


arr = [2, 3, 4, 1, 2, 4, 3, 5, 5, 2, 2, 2, 1, 1, 1, 6, 7]

quickSort(0, len(arr) - 1, arr)
print(arr)

i think there still have flow in it, if there suggestion please correct it

Output:

[1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.