#### Sorting

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:

1. Read the list
2. Sort the list
1. Find the smallest (or largest) element in the list.
2. Swap it with the first element.
3. Repeat the previous two steps starting at the next element.
4. Repeat the previous three steps until the entire list is sorted.
3. Print the sorted list

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>

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;

print_list(list, list_size);
free(list);
return EX_OK;
}

/*
*  Input list size, allocate array, and read in list.
*/

{
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>

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;

print_list(list, list_size);
free(list);
return EX_OK;
}

/*
*  Input list size, allocate array, and read in list.
*/

{
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>

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;

sort_list(list, list_size);
print_list(list, list_size);
free(list);
return EX_OK;
}

/*
*  Input list size, allocate array, and read in list.
*/

{
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

! 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

! 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
!-----------------------------------------------------------------------

! 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
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

```