Selection Sort
The Task
With arrays, we can sort a list of integers entered by the
user. This program uses an algorithm called "Selection Sort"
to put the numbers in increasing order.
The Program
<![CDATA[
/****************************************
** File: sort.c
** Author: Richard Chang
** Date Written: ?
** Modified by: Sue Evans
** Modification date: 2/28/04
** Section: 201 0101
** EMail: bogar@cs.umbc.edu
**
** This program sorts a list of numbers using
** an array and selection sort. This example
** is also used to introduce students to UNIX
** redirection.
*****************************************/
#include <stdio.h>
#define SENTINEL -1
/* max number of values to be sorted */
#define MAX 100
/* function prototypes */
int ReadArray (int array[], int maxSize) ;
void SelectionSort (int array[], int size) ;
int FindSmallest (int array[], int start, int stop) ;
int main ( )
{
int array[MAX], items, i ;
printf("Enter items, one per line.\n") ;
printf("End with sentinel: %d\n", SENTINEL) ;
items = ReadArray(array, MAX) ;
if (items == -1)
{
printf("Too many items!!!\n") ;
}
else
{
SelectionSort(array, items) ;
printf("\nSorted list:\n") ;
for (i = 0; i < items; i++)
{
printf("array[%d] = %d\n", i, array[i]) ;
}
}
return 0;
}
/*********************************************
** Function: SelectionSort()
**
** Selection sort selects the smallest value
** in the unsorted portion of the array and
** moves it into the current position. The
** values "swap" positions.
**
** Input: an array of ints to be sorted
** the size of the array
** Output: the array is sorted "in place"
** there is no return value
**********************************************/
void SelectionSort(int array[], int size)
{
int unsorted, smallestIndex, temp ;
for (unsorted = 0; unsorted < size;
unsorted++)
{
/* get the index of the smallest value */
/* in the unsorted part of the array */
smallestIndex =
FindSmallest(array, unsorted, size);
/* swap values */
temp = array[smallestIndex] ;
array[smallestIndex] = array[unsorted] ;
array[unsorted] = temp ;
}
}
/*********************************************
** Function: FindSmallest()
**
** FindSmallest finds the smallest integer in the
** array between the index, start, and the index,
** stop, inclusive, and returns its index.
**
** Input: an array of ints to search
** the 'start'ing and 'stop'ping indices in
** the array between which to search for
** the smallest
** Output: returns the index corresponding to
** the smallest value
**********************************************/
int FindSmallest(int array[], int start, int stop)
{
int smallestValue, smallestIndex, i ;
smallestIndex = start ;
smallestValue = array[start] ;
/* look for the smallest value in the */
/* unsorted part of the array */
for (i = start + 1 ; i < stop ; i++)
{
if (array[i] < smallestValue)
{
smallestIndex = i ;
smallestValue = array[i] ;
}
}
return (smallestIndex) ;
}
/*********************************************
** Function: ReadArray()
**
** ReadArray() gets integer values and stores
** them in the array. It also counts the number
** of values read and will return the number of
** elements stored or a -1 if too many values
** were read.
**
** Input: an array of ints in which to store values
** the size of the array
** Output: returns the number of elements stored in
** the array or returns -1 if too many
** values are read
**********************************************/
int ReadArray(int array[], int maxSize)
{
int i, value ;
i = 0 ;
/* The priming read */
scanf ("%d", &value);
while (value != SENTINEL)
{
if (i == maxSize)
{
return(-1) ;
}
array[i] = value ;
i++ ;
scanf ("%d", &value);
}
return (i) ;
}
]]>
The Sample Run
<![CDATA[
linux1[74] % a.out
Enter items, one per line.
End with sentinel: -1
10
8
6
2
7
1
3
-1
Sorted list:
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 6
a[4] = 7
a[5] = 8
a[6] = 10
linux1[75] % cat data
8
12
7
13
32
6
29
1
18
10
2
17
1
3
30
-1
linux1[76] % a.out < data
Enter items, one per line.
End with sentinel: -1
Sorted list:
a[0] = 1
a[1] = 1
a[2] = 2
a[3] = 3
a[4] = 6
a[5] = 7
a[6] = 8
a[7] = 10
a[8] = 12
a[9] = 13
a[10] = 17
a[11] = 18
a[12] = 29
a[13] = 30
a[14] = 32
linux1[77] %
]]>
Last Modified -