Question

In this project you will implement and experiment with three different sorting algorithms: Insertion Sort, Selection sort and Bubble Sort. The objective of this project is to understand the relation between the theoretical asymptotic complexities (Big-O) computed in class and the actual running times for different kinds of input.

The enclosed source file main.cpp contains a program that reads two inputs: a letter specifying which sorting algorithm to use (I for InsertionSort , S for SelectionSort and B for BubbleSort), and an integer specifying the input size. For example, if the input parameters are I 1000, the program will run InsertionSort with an input size 1000.

The first step in this project is writing the missing code for the empty functions in the source file main.cpp. The empty functions that you need to write are:

InsertionSort()

SelectionSort()

BubbleSort()

Swap()

After writing the missing code, add your first name to the beginning of every output line. So, if your first name is Ibrahim, the “Sorted Data:” line should appear as

“Ibrahim: Sorted Data:”

Now you are ready to compile your code and build the executable. Before you do the production run with the large input sizes listed below, you will need to do three test runs (one for InsertionSort , one for SelectionSort and one for BubbleSort) using a small input size of 20 to verify that your program generates the input data as desired and produces correctly sorted output. Set the OUTPUT_DATA to true to allow printing outputs. Take screenshots of the three tests.

Once you get correct input and output for the test run, Set the OUTPUT_DATA to false to avoid printing output for large size arrays. Rebuild the code for the production run. It is highly recommended that you enable compiler optimizations in the production run by going to “Build” then “Set Active Configuration” then selecting Release.

In the production run, you should run each of InsertionSort, SelectionSort and BubbleSort with the following input sizes:

10000

100000

200000

Submit your work on elearning only using the link dedicated “submit assignment 1”, Your submission should include the following all in one zipped file:

1. The source code for the functions that you wrote. Do not submit any code that is given to you.
2. A printout of the outputs for the test runs with an input size of 20 elements. The printout should show correct input and output and your first name should appear in the beginning of each line in the output.
3. Three tables summarizing the results (the running times in ms): one table for each sorting algorithm.
4. A report discussing the results and how they relate to the asymptotic complexities (Big O) studied in class and to the properties of each sorting algorithm. Your report should consist of 1-2 pages in which you compare the different algorithms against each other and the different input types against each other. This is a very important part of the assignment that each student should write in his/her own words

Grading Criteria:

Completion of Missing Code	20%	ABET outcomes: A, I, C
Running Time Tables (3 tables)	30%	ABET outcomes: A, I, C
Analysis and Report	50%	ABET outcomes: B

#include <stdlib.h>
#include <time.h>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 1000000;

// Set this to true if you wish the arrays to be printed.
const bool OUTPUT_DATA = false;

void ReadInput(string& sortAlg, int& size);

void GenerateSortedData(int data[], int size);
void GenerateReverselySortedData(int data[], int size);
void GenerateRandomData(int data[], int size);
void GenerateNearlySortedData(int data[], int size);

void Sort(int data[], int size, string sortAlg, char* dataType);

void SelectionSort(int data[], int size);
void BubbleSort(int data[], int size);
void InsertionSort(int data[], int size);
void SelectionSort2(int data[], int size);

void Swap(int &x, int &y);

bool IsSorted(int data[], int size);
void printData(int data[], int size, string title);

int main(void)
{
   int size;
   string sortAlg;
   ReadInput(sortAlg, size);

   int * data = new int[size];

   GenerateSortedData(data, size);
   Sort(data, size, sortAlg, "Sorted Data");

   GenerateReverselySortedData(data, size);
   Sort(data, size, sortAlg, "Reversely Sorted Data");

   GenerateRandomData(data, size);
   Sort(data, size, sortAlg, "Random Data");

   GenerateNearlySortedData(data, size);
   Sort(data, size, sortAlg, "Nearly Sorted Data");

   cout << "\nProgram Completed Successfully." << endl;;

   return 0;
}
/********************************************************************/

// This function asks the user to choose the sorting algorithm and the array size
void ReadInput(string& sortAlg, int& size)
{
   cout << " I:\tInsertion Sort" << endl;
   cout << " S:\tSelection Sort" << endl;
   cout << " B:\tBubble Sort" << endl;
   cout << " 2:\tSelection Sort 2" << endl;
   cout << "Enter sorting algorithm: ";
   cin >> sortAlg;
   string sortAlgName;

   if (sortAlg == "S")
       sortAlgName = "Selection Sort";
   else if (sortAlg == "B")
       sortAlgName = "Bubble Sort";
   else if (sortAlg == "I")
       sortAlgName = "Insertion Sort";
   else if (sortAlg == "2")
       sortAlgName = "Selection Sort 2";
   else {
       cout << "\nUnrecognized sorting algorithm Code: " << sortAlg << endl;
       exit(1);
   }

   cout << "Enter input size: ";
   cin >> size;

   if (size < 1 || size > MAX_SIZE)
   {
       cout << "\nInvalid input size " << size
           << ". Size should be between 1 and " << MAX_SIZE << endl;
       exit(1);
   }

   cout << "\nSorting Algorithm: " << sortAlgName;
   cout << "\nInput Size = " << size << endl;
   cout << endl;

}
/******************************************************************************/

