Author: honzik
Last saved by: Jan Maxmilián Honzík
Company: VUT v Brně

Algorithms and Data Structures
Lesson Eleven

ALGORITHMS AND DATA STRUCTURES
 Lesson eleven

Lecture: Sorting - Ordering I.

11 ORDERING

11.1 Definitions

"Sorting" is distributing the elements of the set to groups of elements according to a defined feature attribute. (Example:  Cars may be sorted to groups according to colors, fruits can be sorted according to kinds). 

"Ordering" is a linear arrangement of the elements of a set, according to the relation based on the value of the key. The key is the necessary part of every element. Ordering is ascending (non-decreasing): ( El[i] <= El[i+1]) or descending (non-increasing) : (El[i] >= El[i+1]).

"Merging" is creating  one resulting ordered file from two or more ordered source ordered files. The type of source and resulting ordering is the same.

The term "sorting" is widely used instead of  "ordering". We will use the term "sorting" with the meaning of the "ordering".

"Sequential sorting" is sorting process which processes the elements in the order, in which they are located in the source sequence.

"Stability" of the ordering is the feature of sorting process, which keeps the relative order of the keys with the same value. 

Example: source sequence has three keys "5":  

6  3  2  5'  1  5''  4   7  5'''

stable ordering will results in: 

1	2  3  4  5'  5''  5'''  6  7
2	
while the non-stable ordering doesn't keep the order of keys "5".).

"Naturalism" of the sorting is a feature, which expresses that the time necessary for sorting of randomly arranged sequence is greater than time necessary for sorting of the ordered sequence and that time is less than time necessary for ordering of the sequence ordered in inverse order.

Note:
Swapping notation: To make the code more understandable, the operator of swapping ":=:" will be used. To exchange the values of the two variables a,b, the statement a:=:b will be used instead of the sequence:

Temp:=a; 
a:=b; 
B:=Temp;

The swap operation is illegal in Pascal!!!

11.2 Ordering with the multiple keys

Let is the set of records representing the persons of the type:
const
  Size:1000;
type
  TMonth:(January,February,March,April,May,June,July,August,September,
         October,November,December);
  TPerson=record
             Name: string;
             Year:1800..2100;
             Month:TMonth;
             Day:1..31
          end;
  TArr=array[1..Size]of TPerson;

The task is to create two lists:

a) List ordered according to the age of each person (the oldest person is the first). 

b) List according to the date of birthday in the current year. If two people have the birthday at the same date, the older precedes the younger.

The priority of the keys for the first list is: Year,Month,Day.
The priority of the keys for the second list is: Month,Day,Year.

There are two different approaches to solve the problem: using of the multiple key relation or using the multiple sorting run.

11.2 1 Multiple key relation

Multiple key relation "older" is Boolean function, which compares the data of the two persons and returns the "true", if the first person is older and "false" if the first person is younger or of the same age!

function Older(P1,P2:TPerson):Boolean;
(* Function "Older" serves as function "Less" in the process of sorting 
the array of person to create the list of persons ordered according the 
age *)
begin
  if P1.Year<>P2.Year
  then Older:=P1.Year<P2.Year (* Different years resolve the relation *) 
  else (* The same value of years *)
    if P1.Month<>P2.Month
    then Older:=P1.Month<P2.Month (* Different months resolve the relation *)
    else Older:=P1.Day<P2.Day  (* Same months -> days resolves the 
                                                             relation *)
end;

Home assignment: Create the similar function "LessForBirthday", for sorting of the array of person to  create the list of persons ordered according to their birthday.

11.2.2  Multiple sorting run

Let the array be:

var A:TArray;

If the array is ordered several times, every time according to a single key, starting with the Day, Month and ending with the Year, the resulting array will be ordered according to the age of the people. There are three procedures, each of them ordering the array according to a different key:

procedure SortDay(var A:TArray; Size:integer);
begin
  ...
end;
procedure SortMonth(var A:TArray; Size:integer);
begin
  ...
end;
procedure SortYear(var A:TArray; Size:integer);
begin
  ...
end;

The following sample of program will create the list of persons sorted  according to the age.

begin
 ...
  SortDay(A,Size);  (* sorting array according day *) 
  SortMonth(A,Size); (* sorting array according month *)
  SortYear(A,Size);  (* sorting array according year *)

end;

Sorting with multiple keys by successive sorting runs with increasing priority of keys should use STABLE sorting method. (Note: further explaining the sorting methods, the stability of every method will be mentioned). 

11.3. Ordering without the movement of items of sorted array

Most important operations of all sorting algorithms are "comparing of the keys of the two items" and "move of item (swapping of two items) of sorted array". Number of these operations determines the time complexity of the sorting method. If the moved item is too long, the moves of such items increase the time necessary for sorting. The ordering without movement of items solves the problem and reduces the sorting time.
 
