Sorting.cpp

/*-------------------------------------------------------------------------+
|     Name:  Jerome Richards                                               |
|   Course:  CNS-2400 F01                                                  |
|                                                                          |
|  Project:  Sorting - Insertion Sort, Shell Sort, and Quick Sort          |
|     File:  Sorting.cpp                                                   |
|                                                                          |
| Compare the performance of the three sorting techniques                  |
+-------------------------------------------------------------------------*/
#include <string>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <time.h>

#include "List.h"

using namespace std;

enum sortTYPE { INSERTION, SHELL, QUICK };

struct sortINFO
{
   clock_t  _elapsedClock;
   clock_t  _elapsedTime;
   string   _outFile;
};

struct procINFO
{
   int        _fileNum;
   int        _numItems;

   sortINFO   _sorts[ 3 ];
};

void dispPrologue();

bool openFile( ifstream& inFile );
bool writeFile( string& fileName, int aData[] );
bool readData( ifstream& inFile, int& tmpData );

bool writeSorted( string fileName, SortedList<int>* tmpList );
void dispStats( procINFO tmpStats[], int max );


int main( int argc, char* argv[] )
{
   ifstream          inFile;
   int               tmpData;
   List<int>*        dataList;
   SortedList<int>*  sortedList;

   const int         maxFILES = 10;
   int               ptr = 0;
   procINFO          procStats[ maxFILES ];

   clock_t           start, end;
   stringstream      charNum;

   dispPrologue();

   while( openFile( inFile )  && ptr < maxFILES )
   {
      dataList = new(nothrow) List<int>();

      if( ! dataList )
      {
         cout << "ERROR: cannot instantiate the list. Press ENTER to end program.";
         cin.get();
         exit( 1 );
      }

      cout << "Processing file. . .";

      procStats[ ptr ]._fileNum = ptr+1;
      procStats[ ptr ]._numItems = 0;

      charNum.str( "" );
      charNum << procStats[ ptr ]._fileNum;

      while( ! inFile.eof() )
      {
         if( readData( inFile, tmpData ) )
         {
            procStats[ ptr ]._numItems++;
            dataList->insert( tmpData );
         }
      }

      cout << "done." << endl;
      cout << "Total items read: " << procStats[ ptr ]._numItems << endl << endl;

      cout << "Sorting the list with Insertion Sort. . .";

         // create a SortedList object with the copy constructor to start with initial items
         sortedList = new(nothrow) SortedList<int>( dataList );

            // sort the list using the insertionSort method
            start = clock();
               sortedList->insertionSort();
            end = clock();

            procStats[ ptr ]._sorts[ INSERTION ]._elapsedClock = end - start;
            procStats[ ptr ]._sorts[ INSERTION ]._elapsedTime = (end - start) / CLK_TCK;
            procStats[ ptr ]._sorts[ INSERTION ]._outFile = "I" + charNum.str() + ".txt";

            cout << "writing output file. . .";
            writeSorted( procStats[ ptr ]._sorts[ INSERTION ]._outFile, sortedList );

         delete sortedList;
         sortedList = NULL;

      cout << "done." << endl << endl;

      cout << "Sorting the list with Shell Sort. . .";

         // create a SortedList object with the copy constructor to start with initial items
         sortedList = new(nothrow) SortedList<int>( dataList );

            // sort the list using the shellSort method
            start = clock();
               sortedList->shellSort();
            end = clock();

            procStats[ ptr ]._sorts[ SHELL ]._elapsedClock = end - start;
            procStats[ ptr ]._sorts[ SHELL ]._elapsedTime = (end - start) / CLK_TCK;
            procStats[ ptr ]._sorts[ SHELL ]._outFile = "S" + charNum.str() + ".txt";

            cout << "writing output file. . .";
            writeSorted( procStats[ ptr ]._sorts[ SHELL ]._outFile, sortedList );

         delete sortedList;
         sortedList = NULL;

      cout << "done." << endl << endl;

      cout << "Sorting the list with Quick Sort. . .";

         // create a SortedList object with the copy constructor to start with initial items
         sortedList = new(nothrow) SortedList<int>( dataList );

            // sort the list using the quickSort method
            start = clock();
               sortedList->quickSort();
            end = clock();

            procStats[ ptr ]._sorts[ QUICK ]._elapsedClock = end - start;
            procStats[ ptr ]._sorts[ QUICK ]._elapsedTime = (end - start) / CLK_TCK;
            procStats[ ptr ]._sorts[ QUICK ]._outFile = "Q" + charNum.str() + ".txt";

            cout << "writing output file. . .";
            writeSorted( procStats[ ptr ]._sorts[ QUICK ]._outFile, sortedList );

         delete sortedList;
         sortedList = NULL;

      cout << "done." << endl << endl;

      // release the source list (original unsorted items)
      delete dataList;
      dataList = NULL;

      inFile.close();
      inFile.clear();

      // keep track of how many files we've processed
      ptr++;
   }

   // display the statistics if any files were processed
   if( ptr )
      dispStats( procStats, ptr );

   return 0;
}


