/* ========================================================================== */
/*   sort.c                                                                   */
/*   (c) March 22, 2017 K. J. Rock                                            */
/*                                                                            */
/*   Sort an array in place  then                                             */
/*   sort a linked list                                                       */
/* ========================================================================== */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct db           		// create database structure of employee data
	{
	int id;
	int age;
	float salary;
	};

int main()
	{
	int age = 0;      	// for finding the average age of the employees
   int count = 19;   	// define the number of employees for ease of change
	float salary = 0;		// for payroll
   struct db temp;		// temporary swap storage

   db employee[count];  // create a new database array called employee

   srand((unsigned) time(NULL));		// randomize by seeding from time

	// instantiate founder's info
	employee[0].id = 42;   				// ultimate answer
   employee[0].age = rand() % 40 + 20;       // minimum age is 20
   employee[0].salary = 25080.15;

	// instantiate the rest of the crew
	for (int i=1; i<count; i++)
		{
      employee[i].id = i;
   	employee[i].age = rand() % 40 + 20;  	// no employees under 20
   	employee[i].salary = (float) (rand() % 40000 + 20000);
		}

	// scan through array of structures in its unsorted state
	for (int i=0; i<count; i++)
		{
		printf("%2d year old employee #%2d earns %6.2f \n", employee[i].age, employee[i].id, employee[i].salary);
		}

   //////////////////////////////////////////////// start of sort routine /////
	// Inline selection sort routine using age as the sort criterion
	// find the smallest element and put it in the lowest position
	// then advance the position through the entire array
	for (int q = 0; q < count-1; q++)
		{
		// find the min element in the unsorted array employee[j .. count-1]
		int pMin = q;  	// assume the min is the first element

		// test against elements after j to find the smallest
		for (int p = q+1; p < count; p++)
			{
			// if this element is less, then it is the new minimum
			if (employee[p].age < employee[pMin].age)   // sort by employee age
				{
				pMin = p;  // found new minimum; remember its index
				}          // or more accurately: mind your p's and q's :)
			}

		// the swap routine is messy because of the shallow copy of =
		// you truly need to move each piece of data for each record
		// it gets tedious to write and runs slowly.
		if(pMin != q)
			{
			// temp = employee[q];   need a temp variable to swap two records
	      temp.id = employee[q].id;
	      temp.age = employee[q].age;
	      temp.salary = employee[q].salary;

			//employee[q] = employee[pMin];
	      employee[q].id = employee[pMin].id;
	      employee[q].age = employee[pMin].age;
	      employee[q].salary = employee[pMin].salary;

			//employee[pMin] = temp;
	      employee[pMin].id = temp.id;
	      employee[pMin].age = temp.age;
	      employee[pMin].salary = temp.salary;
			}
		} //////////////////////////////////////////////// end of sort routine

   // scan through array of structures    after age sort
	printf("\n");   // add whitespace for clarity
	for (int i=0; i<count; i++)
		{
		printf("%2d year old emp #%2d earns %6.2f \n", employee[i].age, employee[i].id, employee[i].salary);
      age += employee[i].age;   // store a rolling sum of the age of the employees
		}
	printf("\nThe average age of employees is %2d\n", age / count);  // integer divide estimate
	// since I am dividing an integer by an integer there will be a rounding error
	// thus this is simply an estimated age.  I could cast both age and count
	// as floats to correct for this but that looks messy and this is just an
	// example app.

   //////////////////////////////////////////////// start of sort routine
	// run a second sort with salary as the sort criterion
	// advance the position through the entire array
	for (int q = 0; q < count-1; q++)
		{
  		// find the min element in the unsorted array employee[j .. count-1]
		int pMin = q;  	// assume the min is the first element

		// test against elements after j to find the smallest
		for (int p = q+1; p < count; p++)
			{
			// if this element is less, then it is the new minimum
			if (employee[p].salary < employee[pMin].salary)   // sort by employee age
				{
				pMin = p;  // found new minimum; remember its index
				}
			}

		if(pMin != q)
			{	// swap(employee[j], employee[pMin]);    // shallow copy problem
			// temp = employee[j];
	      temp.id = employee[q].id;
	      temp.age = employee[q].age;
	      temp.salary = employee[q].salary;

			//employee[j] = employee[pMin];
	      employee[q].id = employee[pMin].id;
	      employee[q].age = employee[pMin].age;
	      employee[q].salary = employee[pMin].salary;

			//employee[pMin] = temp;
	      employee[pMin].id = temp.id;
	      employee[pMin].age = temp.age;
	      employee[pMin].salary = temp.salary;
			}
		}  //////////////////////////////////////////////// end of sort routine

   // scan through array of structures    after salary sort
	printf("\n");
	for (int i=0; i<count; i++)
		{
		printf("%2d year old emp #%2d earns %6.2f \n", employee[i].age, employee[i].id, employee[i].salary);
		salary += employee[i].salary;
		}
	printf("\nThe average pay is $%6.2f\n", salary / count);
	printf("The company payroll is $%8.2f\n\n", salary);
	}