The ordering without movement of (long) items uses auxiliary array (IndArr) with indexes.

Initial state of sorted array A and its column of indexes:

                                                       A
		                   Index       Data        Key            IndArr

1 | | Paul | 1
2 | | Adam | 2
3 | | Denis | 3
4 | | Martha | 4
5 | | Eva | 5

The sorting without movement of items moves only values of the IndArr column (which are short) and keeps the data and key of items at their place. The state of IndArr expresses the result of sorting by ordering the indexes according to the values of their items in the array A.

                                                        A
		                   Index       Data        Key            IndArr

1 | | Paul | 5
2 | | Adam | 1
3 | | Denis | 2
4 | | Martha | 4
5 | | Eva | 3

The pass through the ordered array and processing the items is done by the cycle: 

for i:=1 to Size do begin
  Process(A[IndArr[i]]).

Really sorted array B from the array A sorted without movement the cycle is created by:

  for i:=1 to Size do B[i]:=A[IndArr[i]];

To modify method normal sorting method (with the movement of items) two types of statement are to be changed:

     with movement                   without movement
     A[i]:=:A[j]                       IndArr[i]:=:IndArr[j]
     A[i].K<A[j].K                 A[IndArr[i]].K < A[IndArr[j]].K

While moves are done only in the IndArr, the comparison is done in the source array via index in the IndArr.

The array sorted by IndArr may be converted to ordered linked list by means of array of index-pointers PointArr.

Paul

Adam

Denis

Martha

Eva

0

3

5

1

4

5

1

2

4

3

1
2
3
4
5

Paul

Adam

Denis

Martha

Eva

2

Array ordered by index of order 

Array ordered by pointer index to linked list

Starting pointer

Key column

IndArr – column of index of order

PointArr – column of pointer index. 
 0 means nil

 The PointArr is created by the sequence of statements:

  First:= IndArr[1];  (* pointer to the first item of the list *)
  for i:=1 to Size-1 do PointArr[IndArr[i]]:=IndArr[i+1];
  PointArr[IndArr[N]]:=0; (* nil *)

McLarren's algorithm rearranges the items in the array A without the 
need of temporary array. The algorithm works "in situ". It is difficult 
to understand it at the first glance:

(* McLarren algorithm *)
i:=1;
Temp:=First;
while i<Size do begin
 (* looking for the successor moved to the position greater then i *)
  while Temp<i do Temp:=PointArr[Temp];
  A[i]:=:A[Temp];  (* exchange of the items *)
  PointArr[i]:=:Temp; (* exchange of pointers *)
  i:=i+1  (* the first i items are located at their place *)
end;

11.4 Classification of algorithms

a) According to the type of memory the sorted structure is located in the methods are divided to:
•	methods of internal sorting (sorting of arrays, sorting with random access)
•	methods of external sorting (sorting of files, sorting with sequential access)

b) According to the type of processor running the sorting process sorting algorithms are divided into:
•	serial algorithms - are processed on the processor allowing only one operation at a time.
•	parallel algorithms - are processed on the parallel processor  allowing execution of the multiple operation at the same time.

Note: This course doesn't expose the parallel algorithms.

c) According to the essential principle of the sorting the methods are classified to two complementary couples:

  Algorithms based on selection
  Algorithms based on insertion  (* selection is complementary to insertion *)

  Algorithms based on partition  
  Algorithms based on merging    (* partition is complementary to merging *)

Note: For the following examples we assume, that the type TArr is defined with const
  N=100; (* size of sorted array *)
type
  TArr=array[1..N] of integer;

  (* the only component of array item is integer key *)

11.5 Sorting methods based on selection

11.5.1 Straight selection-sort

Let the sorted array with N items be at a moment split into two parts: 1..k-1, k..N. The left part contains all elements which are less than any element of the right part. The sorting step is represented by searching for minimal item of right hand part and swapping it with the  first (k-th) item of the right hand part. It is done by the following sequence of statements: 

1                                   k-1     k                                                           N  

Sorted part

Unsorted part

    Min:=A[k];  (* initial setting  *)
    MinInd:=k;
    for i:=k+1 to N do begin
      if Min > A[i]    