void dispStats( procINFO tmpStats[], int max )
{
   cout << endl << endl;

   cout << "File#     Items      Sort       Clock     Time     outFile" << endl;
   cout << "-----   --------   ---------   -------   -------   -------" << endl;
   //        99     99999999   Insertion   9999999   999.999   I10.txt

   for( int x = 0; x < max; x++ )
   {
      cout << " " << setw(2) << tmpStats[x]._fileNum << "     ";
      cout << setw(8) << tmpStats[x]._numItems << "   ";

      cout << "Insertion" << "   ";
      cout << setw(7) << tmpStats[x]._sorts[ INSERTION ]._elapsedClock << "   ";
      cout << setw(7) << tmpStats[x]._sorts[ INSERTION ]._elapsedTime  << "   ";
      cout << tmpStats[ x ]._sorts[ INSERTION ]._outFile << endl;

      cout << "                   ";
      cout << "Shell    " << "   ";
      cout << setw(7) << tmpStats[x]._sorts[ SHELL ]._elapsedClock << "   ";
      cout << setw(7) << tmpStats[x]._sorts[ SHELL ]._elapsedTime  << "   ";
      cout << tmpStats[ x ]._sorts[ SHELL ]._outFile << endl;

      cout << "                   ";
      cout << "Quick    " << "   ";
      cout << setw(7) << tmpStats[x]._sorts[ QUICK ]._elapsedClock << "   ";
      cout << setw(7) << tmpStats[x]._sorts[ QUICK ]._elapsedTime  << "   ";
      cout << tmpStats[ x ]._sorts[ QUICK ]._outFile << endl << endl;
   }

   cout << endl << endl << "Press ENTER to continue...";
   cin.get();
}


bool writeSorted( string fileName, SortedList<int>* tmpList )
{
   bool     lOkay = false;
   ofstream outFile( fileName.c_str(), ios_base::out );

   int pos = 0;
   int tmpData;
   
   while( tmpList->retrieve( pos, tmpData ) )
   {
      outFile << tmpData << endl;
      pos++;
   }

   outFile.close();
   lOkay = true;

   return lOkay;
}


bool readData( ifstream& inFile, int& tmpData )
{
   bool lOkay = false;

   inFile >> tmpData;
   lOkay = ! inFile.fail();

   return lOkay;
}


bool openFile( ifstream& inFile )
{
   bool lOpen = false;
   string fileName;

   while( ! lOpen )
   {
      cout << "Enter file name: (blank to exit): ";
      getline( cin, fileName );

      if( ! fileName.length() )
      {
         cout << endl << endl << "Press ENTER to exit program.";
         cin.get();
         return false;
      }

      inFile.open( fileName.c_str() );

      if( !( lOpen = inFile.good() ) )
      {
         cout << endl << "ERROR: could not open data file " << fileName << endl;
         inFile.clear();
      }
   }

   return lOpen;
}


void dispPrologue()
{
   system( "cls" );

   cout << "   Name:  Jerome Richards"   << endl;
   cout << " Course:  CNS-2400 F01"      << endl;
   cout << "Project:  Sorting (prog-05)" << endl;

   cout << endl << endl;
}