2005~2007 HKCEE ( CIT )

Pascal Programming

Task 18 Telephone Directory (Bubble Sort)

Bubble Sort

to arrange a list of data in a certain order (ascending order or descending order)
to compare all adjacent elements in the list of data successively and swap (exchange) them if they are not in the right order
Advantage : simple and easy to understand
Disadvantage : inefficient when the size of a list is very large

Part I

The algorithm for Bubble Sort in ascending order (1^st version)

Repeat each pass
    For a list of N elements, do
       Compare each pair of adjacent elements in the list
       If the first element is greater then that of the second element, then swap the values
until N passes

Bubble1.pas is the simplest version of Bubble Sort (1st version)(simplest version).

The following are the sample outputs the sample program bubble1.pas.

Sample Output 1

Sample Output 2

<< Bubble Sort 1 >>

Enter 5 integers :
4
5
1
3
2

Original list 4 5 1 3 2

Pass 1
   4 5 1 3 2
   4 1 5 3 2
   4 1 3 5 2
   4 1 3 2 5
Pass 2
   1 4 3 2 5
   1 3 4 2 5
   1 3 2 4 5
   1 3 2 4 5
Pass 3
   1 3 2 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
Pass 4
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
Pass 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5

Sorted List 1 2 3 4 5

<< Bubble Sort 1 >>

Enter 5 integers :
1
2
3
4
5

Original list 1 2 3 4 5

Pass 1
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
Pass 2
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
Pass 3
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
Pass 4
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
Pass 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5

Sorted List 1 2 3 4 5

The algorithm for Bubble Sort in ascending order (2^nd version)

For each pass
    Repeat
        For each pair of adjacent elements in the working list
            Repeat
                Swap them if they are not in the proper order
            until the end of working list
    until (N-1) passes have been completed

Bubble2.pas is the modified version of Bubble Sort (2nd version)(better version).

The following are the sample outputs the sample program bubble2.pas.

Sample Output 1

Sample Output 2

<< Bubble Sort 2 >>

Enter 5 integers :
4
5
1
3
2

Original list 4 5 1 3 2

Pass 1
   4 5 1 3 2
   4 1 5 3 2
   4 1 3 5 2
   4 1 3 2 5
Pass 2
   1 4 3 2 5
   1 3 4 2 5
   1 3 2 4 5
Pass 3
   1 3 2 4 5
   1 2 3 4 5
Pass 4
   1 2 3 4 5

Sorted List 1 2 3 4 5

<< Bubble Sort 2 >>

Enter 5 integers :
1
2
3
4
5

Original list 1 2 3 4 5

Pass 1
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
Pass 2
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
Pass 3
   1 2 3 4 5
   1 2 3 4 5
Pass 4
   1 2 3 4 5

Sorted List 1 2 3 4 5

The algorithm for Bubble Sort in ascending order (3^rd version)

For each pass
    Repeat
        For each pair of adjacent elements in the working list
            Repeat
                Swap them if they are not in the proper order
            until the end of working list
    until ((N-1) passes have been completed) or
            (no swapping throughout the comparison of the working list)

This is the last modified version of Bubble Sort (3rd version)(best version).

The following are the sample outputs of the 3rd version of Bubble Sort.

Sample Output 1

Sample Output 2

<< Bubble Sort 3 >>

Enter 5 integers :
4
5
1
3
2

Original list 4 5 1 3 2

Pass 1
   4 5 1 3 2
   4 1 5 3 2
   4 1 3 5 2
   4 1 3 2 5
Pass 2
   1 4 3 2 5
   1 3 4 2 5
   1 3 2 4 5
Pass 3
   1 3 2 4 5
   1 2 3 4 5
Pass 4
   1 2 3 4 5

Sorted List 1 2 3 4 5

<< Bubble Sort 3 >>

Enter 5 integers :
1
2
3
4
5

Original list 1 2 3 4 5

Pass 1
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5
   1 2 3 4 5

Sorted List 1 2 3 4 5

Write a Pascal program to implement the above algorithm of Bubble Sort by using a while loop and a Boolean variable sorted
- while (pass < N) and (not sorted) do
After coding, save your file as bubble3.pas at the drive S:\www\0507cit\programming\.
Execute your program and fix any problem occurred.

Part II

Using the 3rd version of Bubble Sort to sort the telephone directory of a class in alphabetic order.

The follwoing is the content of part of a telephone directory of a class.

	4Aphone.dat		Description
	CHAN TAI MAN 852-10256822 POON BO BO 852-13256888 CHEUNG DO DO 852-36254170		Student's Name Telephone Number Student's Name Telphone Number Student's Name Telephone Number

Below are the sample outputs of a Pascal program. In these outputs, the information following the colon are entered through the keyboard by the user. All other items are output from the program.

Sample Output

Class : 4A

Telephone Directory in alphabetic order
=======================================

    Chan Tai Man        852-10256822
    Cheung Do Do        852-36254170
    Poon Bo Bo          852-13256888

	4Aphone.dat (updated)
	CHAN TAI MAN 852-10256822 CHEUNG DO DO 852-36254170 POON BO BO 852-13256888

Main Program

Declare the following Global Constants with suitable value within the main program
- cls_size (to store the possible maximum number of students in a class)
Declare the following Global Variables within the main program with the suitable data type (integer, text , string[x] or string)
- class (to store the class name and 2 characters in length) (e.g. 4A, 4B, 4C etc.)
- classfile (internal file variable used by the program for the source file and the updated file)
- name (a string array to store the students' names)
- phone (a string array to store the students' telephone numbers)
- i (act as an index of an array)
Prompt the user to enter the class name.
Prepare the source file for input (class + 'phone.dat')(e.g. 4Aphone.dat)
Read all data from the source file to the corresponding arrays.
Close the input file.
Using the best algorithm of bubble sort to sort the telephone directory in alphabetic order.
- exchange the data if they are not in the proper order (by calling the procedure swap(name[i], name[i+1]) or swap(phone[i], phone[i+1])
Display the sorted list of telephone directory on the screen.
Send the updated list to the file.
- Prepare the updated file for output (class + 'phone.dat')(e.g. 4Aphone.dat)
- Transfer the array back to the file again
- Close the output file

Sub-program (procedure)

Details of the procedure swap (exchange two values)
- Declaration of a procedure swap
       procedure swap ( var   first , second : string );
       var temp : string;
       begin     {swap}
          <statements>
       end;      {swap}
After coding, save your file as t18.pas at the drive S:\www\0507cit\programming\.
Execute your program and fix any problem occurred.