Previous: 10.2.1 Selection Sort
Up: 10.2 Improving Search - Sorting the Data
Next: 10.2.3 Insertion Sort
Previous Page: 10.2.1 Selection Sort
Next Page: 10.2.3 Insertion Sort
Previous: 10.2.1 Selection Sort
Up: 10.2 Improving Search - Sorting the Data
Next: 10.2.3 Insertion Sort
Previous Page: 10.2.1 Selection Sort
Next Page: 10.2.3 Insertion Sort
An alternate way of putting the largest element at the highest index in the array uses an algorithm called bubble sort. While this method is neither as efficient, nor as straightforward, as selection sort, it is popularly used to illustrate sorting. We include it here as an alternate method.
Like selection sort, the idea of bubble sort is to repeatedly move the largest element to the highest index position of the array. As in selection sort, each iteration reduces the effective size of the array. The two algorithms differ in how this is done. Rather than search the entire effective array to find the largest element, bubble sort focuses on successive adjacent pairs of elements in the array, compares them, and either swaps them or not. In either case, after such a step, the larger of the two elements will be in the higher index position. The focus then moves to the next higher position, and the process is repeated. When the focus reaches the end of the effective array, the largest element will have ``bubbled'' from whatever its original position to the highest index position in the effective array.
For example, consider the array:
In the first step, the focus is on the first two elements (in bold) which are compared and swapped, if necessary. In this case, since the element at index 1 is larger than the one at index 0, no swap takes place.
Then the focus move to the elements at index 1 and 2 which are compared and swapped, if necessary. In our example, 67 is larger than 12 so the two elements are swapped. The result is that the largest of the first three elements is now at index 2.
The process is repeated until the focus moves to the end of the array, at which point the largest of all the elements ends up at the highest possible index. The remaining steps and result are:
The largest element has bubbled to the top index of the array. In general, a bubble step is performed by the loop:
for (k = 0; k < eff_size - 1; k++)
if (x[k] > x[k + 1])
swaparay(x, k, k + 1);
The loop compares all adjacent elements at index k and k + 1. If they are not in the correct order, they are swapped. One complete bubble step moves the largest element to the last position, which is the correct position for that element in the final sorted array. The effective size of the array is reduced by one and the process repeated until the effective size becomes one. Each bubble step moves the largest element in the effective array to the highest index of the effective array.
The code implementing this algorithm is the function, bubblesort()
shown in Figure 10.7.
The function repeats bubble steps, using the function
bubblemax(), as many times as the size of the array.
This function is passed the array name and the size of the effective array. The
size of the effective array is the original size reduced by one after each
step. Thus, if the initial size of the array to be sorted is lim,
the size of each successive effective array is
lim, lim -1, lim - 2, etc. We have included
a debug statement in bubblesort()
to trace the bubble process after each bubble step.
The function, bubblemax(), compares adjacent elements of an array of the
specified size in sequence and swaps them if necessary. The function
is shown in Figure 10.8 together with
the function, swaparay() to swap elements in an array.
All these functions are included in file, sortsrch.c,
and their prototypes are
included in file, sortsrch.h, also shown in the Figure.
It should be clear that bubble sort is not as efficient as selection sort. There is a great deal of swapping required in bubble sort to ``bubble'' the largest element to the highest index; where in selection sort, it is done by a single swap. On the other hand, if the data is mostly sorted, then bubble sort can be made more efficient.
To illustrate the operation of bubble sort, we now write a program driver to exercise bubble sort shown in Figure 10.9. It uses bubblesort() on the same array used in our search example above. The initialized unsorted array is printed; then the array is sorted and printed. Each bubble step is explicitly shown by a debug statement. Note that DEBUG is defined during program development and removed when the program is debugged.
Sample Session:
There are several ways to improve the bubble sort algorithm. First, a single function should incorporate the entire algorithm (Figure 10.10). The time overhead of a function call in a loop can be quite large if the array is large.
Next, a minor point: since an array of one element is already sorted, at most
bubbling steps are needed for an array of size
. The first for loop need
be executed no more than lim - 1 times.
More important, if the entire array is
sorted at some time in the process, no further processing is needed. An array
is sorted if no elements are swapped in a bubble step. We will use a flag to
keep track of any swapping.
Figure 10.11 shows the revised code.
We include a file, tfdef.h, that defines TRUE and FALSE. In the function, we use a flag, swap, to keep track of any swapping in the bubble step. For each bubble step, we initially assume swap is FALSE. If there is any swapping in the bubble step, we set the flag to TRUE. The sort process repeats as long as swap is TRUE. To get the process started, swap is initialized to TRUE.
These improvements may be important for large arrays. If an array is sorted after the first few steps, the process can be terminated with a saving in computation time. The program, bsrtaray.c, can be modified to use the above bsort() function instead of bubblesort() function. A sample output of such a modified program is shown below.
Sample Session (Modified bsrtaray.c):
Note that the process stops as soon as the effective array of size 3 is found to be sorted. If the original data is almost sorted, then bubble sort can be efficient.