Quick

  1. Psuedo code main sort;

    QuickSort(int sorta[], first, last)

    int pivotIx, Split();

    // when first >= last, we're through -- we've sorted the smallest possible sized bin
    if (first < last) {
    // This is the real work, and it returns the location for the pivot point
    pivotIx = Split(sorta, first, last);

    // Now the recursive calls
    QuickSort(sorta, first, pivotIx-1);
    QuickSort(sorta, pivotIx+1, last);
    } // if first < last -- all done!

  2. Psuedo code split;

    // must have type integer since returns pivotIx
    int Split(int sorta[], first, last)

    int topIx, botIx; // indecies
    int pivotVal, temp; // items

    pivotVal = sorta[first]; // this is just chosen arbitrarily
    botIx = first+1, topIx = last; // start looking at the ends
    while (topIx > botIx) {
    // look for a missorted small number
    while (sorta[topIx] > pivotVal) {
    topIx--;
    }
    // now look for cross point OR missorted large number
    while ((topIx > botIx) AND (sorta[botIx] < pivotVal)) {
    botIx++
    }
    // if you now have two missorted numbers, switch them
    if (botIx < topIx) {
    temp = sorta[topIx];
    sorta[topIx] = sorta[botIx];
    sorta[botIx] = temp;
    }
    } // while topIx > botIx

    // now put the pivot in its correct location by swapping it with whatever is
    // under topIx (which will be <= the pivotVal, as top is now lower than bot
    temp = sorta[topIx];
    sorta[topIx] = pivotVal;
    sorta[first] = temp;
    return(topIx);