// Last updated:  Sunday 9th March 2003 A.H.D.
// Tests the selection sort.
// http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/SSort.html

#include <iostream.h>
#include <conio.h>


void sort(int a[], int number_used);
//Precondition: number_used <= declared size of the array a.
//The array elements a[0] through a[number_used - 1] have values.
//Postcondition: The values of a[0] through a[number_used - 1] have
//been rearranged so that a[0] <= a[1] <= ... <= a[number_used - 1].

void swap_values(int& v1, int& v2);
//Interchanges the values of v1 and v2.

int index_of_smallest(const int a[], int start_index, int number_used);
//Precondition: 0 <= start_index < number_used.
//Referenced array elements have values.
//Returns the index i such that a[i] is the smallest of the values
//a[start_index], a[star_index + 1], ..., a[number_used - 1].

void display(int x[ ], int size );

/***************************************************************************/

int main( )
{
	 cout << "This program sorts numbers from lowest to highest.\n";

	 int sample_array[10] = {8,6,10,2,16,4,18,14,12,20};
    int number_used = 10;

    cout << "\nOriginal array: \n\n";
    display(sample_array,number_used);
    cout << "\nSorting... \n\n";
	 sort(sample_array, number_used);

	 cout << "\nIn sorted order the numbers are:\n\n";
    display(sample_array,number_used);
	 cout << endl;
    cout << "\nPress any key to end this program\n\n";
	 getch();

	 return 0;
}

/***************************************************************************/

void sort(int a[], int number_used)
{
    int index_of_next_smallest;
    for (int index = 0; index < number_used - 1; index++)
    {//Place the correct value in a[index]:
        index_of_next_smallest =
                     index_of_smallest(a, index, number_used);
        swap_values(a[index], a[index_of_next_smallest]);
        //a[0] <= a[1] <=...<= a[index] are the smallest of the original array
        //elements. The rest of the elements are in the remaining positions.
        display(a,number_used);
    }
}

/***************************************************************************/

void display(int x[ ], int size )
{

  int i;
  for( i = 0; i < size; i++ )
     cout << x[i] << ' ';
  cout << endl;
}

/***************************************************************************/

void swap_values(int& v1, int& v2)
{
    int temp;
    temp = v1;
    v1 = v2;
    v2 = temp;
}

/***************************************************************************/

int index_of_smallest(const int a[], int start_index, int number_used)
{
    int min = a[start_index],
        index_of_min = start_index;
    for (int index = start_index + 1; index < number_used; index++)
        if (a[index] < min)
        {
            min = a[index];
            index_of_min = index;
            //min is the smallest of a[start_index] through a[index]
        }

    return index_of_min;
}

/***************************************************************************/