Notes A4: EXAMPLES: Recursion vs. Iteration
[Return to Math 60 Homepage |
Return to Notes Listing Page]
Contents
Selection sort works by "selecting" the smallest (largest) element
in a sublist of an array (i.e., from location i to the limit),
and then switching that element with what is in the location it
really belongs in (i.e., location i). And repeating this
selection process while repeatedly reducing the size of the
sublist of the array (i.e., moving the starting location
slowly from i to limit-1).
A example in Fortran 90/95 of selection sort can be found
here.
We can attempt to change this process into a recursive process
by thinking about "finding the minimum" recursively and
then thinking about how one sorts the list starting
at location first + 1 recursively
assuming that one has already found a minimum for the
list starting at location first.
Insertion sort works by "inserting" element i
into a sublist of an array (i.e., from location 1 to i)
at the proper place (assuming that all the elements in front
of it are already in order). It "inserts" the element
but shifting elements larger than it up a location until
it find the right location to "remain."
The sort repeats this
insertion process while repeatedly increasing the size of the
sublist of the array (i.e., moving the ending location
of the sublist slowly from 1 to limit).
A example in Fortran 90/95 of selection sort can be found
here.
We can attempt to change this process into a recursive process
by thinking about "finding the location" recursively and
then thinking about how one sorts the list starting
at location i
assuming that one has already sorted the
list between location 1 and location i-1
and one can insert the item in location i into the
proper place in the earlier section of the list!
This page is maintained by Dennis C. Smolarski, S.J.
dsmolarski@math.scu.edu
© Copyright 2000 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 10 February 2000.