Programming – Pascal: Essential skills 3

 Programming – Pascal: Essential skills 3

 

Learning Outcomes:

Apply algorithms of counting, accumulating, swapping, searching, sorting and merging in writing programs.

Sorting

• Bubble sort
• Insertion sort
• Merge sort

Bubble sort principles:

Question: to sort the array in ascending order.

i	1	2	3	4	5
A[i]	12	14	5	7	8

For bubble sort, 2 elements are inspected each time, and the larger one is swapped to right if it’s not on the right.

 

i	1	2	3	4	5
A[i]	12	14	5	7	8

Then we move on to position 2 and 3.

i	1	2	3	4	5
A[i]	12	5	14	7	8

Since 14 is larger, it is swapped to the right

 

… the process goes on until…

i	1	2	3	4	5
A[i]	12	5	7	14	8

14 is larger than 7.

i	1	2	3	4	5
A[i]	12	5	7	8	14

After the first round, we are sure the largest number is on the right.

 

So we will work on the remaining 4 elements at second round.

i	1	2	3	4	5
A[i]	12	5	7	8	14

After completing second round, we are sure 12 is the second largest number in the array.

i	1	2	3	4	5
A[i]	5	7	8	12	14

 

After completing third round:

i	1	2	3	4	5
A[i]	5	7	8	12	14

We noticed no swapping happened in the third round since the 3 numbers are in order already.

So there is no need for forth round.

 

Techniques:

Suppose you have an array A[i] with n elements.

var                 i, j, temp : integer;                 swapped : Boolean; begin                 i := 0;                 repeat                                                            (* Outer loop for each round *)                                 i := i + 1;                                       (* count the number of round *)                                 swapped := false;                           (* initiate for each round *)   for j := 1 to n – i do                     (* Inner loop for swapping, 1st round 1 to n-1, 2nd round 1 to n-2, etc. *)                 if A[j] > A[j+1] then                 begin                                 temp := A[j];                (* swapping *)                                 A[j] := A[j+1];                                 A[j+1] = A[j];                                 Swapped := true                               (* if no swapping after 1 round, outer loop stops *)                 end                   until ( i = n – 1 ) or not swapped;            (* maximum number of round is n – 1 *) end;

 

Relevant past paper:

CE CIT Elect A(2005-2011): 2005 1.