One of the most common uses for arrays is sorting lists. Like reversing a list, sorting is inefficient to perform on disk, and easy and fast if done in memory. Of course, if the list is very large, we may not have enough RAM to hold it. In these cases, however, we can sort parts of the list into memory, and merge them later.
Sorting is a very well-studied problem, and many sorting algorithms have been developed. The most efficient algorithms are somewhat difficult to understand, so we will focus on the simpler ones in order to demonstrate the use of arrays more easily.
One of the simplest and most intuitive sorting algorithms is the selection sort. The design of the selection sort is as follows:
To help illustrate a clean implementation process, here is a framed-out first step with stubs for reading and printing the list:
/***************************************************************************
* Usage: sort input-file output-file
*
* Sort a list of real numbers in input-file, placing the results
* in output-file. Both input and output files contain one
* number per line.
*
* Arguments:
* input-file: file to be sorted
* output-file: file to receive the sorted list
*
* History:
* Date Name Modification
* 2017-08-24 Jason Bacon Begin
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <sysexits.h>
double *read_list(size_t *size);
void print_list(const double list[], size_t list_size);
void sort_list(double list[], size_t list_size);
int main(int argc,char *argv[])
{
double *list;
size_t list_size;
list = read_list(&list_size);
print_list(list, list_size);
free(list);
return EX_OK;
}
/*
* Input list size, allocate array, and read in list.
*/
double *read_list(size_t *size_ptr)
{
double *list;
*size_ptr = 10;
list = (double *)malloc(*size_ptr * sizeof(*list));
return list;
}
void print_list(const double list[], size_t list_size)
{
printf("%zu\n", list_size);
}
shell-prompt: ./selsort
10
After testing the stubs, we fill them out and test the completed read and print functions:
/***************************************************************************
* Usage: sort input-file output-file
*
* Sort a list of real numbers in input-file, placing the results
* in output-file. Both input and output files contain one
* number per line.
*
* Arguments:
* input-file: file to be sorted
* output-file: file to receive the sorted list
*
* History:
* Date Name Modification
* 2017-08-24 Jason Bacon Begin
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <sysexits.h>
double *read_list(size_t *size);
void print_list(const double list[], size_t list_size);
void sort_list(double list[], size_t list_size);
int main(int argc,char *argv[])
{
double *list;
size_t list_size;
list = read_list(&list_size);
print_list(list, list_size);
free(list);
return EX_OK;
}
/*
* Input list size, allocate array, and read in list.
*/
double *read_list(size_t *size_ptr)
{
size_t c;
double *list;
scanf("%zu", size_ptr); // No & here, since size_ptr is a pointer
list = (double *)malloc(*size_ptr * sizeof(*list));
for (c = 0; c < *size_ptr; ++c)
scanf("%lf", &list[c]);
return list;
}
void print_list(const double list[], size_t list_size)
{
size_t c;
for (c = 0; c < list_size; ++c)
printf("%f\n", list[c]);
}
shell-prompt: ./selsort
3
6.0
2.1
9.4
6.000000
2.100000
9.400000
Finally, we implement the sort function. Note that while we work on the sort function, we need not worry about anything else, since we know that the rest of the program is already tested.
/***************************************************************************
* Usage: sort input-file output-file
*
* Sort a list of real numbers from stdin, printing the results
* to stdout. Both input and output contain one number per line.
*
* History:
* Date Name Modification
* 2017-08-24 Jason Bacon Begin
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <sysexits.h>
double *read_list(size_t *size);
void print_list(const double list[], size_t list_size);
void sort_list(double list[], size_t list_size);
int main(int argc,char *argv[])
{
double *list;
size_t list_size;
list = read_list(&list_size);
sort_list(list, list_size);
print_list(list, list_size);
free(list);
return EX_OK;
}
/*
* Input list size, allocate array, and read in list.
*/
double *read_list(size_t *size_ptr)
{
size_t c;
double *list;
scanf("%zu", size_ptr); // No & here, since size_ptr is a pointer
list = (double *)malloc(*size_ptr * sizeof(*list));
for (c = 0; c < *size_ptr; ++c)
scanf("%lf", &list[c]);
return list;
}
void print_list(const double list[], size_t list_size)
{
size_t c;
for (c = 0; c < list_size; ++c)
printf("%f\n", list[c]);
}
/*
* Sort list using selection sort algorithm.
*/
void sort_list(double list[], size_t list_size)
{
size_t start,
low,
c;
double temp;
for (start = 0; start < list_size - 1; ++start)
{
/* Find lowest element */
low = start;
for (c = start + 1; c < list_size; ++c)
if ( list[c] < list[low] )
low = c;
/* Swap first and lowest */
temp = list[start];
list[start] = list[low];
list[low] = temp;
}
}
shell-prompt: ./selsort
3
6.0
2.1
9.4
2.100000
6.000000
9.400000
And the Fortran implemtation:
!-----------------------------------------------------------------------
! Description:
! Usage: sort input-file output-file
!
! Sort a list of real numbers in input-file, placing the results
! in output-file. Both input and output files contain one
! number per line.
!
! Arguments:
! input-file: file to be sorted
! output-file: file to receive the sorted list
!
! Modification history:
! Date Name Modification
! Apr 2010 J Bacon Start.
!-----------------------------------------------------------------------
module constants
! Global Constants
real(8), parameter :: &
PI = 3.1415926535897932d0, &
E = 2.7182818284590452d0, &
TOLERANCE = 0.00000000001d0
end module constants
program selection_sort
! Import stuff from constants module
use constants
use ISO_FORTRAN_ENV
! Disable implicit declarations (i-n rule)
implicit none
! Local variables
integer :: list_size, allocate_status
real(8), allocatable :: list(:)
! Get size of list
read *, list_size
! Allocate array for list
allocate(list(1:list_size), stat=allocate_status)
if ( allocate_status /= 0 ) then
print *, 'Error: Could not allocate array of size ', list_size
stop
endif
! Read list
call read_list(list, list_size)
! Sort list
call sort_list(list, list_size)
! Output list
call print_list(list, list_size)
end program
!-----------------------------------------------------------------------
! Description:
! Read a list of real numbers from the standard input to
! the array list. The input file contains one number per line.
!
! Arguments:
! list: Array to contain the list
! list_size: size of the list and the array list
!
! Modification history:
! Date Name Modification
! Apr 2010 J Bacon Start
!-----------------------------------------------------------------------
subroutine read_list(list, list_size)
! Import stuff from constants module
use constants
! Disable implicit declarations (i-n rule)
implicit none
! Dummy variables
integer, intent(in) :: list_size
real(8), intent(out) :: list(1:list_size)
! Local variables
integer :: i
do i = 1, list_size
read *, list(i)
enddo
end subroutine
!-----------------------------------------------------------------------
! Description:
! Print the list of real numbers contained in the array list
! to a file, one number per line.
!
! Arguments:
! filename: Name of the file to store the list in
! list: Array containing the list
! list_size: Size of the list and the array
!
! Modification history:
! Date Name Modification
! Apr 2010 J Bacon Start.
!-----------------------------------------------------------------------
subroutine print_list(list, list_size)
! Disable implicit declarations (i-n rule)
implicit none
! Dummy variables
integer, intent(in) :: list_size
real(8), intent(in) :: list(1:list_size)
! Local variables
integer :: i
do i = 1, list_size
print *, list(i)
enddo
end subroutine
!-----------------------------------------------------------------------
! Description:
! Sort the list of numbers contained in the array list.
!
! Arguments:
! list: Array containing the numbers
! list_size: Size of the list and the array
!
! Modification history:
! Date Name Modification
! Apr 2010 J Bacon Start.
!-----------------------------------------------------------------------
subroutine sort_list(list, list_size)
! Import stuff from constants module
use constants
! Disable implicit declarations (i-n rule)
implicit none
! Dummy variables
integer, intent(in) :: list_size
real(8), intent(inout) :: list(1:list_size)
! Local variables
logical :: sorted
integer :: c, low, start
real(8) :: temp
do start = 1, list_size
! Find low
low = start
do c = start+1, list_size
if ( list(c) < list(low) ) then
low = c
endif
enddo
! Swap with first
temp = list(low)
list(low) = list(start)
list(start) = temp
enddo
end subroutine