Topic 9.4 Improving a Bubble Sort.
Why sorting?
Sorting things out is a very natural human activity since
it gives us the impression of order. From
the time we are kids we find out ways (something weird ways) of sorting toys,
crayons, or pictures. When we sort, we
convert a set of items in no particular order, into a sequence of ordered items
Since computers cannot do anything we do not instruct
them to do, we have to spell out the rules of sorting with a great deal of
precision. Sorting is a very essential
topic in computer science since many other procedures rely on sorting for their
execution.
For instance, a computer receives the following set:
Set1 = {11, 2, 48, 13, 9, 5, 6, 21} and
Transforms it into S2 = {2, 5, 6, 9, 11, 13, 21, 48}
How does a computer do this? There are several methods for sorting. Here, we will illustrate the bubble sorting
method.
Bubble Sort Method
Like the other sorting methods, bubble sorting is
appropriate for a small set of data (1000-1500 items) and takes about the same
time and the same amount of memory to be executed.
Bubble sorting is certainly one of the best-known sorting
methods but it is one of the most inefficient.
It takes its name from the nature of its procedure, in which the
smallest or the largest item “bubbles” to the end of execution. The procedure is very direct as it considers
two adjacent elements and changes them if necessary. Then consider the next two, exchange them if
necessary, and continue until there are no more elements in the list. In a list containing n elements, the
process gets repeated n-1 times.
Given the set of elements S3 = {3, 2, 1},
we will bubble sort them into ascending order, and moving from left to right we
get:
3 2 1 2
and 3 are swapped
2 3 1 3
and 1 are swapped
2 1 3 end of
first pass
2 1 3 1
and 2 are swapped
1 2 3 2
and 3 are in the correct places, therefore no need to swap
1 2 3 End of
second pass, S3 is sorted.
As we sorted S3 from right to left, the smallest element
occupies the leftmost position, and at the end of the sort, it occupies the
rightmost position.
The algorithm for sorting from left to right into
ascending order is:
Array is declared S3[0…n-1]
- Loop
from i = 0 to n-1
- Loop from j = 0 to n-1
Compare each pair of
elements. If second is smaller than
firs, swap them: S3 [j + 1]
S3 [j] - End
- End
The C code for this procedure is as follows:
#include <stdio.h>.
#include <stdlib.h>
void bubble_sort(int array[], int size)
{
int temp, I, J ;
for
(I = 0; I < n - 1; I++)
for(J = 0; J< n -
1; J++)
If (array[I] < array[J]
` {
temp = array[I];
array[I] = array[J];
array[J] = temp;
}
}
A way to improve the Bubble Sort Method
This procedure is inefficient, however, since data that
has already been sorted is re-examined on each pass. For example, given S4 = {10, 4, 14, _3, 12,
6}, after the first pass
S4 = {4, 10, _3, 12, 6, 14}.
The last element, 14, is in the correct place and does not need to be
reconsidered in the second pass. After
the second pass when S4 = {4, -3, 10,
6, 12, 14}, the las two elements are correctly positioned, and only the first 4
data elements need to checked during the third pass. The procedure will continue until only the
first two values need to be checked. The
loop J = n-1 therefore needs to be
reduced by 1 after each pass over the data before the outer loop, (I = 0 to n – 1) Thus, data that has “bubbled”
into the correct place is not re-sorted unnecessarily.
The C code for this procedure is as follows:
#include <stdio.h>.
#include <stdlib.h>
void better_bubble_sort(int array[], int size)
{
int temp, I, J ;
for
(I = 0; I < n - 1; I++)
for(J = 0; J< ( n – 1) – I; J++)
If (array[I] < array[J]
` {
temp = array[I];
array[I] = array[J];
array[J] = temp;
}
}