(* for sorting with the multiple keys the comparison function 
  "less(Temp,A[i])" is used instead of "Temp<A[i]" *)

      then begin
        Min:=A[i];  (* storing the better minimum *)
        MinInd:=i;  (* storing the index of better minimum
      end;
    A[k]:=:A[MinInd];  (* swapping of floating first item of the right hand
                          part with the found  minimum *)

If we start the sorting with the empty right hand part and full left hand part of an array and repeat the above mentioned sequence N times, the array is sorted. The sorting procedure has the form:

 procedure SelectSort(var A:TArr);
 var
   Min,MinInd,i,j,k:integer;
 begin
   for j:=1 to N-1 do begin
     k:=j;
     Min:=A[k];
     MinInd:=k;
     for i:=k+1 to N do begin
       if A[i] < Min
(* for sorting with the multiple keys the comparison function 
  "less(Temp,A[i])" is used instead of "Temp<A[i]" *)

       then begin
         Min:=A[i];
         MinInd:=i;
       end; (* for i:= *)
     A[k]:=:A[MinInd];
   end; (* for j:= *)
 end; (* procedure *)

Notice the modification of the algorithm for the sorting with multiple keys.

Analysis:

a) The method is not stable. After the swapping k-th item with minimum it may happen, that the k-th item might be positioned behind the item with the same value, and that way is violated the relative ordering of the keys with the same value.

b) The time complexity of the method is quadratic:
•	average time complexity: TA(n) ≈ 4.5 * sqr(n)
•	maximal time complexity: TM(n) ≈ 6 * sqr(n)

c) Experimental values of time units for an array with n items ordered initially randomly (RAO) and ordered initially inversely (INV) are in the following table: (numbers in brackets expresse the size of array, the others the  time units). 

N | (128) | (256) | (512)
INV | 64 | 244 | 968
RAO | 50 | 212 | 744

The behaviour of the ordering method is "natural".

11.5.2 Bubble sort

Bubble sort is well known to programming amateurs and very popular. Its principle is the same, but the way how to find and swap the minimum is different and less efficient.

Bubble sort compares all pairs of neighbouring items and swaps the couple and checks if it is ordered inversely. If yes, it swaps items in the pair:

    if A[j-1]>A[j]
    then A[j-1]:=:A[j];

This is done for each item from left to right (or from right to left). After one pass, the maximal item (going from right to left) is moved by swapping to the leftmost position. This is the selectkion process combined with swapping process. If the pass of comparing is finished with no swapping, the sorting process is finished. 

The procedure of bubble sort has the form:

procedure BubbleSelectSort(var A:TArr);
(* Array A is array of 100 items *)
var
  i,j,N:integer;

  Fin:Boolean;  (* Boolean variable indicating the end of sorting *)
begin
   N:=100;
  i:=2;
  repeat
    Fin:=true;
    for j:=N downto i do begin
      if A[j-1]>A[j]
      then begin
        A[j-1]:=:A[j]; 
        Fin:=false;  (* swapping occurs, sorting not finished yet *)
      end (* if *)
    end; (* for j:=N *)
    i:=i+1;  (* first i items are sorted already *)
  until Fin or (i>N);
end; (* procedure *)

Note the modification of the algorithm for sorting with no movement of the items of sorted array. 

Analysis:

a) The Bubble-select-sort algorithm is stable!  It may be used for the sorting with multiple keys using the method of multiple sorting runs according to the keys with increasing priority.

b) The algorithm behaves naturally.

c) The time complexity is quadratic:
       maximal time complexity: TM(n) ~= 11.5 * sqr(n)

Experimental values of time units for an array with n items ordered  initially randomly (RAO) and ordered initially inversely (INV) can be seen in following table: (numbers in brackets expresses the size of array, other the  time units). 

N | (256) | (512)
INV | 338 | 1562
RAO | 558 | 2224

11.5.3 Heap sort

Heap sort is the most important sorting method based on the selection. "Heap" is a binary tree-like structure, here implemented by the array. For all nodes of the tree stands:

   "father-node" is greater than both "child-nodes".

If it is true, then maximal value of all nodes is located in the root position.  

Suppose the root is removed and its value is substituted by some other value.  The problem is to re-establish the rules of the heap. It is done by the procedure "SiftDown".

Procedure SiftDown compares sequentially all "father-nodes" with this node of the couple of "child-nodes", which is greater. If this child-node is greater than the father it both are swapped and the comparison is repeated downstairs until there is no need for swapping or the terminal node of the branch has been encountered. 

What is important is the implementation of the tree by an array. There is an implicit linking applied: if i is the index of "father-node", then left hand child-node has index=2*i and right hand child-node has index=2*i+1. This way an array with indexes:

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11

will represent the tree:

1

2

3

4

5

6

7

8

9

10

11

Representation of an array by the heap and vice-versa.
Values represent indexes of an array.

If N is the size of an array (and the number of nodes of the heap-tree too), then for the terminal node the condition   "(2*i) > N" is true.This is the way how to recognize the terminal node passing down along the branch.

The procedure SiftDown which re-established the heap-rules has the form:

procedure SiftDown(var A:TArr;Left,Right:integer); 
(* Left is the "father" index of sifted item; Right is the size of an 
   array *)
var
  i,j:integer;
  Cont:Boolean;  (* Cycle control variable "Continue" *)
  Temp:integer; (* Auxiliary variable of the same type like item *)
