/**************************************
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 comp(string a, string b);
int maxindex(string *A, int N);
void swap(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 comp(string a, string b)
{
  return a < b;
}

int maxindex(string *A, int N)
{
  int imax = 0, i;
  for(i = 1; i < N; i++)
    if (comp(A[imax],A[i]))
      imax = i;
  return imax;
}

void swap(string &a, string &b)
{
  string temp = a;
  a = b;
  b = temp;
}

void selectionsort(string *A, int N)
{
  for(int length = N; length > 1; length--)
    swap(A[maxindex(A,length)],A[length-1]);
}