void GenerateSortedData(int data[], int size)
{
   int i;

   for (i = 0; i < size; i++)
       data[i] = i * 3 + 5;
}

/*****************************************************************************/

void GenerateReverselySortedData(int data[], int size)
{
   int i;

   for (i = 0; i < size; i++)
       data[i] = (size - i) * 2 + 3;

}
/*****************************************************************************/

void GenerateRandomData(int data[], int size)
{
   int i;

   for (i = 0; i < size; i++)
       data[i] = rand();
}
/*****************************************************************************/

void GenerateNearlySortedData(int data[], int size)
{
   int i;

   GenerateSortedData(data, size);

   for (i = 0; i<size; i++)
       if (i % 10 == 0)
           if (i + 1 < size)
               data[i] = data[i + 1] + 9;
}
/*****************************************************************************/

// This function performs sorting depending on the algorithm chosen by the user.
void Sort(int data[], int size, string sortAlg, char* dataType)
{

   cout << endl << dataType << ":";

   if (OUTPUT_DATA)
       printData(data, size, "Data before sorting:");

   // Sorting is about to begin ... start the timer!
   clock_t start = clock();

   if (sortAlg == "S")
       SelectionSort(data, size);
   else if (sortAlg == "B")
       BubbleSort(data, size);
   else if (sortAlg == "I")
       InsertionSort(data, size);
   else if (sortAlg == "2")
       SelectionSort2(data, size);
   else
   {
       cout << "Invalid sorting algorithm!" << endl;
       exit(1);
   }

   // Sorting has finished ... stop the timer!
   clock_t end = clock();
   double elapsed = (((double)(end - start)) / CLOCKS_PER_SEC) * 1000;

   if (OUTPUT_DATA)
       printData(data, size, "Data after sorting:");

   if (IsSorted(data, size))
       cout << "\nCorrectly sorted " << size << " elements in " << elapsed << "ms";
   else
       cout << "ERROR!: INCORRECT SORTING!" << endl;
   cout << "\n-------------------------------------------------------------\n";
}
/*****************************************************************************/

bool IsSorted(int data[], int size)
{
   int i;

   for (i = 0; i<(size - 1); i++)
   {
       if (data[i + 1] < data[i])
           return false;
   }
   return true;
}
/*****************************************************************************/

void SelectionSort(int data[], int n)
{
   // write your code here

}
/*****************************************************************************/

void BubbleSort(int data[], int size)
{
   // write your code here
}
/*****************************************************************************/

void InsertionSort(int data[], int n)
{
   // write your code here

}
/*****************************************************************************/

void SelectionSort2(int data[], int size)
{
   // write your code here
}
/*****************************************************************************/

void Swap(int &x, int &y)
{

}
/*****************************************************************************/

void printData(int data[], int size, string title) {
   int i;

   cout << endl << title << endl;
   for (i = 0; i<size; i++)
   {
       cout << data[i] << " ";
       if (i % 10 == 9 && size > 10)
           cout << endl;
   }
}

Answer 1

#include <stdlib.h>
#include <time.h>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 1000000;

// Set this to true if you wish the arrays to be printed.
const bool OUTPUT_DATA = false;

void ReadInput(string& sortAlg, int& size);

void GenerateSortedData(int data[], int size);
void GenerateReverselySortedData(int data[], int size);
void GenerateRandomData(int data[], int size);
void GenerateNearlySortedData(int data[], int size);

void Sort(int data[], int size, string sortAlg, char* dataType);

void SelectionSort(int data[], int size);
void BubbleSort(int data[], int size);
void InsertionSort(int data[], int size);
void SelectionSort2(int data[], int size);

void Swap(int &x, int &y);

bool IsSorted(int data[], int size);
void printData(int data[], int size, string title);

int main(void)
{
   int size;
   string sortAlg;
   ReadInput(sortAlg, size);

   int * data = new int[size];

   GenerateSortedData(data, size);
   Sort(data, size, sortAlg, "Sorted Data");

   GenerateReverselySortedData(data, size);
   Sort(data, size, sortAlg, "Reversely Sorted Data");

   GenerateRandomData(data, size);
   Sort(data, size, sortAlg, "Random Data");

   GenerateNearlySortedData(data, size);
   Sort(data, size, sortAlg, "Nearly Sorted Data");

   cout << "\nProgram Completed Successfully." << endl;;

   return 0;
}
/********************************************************************/

