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
- Sort an array that is already sorted with the bubble sort. How many passes and how many swaps does the output show?
- Change the comparison of the bubble sort to a(j) < a(j + 1). What order comes out?
- Sort the five records by name instead of by score. Which comparison line changes?
- 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.
-
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.
-
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.
-
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 pAnswer
1 2 3
Two passes of a swap sort put three values in ascending order.
-
Why does the selection sort add
i - 1to 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.
-
What is the cost of a bubble sort on n values?
Answer
About n squared comparisons
The two nested loops give a quadratic count.
-
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.
-
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.
-
Which intrinsic returns the position of the smallest element of a section?
Answer
minloc
minloc is the locator; minval gives the value.
-
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.
-
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