Selection Sort for Multidimensional Array

[derik001]

Below I have a program that sorts a multidimensional array. The program first sorts the department number, then sorts the the employee number within each department (the monthly pay follows the employee).

The department works fine, but for some of the employee values, my numbers get mixed up between departments. Not all, but some, and I can't figure out why.

#include<iostream>
#include<iomanip>

using namespace std;

// Function sortem()
void sortem(int array[][3], int col, int start, int stop)
{
   int row,                 // The row I'm in
       smallestSubscript,   // Smallest subscript found when sorting through the loop
       smallestValue,       // Smallest value found in that subscript
       smallestSubscript2,  // Same as above, used for payroll
       smallestValue2;      // Same as above, used for payroll

   // I took the easy way out

   // If you're in the department column, sort in ascending order
   if (col == 0)
   {
   for(row = start; row < (stop - 1); row++)
   {
      smallestSubscript = row;
      smallestValue = array[row][0];

        for (int index = row + 1; index < stop; index++)
        {
                if (array[index][0] < smallestValue)
                {
                    smallestValue = array[index][0]; 
                    smallestSubscript = index;
                }
        }
        array[smallestSubscript][0] = array[row][0];
        array[row][0] = smallestValue;
   }
   }

   /* If you're in the employee column, sort in ascending order (the main function takes care of sorting within the department),
      and also swap out the payroll in column 3 */
   if (col == 1)
   {
   for(row = start; row < (stop - 1); row++)
   {
      smallestSubscript = row;
      smallestSubscript2 = row;
      smallestValue = array[row][1];
      smallestValue2 = array[row][2];

        for (int index = row + 1; index < stop; index++)
        {
                if (array[index][1] < smallestValue)
                {
                    smallestValue = array[index][1];
                    smallestValue2 = array[index][2]; 
                    smallestSubscript = index;
                    smallestSubscript2 = index;
                }
        }
        array[smallestSubscript][1] = array[row][1];
        array[smallestSubscript2][2] = array[row][2];
        array[row][1] = smallestValue;
        array[row][2] = smallestValue2;
   }
   }
}

// Main function
int main()
{
   int keyColumn, rowStart, rowEnd;

   // departement, employee, and payroll data
   int array[16][3] = {{2, 5, 1050},
                      {5, 17, 1200},
                      {3, 12, 1225},
                      {2, 23, 1300},
                      {3, 6, 1140},
                      {3, 3, 1110},
                      {2, 4, 1420},
                      {2, 1, 1360},
                      {5, 14, 1225},
                      {5, 11, 1380},
                      {5, 10, 1410},
                      {2, 2, 1565},
                      {3, 8, 1445},
                      {5, 7, 1387},
                      {3, 9, 1128},
                      {2, 16, 1488}};

//print array
cout << "The unsorted array\n\n";
cout << right << setw(11) << "Department" << setw(13) << "Employee" << setw(16) << "Monthly Pay\n";
cout << setw(11) << "----------" << setw(13) << "--------" << setw(16) << "-----------\n";
for(int i = 0; i < 16; i++)
{
    cout << left << " " << setw(15) << array[i][0] << setw(12) << array[i][1] << setw(15) << array[i][2] << endl;
}
cout << endl;
system("pause");
cout << "\n\n";

// Sort the departments into ascending order.
keyColumn = 0; // This is the column you are in
rowStart = 0;  // What row to start with
rowEnd = 16;   // What row to end with

sortem(array, keyColumn, rowStart, rowEnd); 

// Sort employees into ascending order
rowStart = 0;
keyColumn = 1;

do
{
  rowEnd = rowStart; // find last row for this dept. number
  while( array[rowEnd][0] == array[rowStart][0] )         
    rowEnd++; 

  //Now sort on employee number for this department    
  sortem(array, keyColumn, rowStart, rowEnd);
  rowStart = rowEnd;
} while( array[rowStart][0] >= 0 );//keep going til last record         

//Finally, print the sorted table
cout << "The array sorted via a selection sort\n\n";
cout << right << setw(11) << "Department" << setw(13) << "Employee" << setw(16) << "Monthly Pay\n";
cout << setw(11) << "----------" << setw(13) << "--------" << setw(16) << "-----------\n";
for(int i = 0; i < 16; i++)
{
    cout << left << " " << setw(15) << array[i][0] << setw(12) << array[i][1] << setw(15) << array[i][2] << endl;
}
cout << endl;
system("pause");
}

