Question

4) Implement the Selection Sort algorithm discussed in class to sort a list of a certain size. The list is to be
implemented using a dynamic array as well as a singly linked list. You are required to compare the
performance (sorting time) for the dynamic array and singly-linked list-based implementations.

You are given the startup codes for the dynamic array and singly-linked list based implementations. You
are required to implement the Selection Sort function in each of these codes. The main function is written
for you in such a way that the code will run for different values of list sizes ranging from 1000 to 20000,
in increments of 1000. The inputs for the maximum value and number of trials are 5000 and 50 for all
cases. The codes will output the average sorting time (in milliseconds) for each of value of list size for the
two implementations.
You are then required to tabulate the average sorting times observed for the two implementations and then
plot the same in Excel. Generate one plot that displays (compares) the sorting times for both the
implementations. Use the Add Trend Line option in Excel, choose the Power function option and display
the equations and the R2 values for the two curves. The R2 values are expected to be closer to 1.0. Make
sure the two equations and the R2 values are clearly visible in your Excel plot. (Please answer in C++)

Dynamic list implementation code:

#include <iostream>
#include <ctime>
#include <ratio>
#include <chrono>
#include <time.h>
#include <stdlib.h>

using namespace std;

// implementing the dynamic List ADT using array
// operations to be implemented: read, Modify, delete, isEmpty, insert, countElements

class List{

   private:
       int *array;
       int maxSize; // useful to decide if resizing (doubling the array size) is needed
       int endOfArray;
  
   public:
       List(int size){
           array = new int[size];
           maxSize = size;
           endOfArray = -1;
       }
      
       void deleteList(){
           delete[] array;
       }
      
       bool isEmpty(){
          
           if (endOfArray == -1)
               return true;
          
           return false;
       }
      
       void resize(int s){
          
           int *tempArray = array;
          
           array = new int[s];
          
           for (int index = 0; index < min(s, endOfArray+1); index++){
               array[index] = tempArray[index];
           }
          
           maxSize = s;
          
       }
  
      
       void insert(int data){
          
           if (endOfArray == maxSize-1)
               resize(2*maxSize);
          
           array[++endOfArray] = data;
          
       }
      
      
       void insertAtIndex(int insertIndex, int data){
          
           // if the user enters an invalid insertIndex, the element is
           // appended to the array, after the current last element          
           if (insertIndex > endOfArray+1)
               insertIndex = endOfArray+1;
          
           if (endOfArray == maxSize-1)
               resize(2*maxSize);          
          
           for (int index = endOfArray; index >= insertIndex; index--)
               array[index+1] = array[index];
          
           array[insertIndex] = data;
           endOfArray++;
          
       }
      
      
       int read(int index){
           return array[index];
       }
      
       void modifyElement(int index, int data){
           array[index] = data;
       }
          
      
       void deleteElement(int deleteIndex){
          
           // shift elements one cell to the left starting from deleteIndex+1 to endOfArray-1
           // i.e., move element at deleteIndex + 1 to deleteIndex and so on
          
           for (int index = deleteIndex; index < endOfArray; index++)
               array[index] = array[index+1];
          
           endOfArray--;  
      
       }
      
       int countList(){
           int count = 0;
           for (int index = 0; index <= endOfArray; index++)
               count++;
          
           return count;
       }
      
       void print(){
          
           for (int index = 0; index <= endOfArray; index++)
               cout << array[index] << " ";
          
           cout << endl;
          
       }

};

void SelectionSort(List list){
  
// Implement the selection sorting algorithm here...
  
  
}

int main(){

   using namespace std::chrono;
  
   srand(time(NULL));
  

  
   int maxValue;
   cout << "Enter the max value: ";
   cin >> maxValue;
  
   int numTrials;
   cout << "Enter the number of trials: ";
   cin >> numTrials;

for (int listSize = 1000; listSize <= 20000; listSize += 1000){

double totalSortingTime = 0;
  
for (int trials = 1; trials <= numTrials; trials++){
  
   List integerList(1);
  
   for (int i = 0; i < listSize; i++){
      
       int value = 1 + rand() % maxValue;  
       integerList.insertAtIndex(i, value);
   }
  

  
  
   high_resolution_clock::time_point t1 = high_resolution_clock::now();
   SelectionSort(integerList);
   high_resolution_clock::time_point t2 = high_resolution_clock::now();
  
   duration<double, std::milli> sortingTime_milli = t2 - t1;
   totalSortingTime += sortingTime_milli.count();
  
   integerList.deleteList();
  
}
  
  
   cout << "Average sorting time for list size " << listSize << " is " << (totalSortingTime/numTrials) << " milli seconds " << endl;

} // list size   loop

   system("pause");
  
return 0;
}

