[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]

                           Turbo Pascal for DOS Tutorial
                                by Glenn Grotzinger
                       Part 15: Concepts of Sorting Arrays
                    copyright (c) 1995-96 by Glenn Grotzinger

    Here is a solution from last time...keep in mind to be as efficient as
    possible in coding...I figure that many will try simply writing those frames
    out.

    program part14; uses crt;

      var
        esccount: byte;
        chr: char;

      procedure setitup;
        begin
          { green border of 4 units }
          textbackground(green);
          clrscr;
          window(5,5, 76, 21);

          { red border of one unit }
          textbackground(red);
          clrscr;
          window(6,6,75,20);

          { set up black background }
          textbackground(black);
          clrscr;

          { write keypress statement }
          highvideo;
          textcolor(lightcyan);
          writeln('Keypress Detector (Press ESC 5 times to quit)');

          { preserve Keypress detector title. }
          window(6,7,75,20);
        end;

      function status(char1: char;var esccount: byte): string;
        var
          char2: char;
        begin
          if char1 = #0 then
            begin
              char2 := readkey;
              case char2 of
                #59: status := 'F1';
                #60: status := 'F2';
                #61: status := 'F3';
                #62: status := 'F4';
                #63: status := 'F5';
                #64: status := 'F6';
                #65: status := 'F7';
                #66: status := 'F8';
                #67: status := 'F9';
                #68: status := 'F10';
                #82: status := 'Insert';
                #71: status := 'Home';
                #73: status := 'PageUp';
                #81: status := 'PageDown';
                #83: status := 'Delete';
                #79: status := 'End';
                #77: status := 'Right';
                #72: status := 'Up';
                #80: status := 'Down';
                #75: status := 'Left';
              end;
            end
          else
            case char1 of
              #8: status := 'Backspace';
              #9: status := 'TAB';
              #13: status := 'ENTER';
              #27: begin
                     status := 'ESC';
                     inc(esccount, 1);
                     { the 1 is not required here, but the inc and dec
                       functions can be used with values greater than
                       one like this in this case }
                   end;
              #32: status := 'SPACE';
            else
              status := char1;
            end;
        end;

      procedure endit;
        var
          i: byte;
        begin
          window(1,1,80,25);
          gotoxy(1,1);
          for i := 1 to 25 do
            begin
              delline;
              delay(100);
            end;
        end;

      begin
        esccount := 0;
        setitup;

        while esccount <> 5 do
          begin
            chr := readkey;
            normvideo;
            textcolor(lightblue);
            write('You pressed the ');
            highvideo;
            textcolor(green);
            write(status(chr, esccount));
            normvideo;
            textcolor(lightblue);
            writeln(' key.');
          end;

        endit;
      end.
    Now, we will discuss the use of sorting with regards to arrays into a
    particular order.  Sometimes we may need numbers, such as dates in
    chronological order, or a list of names in alphabetical order.

    Swapping Units
    ==============
    The integral part of a sorting routine is a unit swap.  As a rule, we
    MUST have a temporary variable, because a simple assign set will not work.

    For example, to swap the contents in variables a and b, we need a temporary
    variable we will call temp.  Then code such as what is below will do...

    temp := b;
    b := a;
    a := temp;

    The swap should ideally be performed with the smallest units possible,
    based on the sorting key.  The idea of a sorting key will be explained
    later.  You may end up using pointers to get it to move the smallest
    amount of data, which will be explained in a future part.  The less
    amount of data the computer can move, the better.

    The BubbleSort (or the brute force sort)
    ========================================
    Basically, in this sorting method, each and every item in the array is
    compared each and every other item in the array.  This is a largely
    inefficient method for sorting items, but easy to code, and useful for
    small amounts of data.

    program example_of_bubblesort;

      var
        thearray: array[1..20] of integer;
        temp: integer;
        i, j: integer;

      begin
        randomize;
        { generate numbers for array and write them as unsorted }
        write('The unsorted array: ');
        for i := 1 to 20 do
          begin
            thearray[i] := random(50) + 1;
            write(thearray[i], ' ');
          end;
        writeln;

        { the bubblesort. }
        for i := 1 to 20 do
          for j := i+1 to 20 do
            if thearray[i] > thearray[j] then { compare and swap }
              begin
                temp := thearray[i];
                thearray[i] := thearray[j];
                thearray[j] := temp;
              end;

        write('The sorted array: ');
        for i := 1 to 20 do
          write(thearray[i], ' ');
        writeln;

    end.
    As it is a purely iterative solution, you should have no exact trouble
    seeing what is going on.  But to further another point as to exactly
    how it works, and why it is so inefficient, we will sort a sample set
    of numbers manually according to this algorithm to see what is going on.

    1       3       2       5       4

    We will start out with the following short description of what is going
    on within the two for loops for 5 values of data:

    1) i = 1; j = 2; Position1 = 1; Position2 = 3; 1 > 3 = false;
    2) i = 1; j = 3; Position1 = 1; Position3 = 2; 1 > 2 = false;
    3) i = 1; j = 4; Position1 = 1; Position4 = 5; 1 > 5 = false;
    4) i = 1; j = 5; Position1 = 1; Position5 = 4; 1 > 4 = false;

    5) i = 2; j = 3; Position2 = 3; Position3 = 2; 3 > 2 = true; we swap the
    two values...so our resultant array is...

    1       2       3       5       4

    6) i = 2; j = 4; Position2 = 2; Position4 = 5; 2 > 5 = false;
    7) i = 2; j = 5; Position2 = 2; Position5 = 4; 2 > 4 = false;

    8) i = 3; j = 4; Position3 = 3; Position4 = 5; 3 > 5 = false;
    9) i = 3; j = 5; Position3 = 3; Position5 = 4; 3 > 4 = false;

    10) i = 4; j = 5; Position4 = 5; Position5 = 4; 5 > 4 = true; we swap
    the two values...so the resultant array is...

    1       2       3       4       5

    11) Effective termination of loop;

    As we can see, we took 10 steps in the algorithm to swap 2 elements of
    the array in order to sort it.  Basically, this is a very inefficient
    algorithm in comparison to other types that are available, as we are
    considering portions of the array that are already sorted.  As a note,
    to sort the items in descending order instead of ascending order, change
    the comparison between the two positions i and j of the array from > to <.

    QuickSort
    =========
    This is a much faster recursive solution for sorting than the bubblesort.
    It makes use of a pivot marker, which moves according to what exactly is
    contained in the array.  It also will make use of a "divide and conquer"
    approach.  Here is a short example...

    program example_of_quicksort;

      var
        thearray: array[1..20] of integer;
        i, j, PIVOT, t: integer;

      procedure quicksort(L, R: integer);
        begin
          if L < R then
            begin
              i := L + 1;
              j := R;
              PIVOT := thearray[L];

              repeat
                while thearray[i] <= PIVOT do inc(i);
                while thearray[j] > PIVOT do dec(j);
                if i < j then
                  begin
                    t := thearray[i];
                    thearray[i] := thearray[j];
                    thearray[j] := t;
                  end;
              until i > j;

              thearray[L] := thearray[j];
              thearray[j] := PIVOT;

              quicksort(L, j-1);
              quicksort(i, R);
            end;
        end;

      begin
        randomize;
        write('The unsorted array is: ');
        for i := 1 to 20 do
          begin
            thearray[i] := random(50) + 1;
            write(thearray[i], ' ');
          end;

        quicksort(1, 20);

        write('The sorted array is: ');
        for i := 1 to 20 do
          write(thearray[i], ' ');
      end.

    This is a recursive solution, so it will be a little different.  Let's
    start with the same number sequence we had above and see how quicksort
    works...keep in mind that quicksort is about as inefficient as bubble-
    sort with smaller sets...Once you get into larger sets, quicksort beats
    bubblesort hands down -- it more intelligently seeks the proper array
    units to swap.

    1       3       2       5       4

    1) 1 < 5 = true so continue.... i = 2; j = 5; PIVOT = 4;
       3 <= 4 = true so i = 3; 2 <= 4 = true so i = 4;
       5 <= 4 = false so quit;

       4 > 5 so quit;
       4 < 5 = true, so swap values.  The resulting swap is...

    1       3       2       4       5

       4 > 5 = false so continue on repeat loop...

       i = 4; j = 5; PIVOT = 4; 4 <= 4 = true so i = 5;
       5 <= 4 = false so quit;

       5 > 4 = true so j = 4; 4 > 4 = false so quit;

       5 > 4 = true so quit repeat loop.

       j = 4; i = 5; 4 is left side. 4th element is 4.

    2) Quicksort called for left side of 1, and right side of 3.  Then quicksort
    for left side of 5, and right side of 5. Essentially, we keep cutting the
    array in half based by where the pivot lands.  We will process the quicksort
    for the left side as 2a) and the quicksort for the right side as 2b).

    2a) Our number set for this instance of quicksort is:

    1       3       2

        1 < 3 = true so continue.

        i = 2; j = 3; PIVOT = 2; 3 <= 2 = false so quit;
        i = 2; j = 3; PIVOT = 2; 2 > 2 = false so quit;

        2 < 3 = true so swap values...the resulting swap is...

    1       2       3

        2 > 3 = false so quit repeat loop.

        Quicksort called twice for left side of 1, 2 and 2,3.  The results of
        both of these sorts end up being false, so they will terminate
        readily.

    2b) 5 < 5 = false so terminate quicksort.

    As we can see, the algorithm sets itself up so it ignores portions of the
    array that are already sorted.  For larger arrays, it will provide a great
    performance boost as we are ignoring the parts of the array that happen
    to be sorted by using this particular algorithm.

    The version of quicksort pictured sorts in ascending order.  To make it
    sort in descending order, change the two while loops to read the following:

    while thearray[i] <= PIVOT do inc(i);
    while thearray[j] > PIVOT do dec(j);

    ShellSort
    =========
    This is a non-recursive sort that performs close in performance to quicksort.
    We can follow what is going on, so I will just simply write an example of
    the use of the shellsort, and describe how to change it to sort in descending
    order instead of ascending order...

    program example_of_shellsort;

      var
        thearray: array[1..20] of integer;
        i: integer;

      procedure shellsort(n: integer);
        const
          m = 3;   { total number of sort passes }
        var
          i: array[1..m] of integer;
          j, k, p, s, t, incr: integer;
        begin
          i[m] := 1;
          for j := m - 1 downto 1 do i[j] := 2 * i[j];
          for j := 1 to m do
            begin
              incr := i[j];
              for k := 1 to incr do
                begin
                  s := incr + k;
                  while s <= n do
                    begin
                      p := s;
                      t := thearray[p];
                      thearray[k-incr] := t;
                      while t < thearray[p-incr] do
                        begin
                          thearray[p] := thearray[p-incr];
                          dec(p, incr);
                        end;
                      thearray[p] := t;
                      inc(s, incr);
                    end;
                end;
            end;
        end;

      begin
        randomize;
        write('The unsorted array is: ');
        for i := 1 to 20 do
          begin
            thearray[i] := random(50) + 1;
            write(thearray[i], ' ');
          end;
        writeln;

        shellsort(20);  { 20 is high end of array }

        write('The sorted array is: ');
        for i := 1 to 20 do
          write(thearray[i], ' ');
        writeln;
      end.
    To get it to sort in ascending order instead of descending order, change the
    line:

    while t < a[p-inc] do

    to

    while t > a[p-inc] do

    Practice
    ========
    You should practice using these sorting methods.  They stay basically as
    indicated for any use, except for changing the identities of the item
    type in the array we sort.  For strings, we can alphabetize them by using
    the strings in the sorting routine for ascending order.  Look at the ASCII
    chart...It sees characters as numbers... a < b < c ...et al...  With
    strings, be sure to sort them case insensitively, especially, if we
    alphabetize a list or something like that....

    Next Time
    =========
    We will cover methods of searching an array for data.  send comments to
    ggrotz@2sprint.net

[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]