Sorting and Searching Arrays

[Suar]

I was given a code and was asked to explain certain things, but I find it rather confusing.

So here's the code:

#include <iostream>
#include <fstream>
#include <cstdlib>




using std::cin; 
using std::cout; 
using std::endl; 
using std::fstream;
using std::ios;
using std::string;




const int MAX_SCORES = 100;
int read (string filename, int finalExams[], int maxSize); 
void write (string filename, ios::openmode mode, string description, const int finalExams[], int numberOfExams);
int descendingBubbleSortV1 (int finalExams[], int numberOfExams);
int descendingBubbleSortV2 (int finalExams[], int numberOfExams);
int descendingBubbleSortV3 (int finalExams[], int numberOfExams);
int unorderedLinearSearch (int searchValue, const int finalExams[], int numberOfExams);
int binarySearch (int searchValue, const int finalExams[], int numberOfExams);



int main()
{

    int finalExams[MAX_SCORES];
    
    int numberOfExams = read ("dataInLab.txt", finalExams, MAX_SCORES); 

    cout << "number of compares: " << descendingBubbleSortV1(finalExams, numberOfExams) << endl;
         
    write ("outputInLab.txt", ios::out|ios::app, "post V1 sort", finalExams, numberOfExams);


    write ("outputInLab.txt", ios::out, "scores as read", finalExams, numberOfExams);
    
    numberOfExams = read ("dataInLab.txt", finalExams, MAX_SCORES);
    cout << "number of compares: " 
         << descendingBubbleSortV2(finalExams, numberOfExams) << endl;

    write ("outputInLab.txt", ios::out|ios::app, "post V2 sort", finalExams,                     numberOfExams);
    
    numberOfExams = read ("dataInLab.txt", finalExams, MAX_SCORES);
    cout << "number of compares: " 
         << descendingBubbleSortV3(finalExams, numberOfExams) << endl;

    write ("outputInLab.txt", ios::out|ios::app, "post V3 sort", finalExams,                     numberOfExams);
    
    numberOfExams = read("dataInLab.txt", finalExams, MAX_SCORES);




   int searchScore;

   cout << "Enter score for searching: ";
   cin >> searchScore;

   int location = unorderedLinearSearch (searchScore, finalExams, numberOfExams);

   cout << "unordered linear search results for " << searchScore << endl;

   if (location >= 0) 
   {
      cout << "score " << searchScore << " found in array location ["
           << location << "]\n";
   }

   else 
     cout << "score " << searchScore << " not found by libear search\n";
     
   descendingBubbleSortV3 (finalExams, numberOfExams);

   for(int i = 0; i<numberOfExams; i++){
       cout << finalExams[i] << endl;
   }
   
   location = binarySearch (searchScore, finalExams, numberOfExams);
   
   cout << "binary search results for " << searchScore << endl;
   
   if (location >= 0)
   {
      cout << "score " << searchScore << " found in array location [" 
           << location << "]\n";
   }
   else
      cout << "score " << searchScore << " not found by binary search\n";

   return 0;
} 


int read (string filename, int finalExams[], int maxSize){ 

    fstream infile (filename.c_str(),ios::in);
    if (!infile){ 
    
       cout << "Unable to open " << filename << " file. Exiting...\n"; exit(1); 
    }


    int numberOfExams = 0; 

    while (numberOfExams < maxSize && infile >> finalExams[numberOfExams]) { 
    
          numberOfExams++; 
    } 

    infile.close (); 
    
    return numberOfExams; 
} 

void write (string filename, ios::openmode mode, string description, const int finalExams[], int numberOfExams) { 

   fstream outfile (filename.c_str(), mode); 
   
   outfile << description << endl; 

   for (int i = 0; i <= numberOfExams-1; i++){
   
       outfile << i << " " << finalExams[i] << "\n";
   } 
   
   outfile << "\n"; outfile.close ();  
}

int descendingBubbleSortV1 (int finalExams[], int numberOfExams) {

    int compares = 0;
    
    for (int pair = 0; pair <= numberOfExams - 2; pair++) {
        
        compares++;
    
        if (finalExams[pair] < finalExams[pair + 1]) {
        
           int temp             = finalExams[pair];
           finalExams[pair]     = finalExams[pair + 1];
           finalExams[pair + 1] = temp;
        }
    }
    
    return compares;
}

int descendingBubbleSortV2 (int finalExams[], int numberOfExams)
{
   int compares = 0;

   for (int sink = 0; sink <= numberOfExams -2; sink++) 
   {
    for (int pair = 0; pair <= numberOfExams - 2; pair++) 
    {
       compares++;
    
       if (finalExams[pair] < finalExams[pair + 1]) 
       {
           int temp = finalExams[pair];
           finalExams[pair] = finalExams[pair + 1];
           finalExams[pair + 1] = temp;
       }

    }

   }
   
   return compares;
}

int descendingBubbleSortV3 (int finalExams[], int numberOfExams)
{
   int sink     = 0;
   int compares = 0;
   bool swapOccured;

do {
   swapOccured = false;
   
   for (int pair = 0; pair <= numberOfExams - 2 - sink; pair++) 
   {
        compares++;
       
        if (finalExams[pair] < finalExams[pair + 1]) 
        { 
            swapOccured = true;
            int temp = finalExams[pair];
            finalExams[pair] = finalExams[pair + 1];
            finalExams[pair + 1] = temp;
        }
   }
    sink++;

   }while (swapOccured);

 return compares;
}

int unorderedLinearSearch (int searchValue, const int finalExams[], int numberOfExams)
{
    int location = -1;
    bool found = false;
    
    for (int score = 0; score <= numberOfExams - 1 && ! found; score++) 
    {
       if (searchValue == finalExams[score]) 
       {
       location = score;
       found = true;
       }

    }
    return location;
}

int binarySearch (int searchValue, const int finalExams[], int numberOfExams)
{
    int mid;
    int left = 0;
    int right  = numberOfExams - 1;
    int location = -1;
    bool found = false;
    
    while (left < right && ! found)
    {
        mid = (left + right) / 2;
      
        if (searchValue > finalExams[mid])
           right = mid - 1;
        else if (searchValue<finalExams[mid])
           left = mid + 1;
        else 
           found = true;
    }
      
    if (found) 
    {
        location = mid;
    }
    
    
    
    return location;
}

First question: Note that the exam scores are read from the file into the array again so that this version of the sort starts under the same conditions. Execute the program and verify that the number of comparisons has indeed dropped. And demonstrate it (explain why)

Second question: Execute the program and verify that the number of comparisons has dropped further still. Demonstrate your finished in-lab program.

Third question: Execute the program and verify that the search works correctly for scores in the data and not in the data. Repeat the search for 80 and note its location reported by the program. Demonstrate one successful search and one unsuccessful search. Explain why the program reports a different location for the exam score 80.