Read Chpt. 14.3, Study sort1.f, sort2.f, and sort3.f

CSHIFT and EOSHIFT intrinsic functions

Now that you have most of the basics of Fortran down, its time to get more serious about programming applications and you can't have a Computer Science class without talking about sorting methods. In this specific discipline, sorting algorithms are very valuable for Compilers and Operating Systems and Systems Utilities. Usage is much lower in other areas of Engineering and Science, but at some time or another you are likely to need to do some sorting of information.

Sorting has been done for over 40 years by hundreds of programmers with much more skill in that area than you or I could develop in any reasonable time. So the best first reaction to dealing with a sorting problem is to look for a public domain subroutine that will do the job. The first place to look for Subprograms that do Scientific, Mathematical, and Engineering tasks is Netlib. Using their search engine, I was able to locate a subroutine called ssort, that applies a modified Singleton Quicksort algorithm. What's that? Check the reference listed in the subroutine if you are interested (adding references in your comments is a very good programming practice). However, if I need a quick fix to a problem, it doesn't matter, as long as I know what it to do with its arguments, to plug it into a problem. For large poorly ordered array's, this subroutine should be significantly faster than the simpler methods that I will introduce here. Take a look at the way ssort changes the order in which it sorts.

We'll be using Netlib again later. If you remember no other single term exactly from this course, remember NETLIB. It will save you a tremendous amount of programming effort on a wide range of applications, both in later courses and in your professional life.

Here is a simple example with brackets marking numbers swapped during a pass.

Beginning Array : 2 3 1 7 9 5 First Pass : [9] 3 1 7 [2] 5 Second Pass : 9 [7] 1 [3] 2 5 Third Pass : 9 7 [5] 3 2 [1]Two more checks on maximum value follow, but no more swaps result.

The total number of arithmetic operations in a selection sort is always the same for a given array size. For an array with "n" elements the number of computer operations (hence computer time) is proportional to n**2.

The subroutine contained in sort1.f is my implementation of this algorithm. Note the sequence of lines necessary to swap the contents of the two elements within the array. Also notice the second array that I am swapping at the same time. When we run some sample problems, you will see that this can be used to keep track of the original index for an element in the sorted array. If I load the array called "iy" with integers equal to the element indexes, then after sorting a value of 2 in element 5 of "iy" would say that the contents in element 5 of the sorted "x" array were originally in element 2 of "x".

The total number of arithmetic operations in a bubble sort may be of the order n**2 for an array with "n" elements. In a high to low sort, the worst case would occur when the highest value started in the last element of the array. However, if the array is nearly in order, the bubble sort may complete relatively quickly ( a few times "n" operations).

The following sequence of steps on a small array illustrates a bubble sort. A subroutine to do the job has been provided in sort2.f .

**Pass 1**

Base array : 1 5 4 2 3 Swap : [5 1] 4 2 3 Swap : 5 [4 1] 2 3 Swap : 5 4 [2 1] 3 Swap : 5 4 2 [3 1]

No Swap : [5 4] 2 3 1 No Swap : 5 [4 2] 3 1 Swap : 5 4 [3 2] 1Pass is done because we know the last element is in the right position

**Pass 3**

No Swap : [5 4] 3 2 1 No Swap : 5 [4 3] 2 1Pass is done because we know the last two elements are in the right positions

**No swaps in pass 3, sort completed.**

The total number of arithmetic operations in an insertion sort may be of the order n**2 for an array with "n" elements. In a high to low sort, the worst case would occur when the array is originally perfectly ordered from low to high value. However, if the array is nearly in order, the insertion sort will complete relatively quickly ( a few times "n" operations) because few insertion shifts are required.

Examples of the insertion sort are provided in sort3.f and sort3a.f. The latter uses a new Fortran 90 intrinsic function called CSHIFT to handle the shifting of the array elements. The "C" stands for "circular", meaning that any elements that are shifted off of one end of the array are reinserted at the other end of the array in space vacated by other shifted elements. If I had wanted any elements shifted off of the end of the array to vanish (and perhaps specify special treatment for filling vacated elements at the other end), I would have used the EOSHIFT intrinsic function.

Here is a simple example of an insertion sort. In each step square brackets surround the portion of the array that is shifted, and parentheses surround the value that is inserted.

Base array : 1 3 4 2 5 Shift : (3)[1] 4 2 5 Shift : (4)[3 1] 2 5 Shift : 4 3 (2)[1] 5 Shift : (5)[4 2 3 1]

f77 drvsort.f sort1.f

The resulting executable file (a.out) will be the same as if the contents of drvsort.f and sort1.f had been combined in a single file and that file compiled.

I take advantage of this feature with the shell script runit, existing in the same subdirectory (sort) as all of my sample sorting subroutines. It uses a csh "foreach" loop to compile and run drvsort.f with each of the various methods of sorting, verifying that all subroutines produce the same correct results.

It is actually standard practice in a Unix environment (regardless of programming language), to place each program unit (main program, subroutine, function) in its own file. The files are all stored in a subdirectory set aside for that particular program's source code. Normally the names of files match the names of the program units, although the main program is simply named "main.f". One quick way to compile the full program is to change to the program's directory, and type:

f77 *.f

As you become a more frequent user of programming under Unix (regardless of your choice in programming language) you should take the time to master the use of the "make" utility. This will make the creation of an executable program much simpler for you.

Written and Maintained by John Mahaffy : jhm@psu.edu