/**************************************
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
 **************************************/
bool before(string* a, string* b);
void selection_sort(string** A, int N);

/**************************************
 ** 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!
  selection_sort(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 before(string* a, string* b)
{
  // if a and b are not tie (i.e., the last names are different)
  if( a[1] != b[1] )
    return a[1] < b[1];   // compare the last names
  else  // tie!!
    return a[0] < b[0];   // tie: compare the first names
}

void selection_sort(string** A, int n) {
  for (int i = 0; i < n - 1; ++i) {
    // find nexti, the index of the next element
    int nexti = i;
    for (int j = i + 1; j < n; ++j) {
      if (before(A[j], A[nexti])) {
        nexti = j;
      }
    }
    // swap A[i] and A[nexti]
    string* temp = A[i];
    A[i] = A[nexti];
    A[nexti] = temp;
  }
}