Answer 1

If you have any doubts, please give me comment...

#include <iostream>

#include <ctime>

#include <ratio>

#include <chrono>

#include <time.h>

#include <stdlib.h>

using namespace std;

// implementing the dynamic List ADT using array

// operations to be implemented: read, Modify, delete, isEmpty, insert, countElements

class List

{

private:

    int *array;

    int maxSize; // useful to decide if resizing (doubling the array size) is needed

    int endOfArray;

public:

    List(int size)

    {

        array = new int[size];

        maxSize = size;

        endOfArray = -1;

    }

    void deleteList()

    {

        delete[] array;

    }

    bool isEmpty()

    {

        if (endOfArray == -1)

            return true;

        return false;

    }

    void resize(int s)

    {

        int *tempArray = array;

        array = new int[s];

        for (int index = 0; index < min(s, endOfArray + 1); index++)

        {

            array[index] = tempArray[index];

        }

        maxSize = s;

    }

    void insert(int data)

    {

        if (endOfArray == maxSize - 1)

            resize(2 * maxSize);

        array[++endOfArray] = data;

    }

    void insertAtIndex(int insertIndex, int data)

    {

        // if the user enters an invalid insertIndex, the element is

        // appended to the array, after the current last element

        if (insertIndex > endOfArray + 1)

            insertIndex = endOfArray + 1;

        if (endOfArray == maxSize - 1)

            resize(2 * maxSize);

        for (int index = endOfArray; index >= insertIndex; index--)

            array[index + 1] = array[index];

        array[insertIndex] = data;

        endOfArray++;

    }

    int read(int index)

    {

        return array[index];

    }

    void modifyElement(int index, int data)

    {

        array[index] = data;

    }

    void deleteElement(int deleteIndex)

    {

        // shift elements one cell to the left starting from deleteIndex+1 to endOfArray-1

        // i.e., move element at deleteIndex + 1 to deleteIndex and so on

        for (int index = deleteIndex; index < endOfArray; index++)

            array[index] = array[index + 1];

        endOfArray--;

    }

    int countList()

    {

        int count = 0;

        for (int index = 0; index <= endOfArray; index++)

            count++;

        return count;

    }

    void print()

    {

        for (int index = 0; index <= endOfArray; index++)

            cout << array[index] << " ";

        cout << endl;

    }

};

void SelectionSort(List list)

{

    // Implement the selection sorting algorithm here...

    for (int i = 0; i < list.countList(); i++)

    {

        for (int j = i + 1; j < list.countList(); j++)

        {

            if (list.read(i) > list.read(j))

            {

                int temp = list.read(i);

                list.modifyElement(i, list.read(j));

                list.modifyElement(j, temp);

            }

        }

    }

}

int main()

{

    using namespace std::chrono;

    srand(time(NULL));

    int maxValue;

    cout << "Enter the max value: ";

    cin >> maxValue;

    int numTrials;

    cout << "Enter the number of trials: ";

    cin >> numTrials;

    for (int listSize = 1000; listSize <= 20000; listSize += 1000)

    {

        double totalSortingTime = 0;

        for (int trials = 1; trials <= numTrials; trials++)

        {

            List integerList(1);

            for (int i = 0; i < listSize; i++)

            {

                int value = 1 + rand() % maxValue;

                integerList.insertAtIndex(i, value);

            }

            high_resolution_clock::time_point t1 = high_resolution_clock::now();

            SelectionSort(integerList);

            high_resolution_clock::time_point t2 = high_resolution_clock::now();

            duration<double, std::milli> sortingTime_milli = t2 - t1;

            totalSortingTime += sortingTime_milli.count();

            integerList.deleteList();

        }

        cout << "Average sorting time for list size " << listSize << " is " << (totalSortingTime / numTrials) << " milli seconds " << endl;

    } // list size   loop

    system("pause");

    return 0;

}