Difference of the two versions of partition used in quicksort

Question

The first one is straightforward, just walk from both sides until finding a reversion.

/*C++ version, [first, last), last needs --first to fetch the last element*/
/*returns the middle of partitioning result*/
int* partition( int *first, int *last, int pivot ) {
    while (true) {
        while (*first < pivot) ++first;
        --last;//Don't edit this, it's true.
        while (pivot < *last) --last;
        if (!(first < last)) return first;
        swap(*first, *last);
        ++first;
    }
}

The second one (shown in "Introduction to algorithms") is:

int* partition( int a[], int n, int pivot ) {
    bound = 0;
    for ( i = 1; i != n; ++i )
        if ( a[i] < pivot )
            swap( &a[i], &a[++bound]);
    swap(a, a + bound);
    return a + bound;
}

The invariant of the second one is " All elements before bound is less than pivot " .

Q: And what is the advantages and disadvantages of the two versions?

I'll give one first, the second one require ++ operation on the iterator( pointer ), so it can be applied to some ForwardIterator like the iterator of a linked list. Other tips?

Answer 1

As far as the basic idea of the two algorithms go, both are correct. They will do the same number of comparisons but the second one will do more swaps than the first.

You can see this by stepping through the algorithms as they partition the array 1 9 2 8 3 7 4 6 5 using 5 as the pivot. When the first algorithm swaps two numbers it never touches either of then again. The second algorithm first swaps 9 and 2, then 9 and 3, and so on, taking multiple swaps to move 9 to its final position.

There are other differences too. If I haven't made any mistakes, this is how the first algorithm partitions the array:

1 9 2 8 3 7 4 6 5
f                 l
1 9 2 8 3 7 4 6 5  # swap 9,5
  f             l
1 5 2 8 3 7 4 6 9  # swap 8,4
      f     l
1 5 2 4 3 7 8 6 9  # return f = 5
        l f

This is how the second algorithm partitions the array:

1 9 2 8 3 7 4 6 5  # 1<5, swap 1,1
bi      
1 9 2 8 3 7 4 6 5  # 9>5, no swap
  bi
1 9 2 8 3 7 4 6 5  # 2<5, swap 9,2
  b i
1 2 9 8 3 7 4 6 5  # 8>5, no swap
    b i
1 2 9 8 3 7 4 6 5  # 3<5, swap 9,3
    b   i
1 2 3 8 9 7 4 6 5  # 7>5, no swap
      b   i
1 2 3 8 9 7 4 6 5  # 4<5, swap 8,4
      b     i
1 2 3 4 9 7 8 6 5  # 6>5, no swap
        b     i
1 2 3 4 9 7 8 6 5  # 5=5, exit loop, swap 9,5
        b       i
1 2 3 4 5 7 8 6 9  # return b = 4
        b       i

Notice how it makes 5 swaps, compared to just 2 of the other algorithm. It also moves the last item in the array to the middle array. In this case the last item happens to be the pivot so it's the pivot that's moved to the middle, but that's not the general case.