Is this partition algorithm correct?

Question

I've been looking at the partition function in the book "Cracking the Coding Interview" (5e, page 119). I've copied it below:

int partition(int arr[], int left, int right){
    int pivot = arr[(left + right) /2 ]; // Pick pivot point
    while (left <= right) {
        // Find element on left that should be on right
        while (arr[left] < pivot) left++;
        // Find the element on right that should be on left
        while (arr[right] > pivot) right--;
        // Swap elements, and move left and right indicies
        if (left <= right) {
            swap(arr, left, right); // swaps elements
            left++;
            right--;
        }
    }
    return left;
}

Given this array:

1 2 3 4 5 6 3

This is how the partition worked out for me in steps

4 is the pivot value. left = 0, right = 6
left = 3, right = 6. Swap.

1 2 3 3 5 6 4
left = 4, right = 4. Exit

However, the array I ended up with:

1 2 3 3 5 6 4

Is not partitioned around 4. Have I followed the steps incorrectly or is the algorithm incorrect? I've double checked my reproduction of the algorithm and I've copied it correctly.

Also, I'm not positive why partition is returning left, is it returning the pivot?

I understand the Wikipedia implementation of partition and quicksort, but I'm trying to wrap my head around what's going on here.

Why do you say it is not partitioning around 4? Are you expecting 4 not to move? — Vaughn Cato
– Vaughn Cato, Commented Jul 23, 2012 at 3:44
Well in my solution above, 5 and 6 are still to the left of 4. Doesn't that mean it hasn't partitioned? — oxuser
– oxuser, Commented Jul 23, 2012 at 3:47
@LastStar007 left and right indicate the start and end indicies of the array. This is an in-place partition. — oxuser
– oxuser, Commented Jul 23, 2012 at 3:48

Vaughn Cato · Accepted Answer · 2012-07-23 03:55:02Z

7

The goal of the partition is to break the array into two segments. The first segment contains elements [1,2,3,3]. All of these values are less than or equal to four. The second segment contains elements [5,6,4]. All of these values are greater than or equal to four.

The partition function returns where the second segment begins. In this case it starts at index 4.

edited Jul 23, 2012 at 3:55

answered Jul 23, 2012 at 3:49

Vaughn Cato

64.5k5 gold badges87 silver badges135 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Adrian McCarthy Nov 4 at 1:31

@Vaughn Cato: The first segment contains values strictly less than the pivot value, not less than or equal to it. (At least that's what the code appears to do.) Wouldn't it be a problem if the pivot value itself could occur in both segments?

Vaughn Cato Nov 5 at 2:07

According to Wikipedia: "Partition the range: reorder its elements, while determining a point of division, so that all elements with values less than the pivot come before the division, while all elements with values greater than the pivot come after it; elements that are equal to the pivot can go either way"

Vlad Bud · Accepted Answer · 2019-10-26 13:26:29Z

0

The goal of partition algorithm is to simply take some collection of elements (for example, you work with “arrays”) and then partitioning (or splitting!) this collection around the pivot into two parts — left part and right part.

There should be some "rule" regarding the elements on the left of pivot and on the right of the pivot. For example, all elements on the left will be smaller than the chosen pivot and all the elements on the right will be greater than the pivot.

You may also see the Implementation in the following video: https://www.youtube.com/watch?v=MLpH7mpwOxQ

Hope that helps!

answered Oct 26, 2019 at 13:26

Vlad Bud

11 bronze badge

Collectives™ on Stack Overflow

Is this partition algorithm correct?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related