begin
  i:=Left;
  j:=2*i;  (* Index of the left child-node *)
  Temp:=A[i];
  Cont:=j<=Right;
  while Cont do begin
    if j<Right
    then (* Node i has both child-nodes *)
      if A[j]< A[j+1]
      then (* The right son is greater *)
        j:=j+1; (* set the j to the greater son of the pair *)

    if Temp >= A[j]
    then (* Element Temp has been sifted to its position; 
            cycle finishes *)
      Cont:=false
    else begin (* Temp is sifted to lower position and A[j] is emerging 
                  one level higher *)
      A[i]:=A[j];  (* emerging *)
      i:=j;        (* son becomes the next "father", 
                      preparation for the next pass *)
      j:=2*i;      (* next "left son" *)
      Cont:=j<=Right; (* condition : "j is not terminal node" *)
    end (* if *)
  end; (* while *)
  A[i]:=Temp; (* final positioning of the sifted root *)
end; (* procedure *)

To establish the heap from the randomly organized array, the SiftDown procedure is used. Starting with the lowest and the rightmost "father-node" the sub-heaps are established for all other "father-nodes" up to the root. The index of the lowest and the rightmost "father-node" is (N div 2); 

(Note, that in the above placed figure of the heap-tree with the 11 nodes,  the lowest and the rightmost "father-node" has index 11 div 2 = 5 ). 

The following statement makes the heap:

for i:=Right div 2 downto 1 do SiftDown(A,i,Right); 
  
The Heap-Sort works in the following way:

1	Create heap. The maximal value is in the root on the index=1.
2	 Swap the root with the currently last index. Its result is violating the  rule of  heap in the root. The right part of an array - from currently last index to N is ordered. 
3	Currently last index is thereby decreased by 1.
4	Calling the SiftDown the heap is re-established. 
5	The cycle is repeated until the right part contains entire array.

The resulting procedure has the form:

procedure HeapSort(var A:TArr);
var
  i,Left,Right:integer;
begin
  Left:= N div 2; (* index of the rightmost, lowest father-node *)
  Right:=N;
  for i:= Left downto 1 do SiftDown(A,Left,Right); (* Creation of the heap *)

  for Right:=N downto 2 do begin  (* Cycle of the own Heap-sorting *)
    A[1]:=:A[Right];  (* swapping of the root with the currently last 
                          item *)
    SiftDown(A,1,Right-1)  (* Re-establishing of heap *)
  end; (* for *)
end; (* procedure *)

Analysis:

a) Heap-sort is not stable! Heap-sort does not behave naturally! Method  works "in situ" (no need for additional array space!). 

b) Time complexity has linearithmic order (n * lg(n)).
•	maximal time complexity: TM(n) ~= 31.5 * n * lg(n-1)

Experimental values of time units for an array with n items ordered initially randomly (RAO), ordered initially inversely (INV) and initially properly ordered (IPO) are in the following table: (numbers in the table expresses time units). 

n | (256) | (512)
IPO | 42 | 210
RAO | 38 | 186
INV | 40 | 196

 The home assignments:

1) Use the Select Sort to create the list of students ordered according to the multiple keys.

The necessary types are:
TBranch = (Informatics, Electronics, Cybernetics, PowerEng);
TStudent = record
              Name:string;
              YearOfStudy:integer;
              Branch:TBranch;
              GPA:real;
	  IdentNo:integer
           end;
TArray=array[1..200] of TStudent;
Suppose the a
The created list should be ordered according to:

    Branch, Year in the Branch, GPA in the year, Name in the GPA.

2)  Create the procedure which sorts the source array A full of students without movement of items, creates the inner array of indexes and ordered linked list (by using the inner array of pointers) and place the resulting array into output array B. As a sorting key use IdentNo.

procedure Sort(A:TArr; var B:TArr);

3)  Modify the SelectSort for sorting without movement of the items. Sort  the array A of students without the movement of items according the name. Create the array B:TArr,  which will be finally sorted, by moving the items from A to B.

4)  Modify the SeletSort for sorting without movement of the items. Sort the array A of students by name without the movement of items. Create the linked list of items by means of PointArr. Sort the array A "in situ" by means of  McLarren algorithm. 

5)  Modify the Bubble-Select-Sort for sorting with multiple key. From the input array AI, create two output arrays AAge and ABirth, containing the  list of persons sorted by the age (AAge) or a list of persons sorted according to the birthday.

The type of item is:
type
  TPerson = record
     Name: string;
     Year:integer;
      Month:integer;
      Day:integer
  end;	
	
6) Modify the Heapsort the same way as the first and third previous exercises (for sorting without movement and for sorting with multiple keys). Use source array A and destination array B of students. Sort them without movement according the  GPA and the result place into the array B.

Updated: 1/2/2003