Data Structures and Algorithm Analysis C++ Write a program to verify your soluti

Question

Data Structures and Algorithm Analysis C++

Write a program to verify your solution to Exercises 7.17. Your program should randomly generate three integer arrays of N=103, 105, and 107 elements and run either merge sort or insertion sort to sort the arrays in increasing and decreasing orders. Then run both insertion sort and merge sort on the three ordered and three reverse-ordered arrays and output the numbers of comparisons and assignments performed between elements of the input arrays during the executions of the two sorting algorithms on each of the arrays. Draw a table to summarize the outputs of your program on the six input arrays (3 ordered and 3 reverse-ordered) and discuss about whether the performance of the insertion sort and merge sort on those ordered and reverse-ordered arrays is consistent with your solution to Exercise 7.17. If not, why?

Determine the running time of mergesort for a. sorted input b. reverse-ordered input c. random input 7.17

Explanation / Answer

#include <cstdlib>

#include <ctime>

#include <iostream>

using namespace std;

int comparisonCount, assignmentCount;
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;

    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++){
        L[i] = arr[l + i];

assignmentCount++;

}
    for (j = 0; j < n2; j++){
        R[j] = arr[m + 1+ j];

assignmentCount++;

}

    i = 0;

j = 0;
    k = l;
    while (i < n1 && j < n2)
    {

comparisonCount++;
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;

assignmentCount++;
        }
        else
        {
            arr[k] = R[j];
            j++;

assignmentCount++;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;

assignmentCount++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;

assignmentCount++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l+(r-l)/2;

        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;

       while (j >= 0 && arr[j] > key)
       {

comparisonCount++;
           arr[j+1] = arr[j];
           j = j-1;

assignmentCount++;
       }
       arr[j+1] = key;

assignmentCount++;
   }
}

void reverseArray(int Arr[], int n){

int i,j,temp;
for(i=0,j=n-1;i<n/2;i++,j--) {

temp=Arr[i];

Arr[i]=Arr[j];

Arr[j]=temp;

}
}

int main() {

int array103[103],array105[105],array107[107],i;

srand((unsigned)time(0));

for(i=0; i<103; i++){

array103[i] = (rand()%1000)+1;

}

for(i=0; i<105; i++){

array105[i] = (rand()%1000)+1;

}

for(i=0; i<107; i++){

array107[i] = (rand()%1000)+1;

}

//sorting arrays in increasing order

insertionSort(array103, 103);

insertionSort(array105, 105);

insertionSort(array107, 107);

//analysis for increasing order

assignmentCount=comparisonCount=0;

insertionSort(array103, 103);

cout<<"For Increasing Order arrays For array of length 103 Insertion Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

mergeSort(array103, 0,102);

cout<<" Merge Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

insertionSort(array105, 105);

cout<<" For array of length 105 Insertion Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

mergeSort(array105, 0,104);

cout<<" Merge Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

insertionSort(array107, 107);

cout<<" For array of length 107 Insertion Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

mergeSort(array107, 0,106);

cout<<" Merge Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

//now arrays are already sorted, reversing them

reverseArray(array103, 103);

reverseArray(array105, 105);

reverseArray(array107, 107);

//analysis for decreasing order

assignmentCount=comparisonCount=0;

insertionSort(array103, 103);

cout<<"For Decreasing Order arrays For array of length 103 Insertion Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

mergeSort(array103, 0,102);

cout<<" Merge Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

insertionSort(array105, 105);

cout<<" For array of length 105 Insertion Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

mergeSort(array105, 0,104);

cout<<" Merge Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

insertionSort(array107, 107);

cout<<" For array of length 107 Insertion Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

assignmentCount=comparisonCount=0;

mergeSort(array107, 0,106);

cout<<" Merge Sort Assignments= "<<assignmentCount<<" Comparisons="<<comparisonCount;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.