Sorting Programs

There are three common algorithms used to sort or reorder a list of values in ascending order (from lowest to highest): selection sort, bubble sort, and insertion sort. The best or most efficient sort depends on the situation.

The selection sort starts by finding the smallest number in the list and exchanging it with the first number. The next smallest number is found and exchanged with the second number, and so on. Use of the selection sort to order the first five elements of the array gest is described below:

SELECTION SORT

In this example, we start with gest(1) and go through the following steps described as one pass.

Pass one:

is gest(2) less than gest(1)? NO
is gest(3) less than gest(1) YES; the subscript 3 is saved because it contains the smallest value so far
is gest(4) less than gest(3)? NO
is gest(5) less than gest(3)? NO

The value in gest(1) is saved (save=gest(1)) before gest(1) is assigned the value in gest(3). The exchange of gest(1) and gest(3) is complete when gest(3) is assigned the value in save. Now the first element, gest(1), contains the smallest value and we proceed to gest(2).

Pass two:

is gest(3) less than gest(2)? YES; the subscript 3 is saved because it contains the smallest value so far
is gest(4) less than gest(3)? NO
is gest(5) less than gest(3)? YES; the subscript 5 is saved because it contains a smaller value than gest(3) contains

The value in gest(5) and gest(2) are exchanged in the same manner as the first exchange.

This process continues until the values are sorted. If there are n values, it will take a maximum of (n-1) passes to complete a sort.

The code for this selection sort is listed below with comments; assume that gest has been declared to be an INTEGER array and that the values 210, 250, 22, 280, 63 have been read into gest(1), gest(2), gest(3), gest(4), and gest(5), respectively.

PUT select.f HERE

Bubble Sort

Using the bubble sort, we compare adjacent elements and exchange their values if the first of the two values is greater than the second. You will see, in the following example, that one pass, a comparison between each pair of adjacent values, does not order all of the values, but the largest value does end up being the last value. Therefore, in the next pass you must only compare gest(1) and gest(2), gest(2) and gest(3), and gest(3) and gest(4); gest(5) is already in its correct position of order. After a second pass gest(4) and gest(5) are in the correct order, so only two comparisons must be made; after a third pass, gest(3), gest(4), and gest(5) are in the correct order; and, after the fourth and last pass, a comparison is made between gest(1) and gest(2). In this example, gest(1) was less than gest(2), so an exchange did not take place during the fourth pass. In general, in the bubble sort, the sorting of n values is complete after a maximum of (n-1) passes.

BUBBLE SORT

Insertion Sort

The insertion sort also compares adjacent values, but instead of working down the list with comparisons, if an exchange is made, this sort works backwards comparing the exchanged value with all previous values until the value is in its correct position. The sort then returns to the position in the list of the value that was out of order where it looks for the next value that is out of order.

In this example, gest(1) and gest(2) are compared but not exchanged, so gest(2) and gest(3) are compared. Their values are exchanged, so now gest(2) and gest(1) are compared and, in this case, their values are exchanged. Since the first three elements are now ordered among themselves, a comparison is made between gest(3) and gest(4). No exchange is made in this case, so gest(4) and gest(5) are compared. Since gest(5) is smaller than gest(4), an exchange is made and gest(4) is compared with gest(3), gest(2), and gest(1). After appropriate exchanges are made, all values are ordered.

INSERTION SORT