The 'bubble' sort is one of the most popular sorting algorithms, mainly because it is simple to understand, though it is probably not the most efficient in terms of computer time. Sorting is often performed on arrays of data, putting the items in either ascending or descending order, though it can also be performed on files where it is known as a 'merge sort'. Other sorting algorithms include the 'insertion' sort, the 'shell' sort and the 'quick' sort methods.
The speed with which different algorithms sort lists of items depends on the size of the data set and the extent to which the data is already in some kind of order. The bubble sort is not thought to be very efficient with large data sets but it is fine for small data sets and where the programmer wants to implement something simple that he can remember easily. It is also a good place to start in understanding the mechansims of sorting.
Given an array of, say, 10 numbers in no particular order the task of any sorting algorithm is to move the numbers between cells until they are in order, ascending or descending. This is done by systematically comparing pairs of numbers and swapping them if their order does not match what is required. We will work on the following data set:
23 12 54 36 76 14 98 15 83 11
Stored in an array, these data will be known as number_list[1], number_list[2]... number_list[10].
The bubble sort tackles the problem of sorting by comparing every possible pair of numbers in the list. Thus the first item is compared with the remaining nine, the second with the remaining eight, the third with the remaining seven, and so on. The number of comparisons is thus (9+8+7+6+5+4+3+2+1)=45 (given by the formula n*(n+1)/2), where n is 1 less than the number of items in the array).
In the case of our numbers 23 is compared with 12 and, for an ascending sort, they are swapped over; 12 is now compared with 54, 36, through to 11, which is swapped with 12, so after one pass the list looks like this:
11 23 54 36 76 14 98 15 83 12
11 is in the right place but 12 has gone further out of place - no matter, subsequent passes will move it back to its correct place.
Now 23 is compared with 54, 36, etc. until the list looks like this:
11 12 54 36 76 14 98 15 83 23
The code for implementing this procedure requires two nested for loops:
for i := 1 to length_of_list - 1 do
for j := i + 1 to length_of list do
The outer loop starts at the first item and ends at the last but one; the inner loop starts at the item after i and ends at the last item in the list. The outer loop finishes 1 short to avoid the error of comparing the last item in this loop with a non-existent item in the inner loop (i+1). The inner loop starts at i+1 so that adjacent cells are compared.
The code to compare and swap items is as follows:
if number_list[i] > number_list[j] then
begin
temp:=number_list[i];
number_list[i] := number_list[j];
number_list[j] := temp;
end
That's it! The data type can be almost anything, including record types where any field can be used as the sort key:
if my_list[i].name > my_list[j].name then
begin
temp:=number_list[i];
number_list[i] := number_list[j];
number_list[j] := temp;
end
You can see a bubble sort at work in the TList section.
The 'quick sort' method is considered later.