// This function asks the user to choose the sorting algorithm and the array size
void ReadInput(string& sortAlg, int& size)
{
   cout << " I:\tInsertion Sort" << endl;
   cout << " S:\tSelection Sort" << endl;
   cout << " B:\tBubble Sort" << endl;
   cout << " 2:\tSelection Sort 2" << endl;
   cout << "Enter sorting algorithm: ";
   cin >> sortAlg;
   string sortAlgName;

   if (sortAlg == "S")
       sortAlgName = "Selection Sort";
   else if (sortAlg == "B")
       sortAlgName = "Bubble Sort";
   else if (sortAlg == "I")
       sortAlgName = "Insertion Sort";
   else if (sortAlg == "2")
       sortAlgName = "Selection Sort 2";
   else {
       cout << "\nUnrecognized sorting algorithm Code: " << sortAlg << endl;
       exit(1);
   }

   cout << "Enter input size: ";
   cin >> size;

   if (size < 1 || size > MAX_SIZE)
   {
       cout << "\nInvalid input size " << size
           << ". Size should be between 1 and " << MAX_SIZE << endl;
       exit(1);
   }

   cout << "\nSorting Algorithm: " << sortAlgName;
   cout << "\nInput Size = " << size << endl;
   cout << endl;

}
/******************************************************************************/

void GenerateSortedData(int data[], int size)
{
   int i;

   for (i = 0; i < size; i++)
       data[i] = i * 3 + 5;
}

/*****************************************************************************/

void GenerateReverselySortedData(int data[], int size)
{
   int i;

   for (i = 0; i < size; i++)
       data[i] = (size - i) * 2 + 3;

}
/*****************************************************************************/

void GenerateRandomData(int data[], int size)
{
   int i;

   for (i = 0; i < size; i++)
       data[i] = rand();
}
/*****************************************************************************/

void GenerateNearlySortedData(int data[], int size)
{
   int i;

   GenerateSortedData(data, size);

   for (i = 0; i<size; i++)
       if (i % 10 == 0)
           if (i + 1 < size)
               data[i] = data[i + 1] + 9;
}
/*****************************************************************************/

// This function performs sorting depending on the algorithm chosen by the user.
void Sort(int data[], int size, string sortAlg, char* dataType)
{

   cout << endl << dataType << ":";

   if (OUTPUT_DATA)
       printData(data, size, "Data before sorting:");

   // Sorting is about to begin ... start the timer!
   clock_t start = clock();

   if (sortAlg == "S")
       SelectionSort(data, size);
   else if (sortAlg == "B")
       BubbleSort(data, size);
   else if (sortAlg == "I")
       InsertionSort(data, size);
   else if (sortAlg == "2")
       SelectionSort2(data, size);
   else
   {
       cout << "Invalid sorting algorithm!" << endl;
       exit(1);
   }

   // Sorting has finished ... stop the timer!
   clock_t end = clock();
   double elapsed = (((double)(end - start)) / CLOCKS_PER_SEC) * 1000;

   if (OUTPUT_DATA)
       printData(data, size, "Data after sorting:");

   if (IsSorted(data, size))
       cout << "\nCorrectly sorted " << size << " elements in " << elapsed << "ms";
   else
       cout << "ERROR!: INCORRECT SORTING!" << endl;
   cout << "\n-------------------------------------------------------------\n";
}
/*****************************************************************************/

bool IsSorted(int data[], int size)
{
   int i;

   for (i = 0; i<(size - 1); i++)
   {
       if (data[i + 1] < data[i])
           return false;
   }
   return true;
}
/*****************************************************************************/

void SelectionSort(int data[], int n)
{
   int small,loc,i,j;

    for(i=0;i<n;i++)
    {
        small=data[i];
        loc=i;
        for(j=i+1;j<n;j++)
        {
        if(small>data[j])
        {
            small=data[j];
            loc=j;
        }
    }
    data[loc]=data[i];
    data[i]=small;
    }
}
/*****************************************************************************/

void BubbleSort(int data[], int size)
{
   int i,j,temp;

   for(i=0;i<size;i++)
   {
    for(j=0;j<size-1;j++)
    {
        if(data[j]>data[j+1])
        {
            temp=data[j];
            data[j]=data[j+1];
            data[j+1]=temp;
        }
     }
    }
}
/*****************************************************************************/

void InsertionSort(int data[], int n)
{
   int i,j,key;

   for(j=1;j<n;j++)
    {
        key=data[j];
        i=j-1;
        while((i>=0)&&(data[i]>key))
        {
            data[i+1]=data[i];
            i=i-1;
        }
        data[i+1]=key;
    }
}
/*****************************************************************************/

void SelectionSort2(int data[], int size)
{
   int small,loc,i,j;

    for(i=0;i<size;i++)
    {
        small=data[i];
        loc=i;
        for(j=i+1;j<size;j++)
        {
        if(small>data[j])
        {
            small=data[j];
            loc=j;
        }
    }
    data[loc]=data[i];
    data[i]=small;
    }
}
/*****************************************************************************/

void Swap(int &x, int &y)
{
    int temp;
    temp= x;
    x= y;
    x = temp ;
}
/*****************************************************************************/

void printData(int data[], int size, string title) {
   int i;

   cout << endl << title << endl;
   for (i = 0; i<size; i++)
   {
       cout << data[i] << " ";
       if (i % 10 == 9 && size > 10)
           cout << endl;
   }
}