/**************************************
This program simply reads 10 names from
the file names.txt and prints them out
in alphabetical order by last name, with
ties broken by first name.
**************************************/
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

/**************************************
 ** PROTOTYPES
 **************************************/
void selectionsort(string** A, int N);
bool comp(string* a, string* b);
int indexOfMax(string** A, int N);
void swap(string* &a, string* &b);

/**************************************
 ** MAIN FUNCTION
 **************************************/
int main()
{
  // Open file names.txt containing 10 names
  ifstream fin("names.txt");

  // Create and populate 2D array of 10 names
  // names[i][0] is first name
  // names[i][1] is last name
  int N = 10;
  string **names = new string*[N];
  for(int i = 0; i < N; i++)
    names[i] = new string[2];
  for(int i = 0; i < N; i++)
    fin >> names[i][0] >> names[i][1];

  // Sort!
  selectionsort(names,N);

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

  return 0;
}

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

bool comp(string* a, string* b)
{
  return a[1] < b[1] || a[1] == b[1] && a[0] < b[0];
}

int indexOfMax(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[indexOfMax(A,length)],A[length-1]);
}