There are two kinds of sorting:

1.    Internal sorting.  In this method, the elements are interchanged within the array to obtain the required order.
2.    External sorting.  Here the elements are arranged in order in another array.  The original array is unchanged.

It is a time/space trade-off.  Internal sorting usually requires more time, but less space, while external sorting needs more space but is usually faster.  Click below for sorting routines:

For animation click here:     Animation
 Top of Page
MAX SORT  The list of elements is repeatedly compared to locate the largest element.  In internal sorting, this element is interchanged with the last element  In external sorting, this element is placed as the last element of the second array.  This routine is conducted repeatedly with one element less for each pass until the elements are sorted.  Below is the algorithm to achieve this task.

/* Find the largest number in the list of numbers (assume that all numbers are integers).  Same algorithm can be used if all
 numbers are real.
Function to find the largest in a list
 The list consists of n elements from 0 to n – 1
Assume that the first element E[0] is the largest.  Then compare with all elements until the last E[n – 1], for the first pass.  Then switch Max with the last element E[n – 1]. In the second pass compare only up to e[n – 2] since last element is the largest. Switch with the second last element E[n – 2].   Continue with one less element in each subsequent pass and switch with the element earlier. */

Input  E[], n
Output ordered E[]

int  E[], n, Max
for ( int last = n - 1; last >= 1; last--)
 findMax(E[], last);
//  Call function findMax to locate largest
 Exchange(E[], Max);
// Call function Exchange to switch largest element with last
// End for loop and main
// Function findMax locates largest element
int findMax(E, last)
 Max = E[0];  //  assume first element is largest
  for (int index = 1; index <= last; index++)
   if (max < E[index])
    max = E[index];
  return max;  // End function

// Function Exchange switches Max with the last number, puts Max
// in temp, puts last element in Max, puts temp in last element
int Exchange(E, Max)
 temp = Max;
 Max = E[last];
 E[last] = temp;

How many comparisons are required for the best case, the worst case and for the average case?   In the first pass, Max must compare with elements from 1 to n – 1.  In the second pass, Max must compare with elements from 1 to n – 2, In the third pass to n – 3, and so on .
 So the total number of comparisons will be 1 + 2 + 3 + ….. + n – 1
 This equals (n – 1) * (n – 1 + 1)
                               2
which equals n(n – 1)/2.  Since we must compare irrespective of the manner in which the elements are arranged, this would be the true for the worst as well as the best and the average case.
 Top of Page
BUBBLE SORT  It sorts by making several passes through the array, comparing pairs of keys in adjacent locations and interchanging their elements if they are out of order.  That is, the first and second elements are compared and interchanged if the first is larger than the second; then the (new) second and the third elements are compared and interchanged if necessary, and so on.  The largest element will sink to the bottom, while the smallest (lightest) will bubble to the top.  On subsequent passes, the largest element will be ignored.  If on any pass, no entries are interchanged, the array is completely sorted and the algorithm will halt.  The algorithm is shown below.

input    E, an array of elements, and n >= 0, the number of elements
Output    E with elements in ascending order of the elements

    void bubbleSort(Element[] E, int n)
        int numpairs;    // the number of pairs to be compared
        boolean didswitch;     // true if an interchange is done
        int j;

        numpairs = n - 1;
        didswitch = true;
        while (didswitch)
            didswitch = false;
            for (j = 0; j < numpairs; j++)
                if (E[j] > E[j + 1])
                    Interchange E[j] and E[j + 1].
                    didswitch = true;
                // continue for loop.
            numpairs--;
        return;
How many comparisons are required?  For the first pass, we need n - 1 comparisons.  In the best case, (if the elements are already in order) that is all that is required as no interchanges will take place and the algorithm is complete.  In the worst case, (when the elements are in exactly the opposite order) we will require n - 2 comparisons in the second pass, n - 3 in the third pass and so on (1 comparison for the last pass) for a total of 1 + 2 + 3 + ... (n - 1).  This equals n(n - 1)/2 comparisons.  But that figure can be reduced by using a variation of divide and conquer.  The number of comparisons is then lg(n!).  So if we have 4 elements, by the normal method, we need 4(3)/2 = 6 comparisons.  By the improved method w will need lg(4!) = lg(24) = 5 comparisons.  Similarly for 5 elements we can reduce from 5(4)/2 = 10 to lg(5!) = lg(120) = 7 comparisons.  For the average case we need [(n - 1) + n(n - 1)/2]/2 comparisons.  This computes to (n - 1)(n + 2)/4 comparisons.  But in most cases, the average is larger than that and tends towards the worst case.
 Top of Page
Insertion Sort works the way a hand of cards is sorted.  We start with an empty hand, with cards face down on the table.  We pick a card at a time, compare it to the cards already in the hand and insert it in the correct position.  This algorithm was first proposed by Donald Knuth                                Donald Knuth

Algorithm and Analysis:

Subroutine shiftVac(E, vacant, x) shifts elements until the vacancy is at the correct position in which to place x among the sorted elements.

int shiftVacRec(Element[] E, int vacant, Key x)
    int xLoc;
1.    if (vacant == 0)
2.        xLoc = vacant;        // alrady sorted
3.    else if (E[vacant-1].key <= x)
4.        xLoc = vacant;        // in order
5.    else
6.        E[vacant] = E[vacant - 1];
7.        xLoc = shiftVacRec(E, vacant - 1, x);
8.    return xLoc;

Worst-Case Complexity:

This happens when the keys are in recerse (i.e. decreasing) order.  It then equals n(n - 1)/2 or in the order of n².

Average Behavior:

It is approximately n²/4 also in the order n².

Space:

It is in-place with the iterative version of shiftVac.

For more information, click below

Conquer:    The two subarrays are sorted by recursive calls to quicksort.

Combine:    Since the subarays are sorted in place, no work is needed to combine them:  the entire array is now sorted.

Worst Case:

Partition compares each key to pivot, so if there are k positions in the range of the array, it does k - 1 comparisons since the first position is vacant.  If the pivot  is the smallest key each time Partition is called, then the totaoal number of comparisons is n(n - 1)/2 which is just as bad as Insertion sort. The worst case occurs when the keys are already in ascending order.

For more information, click below:

For comparing six sorting routines, click below

 Top of page

 Return to Syllabus