11.2 Problem Solving: a General Sorting Program

We have introduced the concept of sorting and sort procedures in earlier chapters. The utility of a sort procedure is greatly enhanced if it can be used with a wide variety of arguments. In this section we develop a sort that will work for arrays of the same unconstrained type but differing bounds; in Section 11.4 we will exploit the full generality of Ada's generics to create a sort that will work with any unconstrained array type at all, regardless of its index type or element type.

Case Study: Software Support "Hot Line"

You are employed in the customer-support department of a software company. the toll-free telephone system is open seven days a week, and your supervisor is interested in knowing how many calls arrive each day and also in seeing the data presented in order of increasing number of calls. That is, the day with the fewest calls will appear first and the day with the most calls will appear last. Your supervisor might also wish to see the data for weekdays or weekend days only.

ANALYSIS

Since you are experienced in data handling, you realize that this is basically a sorting problem, and so you develop a sort program that will work with arrays of call records. The program should handle correctly arrays of one through seven elements, so that, for example, just the weekdays or just the weekend days can be sorted.

Data Requirements

Probem Inputs

a set of up to seven pairs of data, each giving a day of the week (type Days) and a number of calls (type Natural)

Problem Outputs

a display of the data pairs, sorted in order of increasing number of calls

DESIGN

Here is a good application of unconstrained array types. Let us define the types

    TYPE Days IS (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
    SUBTYPE DayRange IS Natural RANGE 0..6;
    TYPE CallRecord IS RECORD
      DayOfWeek    : Days;
      NumberOfCalls: Natural;
    TYPE Callers IS ARRAY(DayRange RANGE <>) OF CallRecord;

and write a procedure Exchange capable of exchanging two elements of type Natural. The procedure SelectSort will implement a very simple sorting algorithm called exchange sort.

Algorithm

We have already developed a simple sorting algorithm and procedure SelectSort in Section 8.10. We can just adapt the sort procedure to the current record strucure; the algorithm is unchanged.

IMPLEMENTATION

Program 11.2 gives the modified sort procedure SelectSort, together with auxiliary procedures Exchange and DisplayCallers. The main program declares three arrays of type Callers with differing bounds and illustrates the sort procedure operating on the three arrays in turn. Note how the attributes are used in SelectSort to make the procedure independent of the bounds of the parameter.

Program 11.2
Sorting Unconstrained Arrays

WITH Ada.Text_IO;
WITH Ada.Integer_Text_IO;
PROCEDURE Phone_Service IS
------------------------------------------------------------------------
--| Shows sorting of unconstrained arrays and slices
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: September 1995                                     
------------------------------------------------------------------------

  SUBTYPE DayRange IS Natural  RANGE 0..6;
  SUBTYPE Weekdays IS DayRange RANGE 0..4;
  SUBTYPE Weekend  IS DayRange RANGE 5..6;

  TYPE Days IS (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
  TYPE CallRecord IS RECORD
    DayOfWeek    : Days;
    NumberOfCalls: Natural;
  END RECORD;
    
  TYPE Callers IS ARRAY(DayRange RANGE <>) of CallRecord;

  PACKAGE Days_IO IS NEW Ada.Text_IO.Enumeration_IO(Enum => Days);

  ThisWeek:       Callers(DayRange);
  WeekdayCallers: Callers(Weekdays);
  WeekendCallers: Callers(Weekend);

  PROCEDURE DisplayCallers (List: Callers) IS
  -- Pre:  List is defined
  -- Post: display all elements in the vector

  BEGIN -- DisplayCallers
    FOR Count IN List'Range LOOP
      Days_IO.Put  (Item=>List(Count).DayOfWeek, Width=>3);
      Ada.Integer_Text_IO.Put
        (Item=>List(Count).NumberOfCalls, Width=>4);
      Ada.Text_IO.New_Line;
    END LOOP;
    Ada.Text_IO.New_Line;
  END DisplayCallers;


  PROCEDURE Exchange(Value1, Value2: IN OUT CallRecord) IS
  -- Pre:  Value1 and Value2 are defined
  -- Post: Value1 and Value2 are interchanged

    TempValue: CallRecord;

  BEGIN -- Exchange
    TempValue := Value1;
    Value1    := Value2;
    Value2    := TempValue;
  END Exchange;


  PROCEDURE SelectSort(List: IN OUT Callers) IS
  -- Pre:  List is defined
  -- Post: elements of List are arranged in ascending order

    IndexOfMax: DayRange;

  BEGIN

    FOR PositionToFill IN List'First..List'Last - 1 LOOP

      IndexOfMax := PositionToFill;

      FOR ItemToCompare IN PositionToFill + 1..List'Last LOOP
        IF List(ItemToCompare).NumberOfCalls 
         < List(PositionToFill).NumberOfCalls THEN
          IndexOfMax := ItemToCompare;
        END IF;
      END LOOP;
      -- assert: element at List(PositionToFill) 
      --         is smallest in subarray

      IF IndexOfMax /= PositionToFill THEN
        Exchange(List(PositionToFill),List(IndexOfMax));
      END IF;

    END LOOP;

  END SelectSort;


BEGIN -- Phone_Service

  ThisWeek := ((Mon, 12), (Tue, 23), (Wed, 100), (Thu, 40), 
               (Fri, 52), (Sat, 17), (Sun,   2));
  WeekdayCallers := ThisWeek(Weekdays);
  WeekendCallers := ThisWeek(Weekend);

  Ada.Text_IO.Put(Item=> "Testing SelectSort for telephone callers");
  Ada.Text_IO.New_Line;
  Ada.Text_IO.Put(Item=> "Here is ThisWeek before sorting.");
  Ada.Text_IO.New_Line;
  DisplayCallers(List => ThisWeek);
  Ada.Text_IO.New_Line;
  
  SelectSort(List => ThisWeek);
  Ada.Text_IO.Put(Item=> "Here is ThisWeek after upward sorting.");
  Ada.Text_IO.New_Line;
  DisplayCallers(List => ThisWeek);
  Ada.Text_IO.New_Line;

  Ada.Text_IO.Put
    (Item=> "Here is WeekdayCallers before sorting.");
  Ada.Text_IO.New_Line;
  DisplayCallers(List => WeekdayCallers);
  Ada.Text_IO.New_Line;
  
  SelectSort(List => WeekdayCallers);
  Ada.Text_IO.Put
    (Item=> "Here is WeekdayCallers after upward sorting.");
  Ada.Text_IO.New_Line;
  DisplayCallers(List => WeekdayCallers);
  Ada.Text_IO.New_Line;

  Ada.Text_IO.Put
    (Item=> "Here is the WeekendCallers before sorting.");
  Ada.Text_IO.New_Line;
  DisplayCallers(List => WeekendCallers);
  Ada.Text_IO.New_Line;
  
  SelectSort(List => WeekendCallers);
  Ada.Text_IO.Put
    (Item=> "Here is WeekendCallers after upward sorting.");
  Ada.Text_IO.New_Line;
  DisplayCallers(List => WeekendCallers);
  Ada.Text_IO.New_Line;

END Phone_Service;

Sample Run

Testing SelectSort for telephone callers
Here is ThisWeek before sorting.
MON  12
TUE  23
WED 100
THU  40
FRI  52
SAT  17
SUN   2


Here is ThisWeek after upward sorting.
SUN   2
MON  12
TUE  23
SAT  17
THU  40
FRI  52
WED 100


Here is WeekdayCallers before sorting.
MON  12
TUE  23
WED 100
THU  40
FRI  52


Here is WeekdayCallers after upward sorting.
MON  12
TUE  23
FRI  52
THU  40
WED 100


Here is the WeekendCallers before sorting.
SAT  17
SUN   2


Here is WeekendCallers after upward sorting.
SUN   2
SAT  17

Unconstrained arrays and slicing make it easier to write programs that deal with partially filled arrays. Look again at Program 8.16, in which an array of scores is sorted. If the score array type were defined as an unconstrained type similar to Callers, and the variable Scores were declared as an array object similar to V1, then the procedure SelectSort would need only a single parameter--namely, the name of the actual array to be sorted. Once Scores was partially filled, the slice Scores(1..ClassSize) could be passed as the single actual parameter. You can make this change as an exercise.

Exercises for Section 11.2

Programming

Modify Program 8.16 so that ScoreArray is defined as an unconstrained array type and SelectSort requires only a single parameter.