Sorting arrays

Fortran 2018 has no sorting intrinsic. A program that needs an ordered array writes the sort, and the two sorts worth knowing by hand are the bubble sort, which is short enough to read out loud, and the selection sort, which is short enough to build from minloc. This lesson writes both, counts their work, and then sorts records without moving them.

A bubble sort

The bubble sort walks the array and swaps every neighbouring pair that is out of order. One pass moves the largest remaining value to the end, so the next pass can stop one place earlier; after n - 1 passes the array is sorted.

The file bubble.f90 prints the array after every pass and counts the swaps:

program bubble_demo implicit none integer, parameter :: n = 8 integer :: a(n), i, j, tmp, swaps logical :: changed a = [5, 2, 9, 1, 7, 3, 8, 4] swaps = 0 do i = 1, n - 1 changed = .false. do j = 1, n - i if (a(j) > a(j + 1)) then tmp = a(j) a(j) = a(j + 1) a(j + 1) = tmp swaps = swaps + 1 changed = .true. end if end do print *, "pass", i, ":", a if (.not. changed) exit end do print *, "sorted :", a print *, "swaps :", swaps end program bubble_demo

gfortran -Wall -Wextra -std=f2018 bubble.f90 -o bubble
./bubble

pass 1 : 2 5 1 7 3 8 4 9
pass 2 : 2 1 5 3 7 4 8 9
pass 3 : 1 2 3 5 4 7 8 9
pass 4 : 1 2 3 4 5 7 8 9
pass 5 : 1 2 3 4 5 7 8 9
sorted : 1 2 3 4 5 7 8 9
swaps : 13

Read the first pass: the nine travelled to the end, and the five travelled one place left at the start; every pass puts one more value in its final place. The last two passes print the same array, which is the signal the early exit is looking for.

Stopping early

changed is set when a pass swaps anything and cleared at the start of each pass. A pass with no swap proves the array is sorted, so the loop leaves at once with exit instead of running the remaining passes. On this input the fifth pass is the first quiet one, and it is also the last the loop could run: the test is at the end of the body, so the exit saves nothing here.

The saving is real on an almost sorted array, and the cost of the flag is one logical variable. The swap itself is three assignments through a temporary, because Fortran has no a, b = b, a form outside an array constructor.

A selection sort with MINLOC

The selection sort finds the smallest remaining value and puts it in the next place, once per position. With minloc the search is one line, and the position it returns is relative to the section it was given, which is why the code adds i - 1 back.

program selection_demo implicit none integer, parameter :: n = 8 integer :: a(n), i, k, tmp a = [5, 2, 9, 1, 7, 3, 8, 4] do i = 1, n - 1 k = i - 1 + minloc(a(i:), dim=1) tmp = a(i) a(i) = a(k) a(k) = tmp end do print *, "sorted :", a end program selection_demo

gfortran -Wall -Wextra -std=f2018 selection.f90 -o selection
./selection

sorted : 1 2 3 4 5 7 8 9

minloc(a(i:)) on a rank-one section returns a rank-one array of one element, so the dim=1 is what makes it a scalar; without it the assignment is a rank error, which is exactly the error the compiler printed while this page was written. The sort does at most n - 1 swaps and n searches, and it is the cheaper of the two when a swap is expensive.

Sorting records with an index

A record is usually several arrays that must stay aligned, and moving all of them for every swap is work a program can avoid: sort an array of indices instead and read the records through it. The data never moves, and the same index serves every column.

program index_demo implicit none integer, parameter :: n = 5 integer :: score(n), order(n), i, j, tmp character(len=8) :: name(n) name = ["alice ", "bob ", "carol ", "dave ", "erin "] score = [72, 91, 65, 88, 91] order = [(i, i = 1, n)] do i = 1, n - 1 do j = 1, n - i if (score(order(j)) < score(order(j + 1))) then tmp = order(j) order(j) = order(j + 1) order(j + 1) = tmp end if end do end do do i = 1, n print '(a,a,i4)', " ", name(order(i)), score(order(i)) end do end program index_demo

gfortran -Wall -Wextra -std=f2018 index_sort.f90 -o index_sort
./index_sort

bob 91
erin 91
dave 88
alice 72
carol 65

The comparison is < between scores, so the order is descending, and it is strict: bob and erin have the same score and bob comes first, which is the order of the input. That property is called stability, and a strict comparison in an exchange sort keeps it by accident; a sort that needs it guarantees it by comparing the second key when the first is equal.

The format '(a,a,i4)' prints a literal, the name and the score with no spaces between them, which is why the two leading blanks in the string are there: they align the output by hand.

Which sort to write

Both sorts are quadratic: a thousand values need about half a million comparisons, a million values need a trillion. For the small tables a program reads from a file, either one is fine and the index version is the one to write. For anything larger the answer is a library: sorting is the one thing a numerical code should not write by hand, and the language has no sorting intrinsic to reach for.

The other reason to keep the sort small is testing: a sort that is twenty lines can be checked against a hand-written order, and a test written against a small case with a known answer is what a sort needs before anything larger relies on it.

Exercises

  1. Sort an array that is already sorted with the bubble sort. How many passes and how many swaps does the output show?
  2. Change the comparison of the bubble sort to a(j) < a(j + 1). What order comes out?
  3. Sort the five records by name instead of by score. Which comparison line changes?
  4. Make the index sort stable for equal scores by adding a second comparison on the name. What does the output look like now?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does one pass of a bubble sort guarantee?

    Answer

    The largest remaining value is in its final place at the end

    Each pass bubbles the largest value to the end of the unsorted part.

  2. Why is the array printed after the fifth pass the same as after the fourth?

    Answer

    The array was already sorted, so the pass swapped nothing

    A quiet pass is the test for a sorted array, and the early exit uses it.

  3. What does this program print? program p implicit none integer :: a(3), i, j, t a = [3, 1, 2] do i = 1, 2 do j = 1, 3 - i if (a(j) > a(j + 1)) then t = a(j) a(j) = a(j + 1) a(j + 1) = t end if end do end do print *, a end program p

    Answer

    1 2 3

    Two passes of a swap sort put three values in ascending order.

  4. Why does the selection sort add i - 1 to the result of MINLOC?

    Answer

    MINLOC counts from the start of the section, not from the start of the array

    The section a(i:) starts at i, so its first element is position i.

  5. What is the cost of a bubble sort on n values?

    Answer

    About n squared comparisons

    The two nested loops give a quadratic count.

  6. What does an index sort keep in place?

    Answer

    The data arrays; only the array of indices moves

    The records are read through the sorted index.

  7. Why do bob and erin keep their input order when both score 91?

    Answer

    The comparison is strict, so equal values are never swapped

    A strict comparison leaves equal neighbours where they are.

  8. Which intrinsic returns the position of the smallest element of a section?

    Answer

    minloc

    minloc is the locator; minval gives the value.

  9. What does the early exit in the bubble sort test?

    Answer

    That the last pass swapped nothing

    A pass without a swap proves the order is already correct.

  10. What is a stable sort?

    Answer

    One that keeps the input order of equal keys

    Equal keys keep their relative order.

The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image