Is this partition algorithm correct?

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.

---

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.

链接地址: http://www.djcxy.com/p/61820.html

上一篇: 图像上的透明度渐变

下一篇: 这个分区算法是否正确？