Alternative partition method

 

See also

http://analgorithmaday.blogspot.com/2011/02/partitioning-algorithmin-place.html

Introduction

  Quick sort partition algorithm is sometimes taught differently. :) So, thought of covering that too. There is no difference in performance or space usage. Only advantage is, this method is little bit straight forward.

Concept

  Instead of taking the pivot and incrementing 2 counts: i and j both starting from the left, we can maintain left & right with left starting from the start and right starting from the end.

  As we know that, left needs to have lesser items and right needs to have greater items. until we have appropriate items, we can simply skip it. This is little bit clearer since the skip we do is not so clear in old partition approach.

  After we skip perfectly “ok” left and right, what we have will be swappable items. We continue this until we meet the condition left > right.

  After we do all the swaps and ready with left & right lists smaller & greater. We can simply swap the element in the location where right is.

Code

int qpartition( int *a, int low, int high )

{

    int left, right;

    int pivot_item;

    pivot_item = a[low];

    left = low;

    right = high;

    while ( left < right ) {

        /* Move left while item < pivot */

        while( a[left] <= pivot_item ) left++;

        /* Move right while item > pivot */

        while( a[right] > pivot_item ) right--;

        if ( left < right ) swap(a[left],a[right]);

    }

    /* right is final position for the pivot */

    a[low] = a[right];

    a[right] = pivot_item;

    return right;

}

void main()

{

    int A[] = {9,5,7,1,10,2,3};

    int loc = qpartition(A, 0,6);

}

• I felt this approach, little bit confusing.. :) If you are not used to lots of counters.. be with the old approach
• The above code taken from: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort1a.html
• Even though a[low] is the pivot, we include that as well in the comparison. This is also another difference in this algorithm.