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:

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

**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.