Any help would be highly appreciated.

[Ashden]

As i see it, you can only sort two out of three columns. I tried a bubble sort on your data, and practically, you can't sort the third one. Think of it this way:

1. You sort the Employees
2. You sort the Department (The Employees stay sorted, because this is a grouping on Departments)
3. Now, if you try and sort on Pay, you'll break the sort on the Department and Employees, because the Pay doesn't (logically) have a connection with the Department or Employees.

So, you can sort on Department, then choose whether to sort on Employees or Pay.
Here's my shot at Department/Employees:

#include <cstdlib>
#include <iostream>
#include <iomanip>

using namespace std;
void bubble_sort (int array[][3], int col)
{
     int sorted, i, j, aux[3];
     do
     {
         sorted=1;
         for (i=1; i<16; i++)
         {
             if (array[i][col]<array[i-1][col])
             {
                for (j=0; j<3; j++) aux[j]=array[i][j];
                for (j=0; j<3; j++) array[i][j]=array[i-1][j];
                for (j=0; j<3; j++) array[i-1][j]=aux[j];
                sorted=0;    
             }
         }
     } while (sorted==0);
}

int main(int argc, char *argv[])
{
    int array[16][3] = {{2, 5, 1050},
                      {5, 17, 1200},
                      {3, 12, 1225},
                      {2, 23, 1300},
                      {3, 6, 1140},
                      {3, 3, 1110},
                      {2, 4, 1420},
                      {2, 1, 1360},
                      {5, 14, 1225},
                      {5, 11, 1380},
                      {5, 10, 1410},
                      {2, 2, 1565},
                      {3, 8, 1445},
                      {5, 7, 1387},
                      {3, 9, 1128},
                      {2, 16, 1488}};
    cout << "The unsorted array\n\n";
    cout << right << setw(11) << "Department" << setw(13) << "Employee" << setw(16) << "Monthly Pay\n";
    cout << setw(11) << "----------" << setw(13) << "--------" << setw(16) << "-----------\n";
    for(int i = 0; i < 16; i++)
    {
    cout << left << " " << setw(15) << array[i][0] << setw(12) << array[i][1] << setw(15) << array[i][2] << endl;
    }
    cout << endl;
    system("pause");
    cout << "\n\n";
    bubble_sort(array, 1);
    bubble_sort(array, 0);
    cout << "The array sorted via a selection sort\n\n";
    cout << right << setw(11) << "Department" << setw(13) << "Employee" << setw(16) << "Monthly Pay\n";
    cout << setw(11) << "----------" << setw(13) << "--------" << setw(16) << "-----------\n";
    for(int i = 0; i < 16; i++)
    {
            cout << left << " " << setw(15) << array[i][0] << setw(12) << array[i][1] << setw(15) << array[i][2] << endl;
    }
    cout << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

And the output:

 Department     Employee    Monthly Pay
 ----------     --------    -----------
 2              1           1360
 2              2           1565
 2              4           1420
 2              5           1050
 2              16          1488
 2              23          1300
 3              3           1110
 3              6           1140
 3              8           1445
 3              9           1128
 3              12          1225
 5              7           1387
 5              10          1410
 5              11          1380
 5              14          1225
 5              17          1200

You would be able to sort all three columns if your employees are paid according to their ID (the first employee to have the lowest pay, and the last to have the highest pay, in order).

[herbert1910]

derik001, if you print out after the first column sort, you will notice the middle and last column didn't change.

each time you move a department number up or down in the list, you have to move the employee number and payroll data along with it.

i don't know how you missed that. you maintained the associations between employee and pay while sorting the middle column. i guess the right paycheck is the most important part! ha ha.

[derik001]

You're right! Thanks for the help guys. I got it figured out.