Advanced Assembly Programming - The HCS12/9S12: An Introduction to Software and Hardware Interfacing - page 158

method is called the bubble sort because each number slowly bubbles up to its proper position.
After the second iteration the array is in the order
13 9 35 98 120 54 10 30 157 810
Notice that 157 is now in the second-highest position. Since each iteration places a new
element into its proper position, an array or a file of n elements requires no more than n 2 1
iterations. The complete set of iterations is as follows:
Iteration 0 (original array) 157 13 35 9 98 810 120 54 10 30
1 13 35 9 98 157 120 54 10 30 810
2 13 9 35 98 120 54 10 30 157 810
3 9 13 35 98 54 10 30 120 157 810
4 9 13 35 54 10 30 98 120 157 810
5 9 13 35 10 30 54 98 120 157 810
6 9 13 10 30 35 54 98 120 157 810
7 9 10 13 30 35 54 98 120 157 810
8 9 10 13 30 35 54 98 120 157 810
9 9 10 13 30 35 54 98 120 157 810
There are some obvious improvements to the foregoing method.
• First, since all elements in positions greater than or equal to n 2 i are already
in proper position after iteration i , they need not be considered in succeeding
iterations. Thus, in the first iteration n 2 1 comparisons are made, on the second
iteration n 2 2 comparisons are made, and on the ( n 2 1)th iteration, only one
comparison is made (between x[0] and x[1]). Therefore, the process is sped up as it
proceeds through successive iterations.
• Second, although we have shown that n 2 1 iterations are sufficient to sort an array
or a file of size n , in the preceding sample array of 10 elements, the array was sorted
after the seventh iteration, making the last two iterations unnecessary. To eliminate
unnecessary iterations, we must be able to detect the fact that the array is already
sorted. An array is sorted if no swaps are made in an iteration. By keeping a record of
whether any swaps are made in a given iteration, it can be determined whether any
further iteration is necessary. The logic flow of the bubble sort algorithm is illustrated
in Figure 4.7. The following example implements the bubble sort as a subroutine:

Example 4.5
▼

Write a subroutine to implement the bubble sort algorithm and a sequence of instructions
along with a set of test data for testing this subroutine. Use an array that consists of n 8-bit
unsigned integers for testing purposes.
Solution: The bubble sort subroutine has several local variables.
• buf . buffer space for swapping adjacent elements
• inOrder . flag to indicate whether the array is in order after an iteration
• inner . number of comparisons remaining to be performed in the current iteration
• iteration . number of iterations remaining to be performed
The stack frame of the bubble sort subroutine is shown in Figure 4.8.
arr equ 13 ; distance of the variable arrayX from stack top

arcnt equ 12 ; distance of the variable arcnt from stack top

buf equ 3 ; distance of local variable buf from stack top