9.6.2 Algorithm for Partitioning

int partition (int i; int j; key-type pivot);

        /* partitions the elements a[k] ... a[j],

        wrt the pivot and returns the position k  */

    {

        int$\ell$, r;

        {

$\ell$ = i; /*$\ell$ starts from left end */

            r = j; /*r starts from right end */

            do

                swap the records a[$\ell$] and a[r];

                while (a[$\ell$] . key < pivot)

$\ell$ = $\ell$ + 1;

                while (a[r] . key $\geq$ pivot)

                    r = r - 1;

                while($\ell$$\leq$r);

                    return ($\ell$);

            }

    }

• For an example, see Figure 9.3.
• Worst case arises when the input is already sorted: O(n²)
• Average case : O(nlog n)

Figure 9.3: Quicksort applied to a list of 10 elements