/**************************************
This program simply reads in a bunch
of strings and sorts them.  Whoopee!
**************************************/
#include <iostream>
#include <string>

using namespace std;

/**************************************
 ** PROTOTYPES
 **************************************/
void selectionsort(string *A, int N);
bool before(string a, string b);

/**************************************
 ** MAIN FUNCTION
 **************************************/
int main()
{
  // Get number of strings
  int N;
  cout << "Enter number of strings: ";
  cin >> N;

  // Create and populate array
  string *A = new string[N];
  cout << "Enter strings: ";
  for(int i = 0; i < N; i++)
    cin >> A[i];

  // Sort!
  selectionsort(A,N);

  // Print in sorted order
  for(int j = 0; j < N; j++)
    cout << A[j] << endl;

  return 0;
}

/**************************************
 ** FUNCTION DEFINITIONS
 **************************************/

bool before(string a, string b)
{
  return a < b;
}

void selectionsort(string *A, int N)
{
  for(int length = N; length > 1; length--)
  {
    // Find imax, the index of the largest
    int imax = 0, i;
    for(i = 1; i < length; i++)
      if (before(A[imax],A[i]))
	imax = i;
    // Swap A[imax] & the last element
    string temp = A[imax];
    A[imax] = A[length - 1];
    A[length - 1] = temp;
  }
}