Problem: Code insertion sort and merge sort using the pseudocode from the text,

Question

Problem: Code insertion sort and merge sort using the pseudocode from the text, and run these sorts on two arrays as specified below. Time the sorts and create a table for the output that displays the actual times. Your times should be in seconds, accurate to at least three decimal places. DO NOT DISPLAY THE ARRAYS! Here are the problem specifications.
1. Create a dynamic array of ints. Get the dimension of the array from the command line in argv[1].
2. Populate the array with random ints in the range [1, 30000].
3. Time the sorts and save the times.
4. Display the results of your sorts in table format with the accuracy specified earlier.
Here is an example of the expected output
Sort Unsorted time Sorted time
------------------------------------------------------------------------
Merge sort 0.000 0.000

Insertion sort 0.000 0.000

Notes
1. You should use the rand() function from <cstdlib> to generate your pseudorandom numbers.
2. You should use the clock() function from <ctime> to help you generate clock times.
3. You should use operators new and delete to allocate and deallocate your arrays.
4. Each sort should sort the same numbers in the same order.
5. Be sure to test your program using the g++ compiler before submitting.
6. Be sure to use program style (pre/post, header comments, sparse code comments, selfdocumenting names, whitespace, indentation, etc.).

Finally, answer this question. Do the times of the sorts you computed correspond with the theological bounds? Explain your answer

Criteria Value (points)
Style
Global functions
Output with annotations
Greeting
Error checking on input

INSERTION-SORT(A)
1 for j ? 2 to length[A]
2 do key ? A[j]
3 ? Insert A[j] into the sorted
sequence A[1 j - 1]
4 i ? j - 1
5 while i > 0 and A[i] > key
6 do A[i + 1] ? A[i]
7 i ? i - 1
8 A[i + 1] ? key

MERGE(A, p, q, r)
1 n1 ? q - p + 1
2 n2 ? r - q
3 create arrays L[1 n1 + 1] and R[1 n2 + 1]
4 for i ? 1 to n1
5 do L[i] ? A[p + i - 1]
6 for j ? 1 to n2
7 do R[j] ? A[q + j]
8 L[n1 + 1] ? 8
9 R[n2 + 1] ? 8
10 i ? 1
11 j ? 1
12 for k ? p to r
13 do if L[i] = R[j]
14 then A[k] ? L[i]
15 i ? i + 1
16 else A[k] ? R[j]
17 j ? j + 1

Explanation / Answer

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

//displays array elemnets

void display(int a[], int length)

{

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

cout<<a[i]<<" " ;

cout<<endl;

}

//insertion sort

//sorts the array elements using insertion sort

void insertionSort(int a[], int length)

{

int key,i;

for(int j = 1; j < length; j++)

{

key = a[j];

i = j-1;

while(i >= 0 && a[i] > key)

{

a[i+1] = a[i];

i = i-1;

}

a[i+1] = key;

}

}

//helper function for mergesort

void merge(int a[], int low, int high, int mid)

{

int i, j, k, c[50];

i=low;

j=mid+1;

k=low;

while((i<=mid)&&(j<=high))

{

if(a[i]<a[j])

{

c[k]=a[i];

k++;

i++;

}

else

{

c[k]=a[j];

k++;

j++;

}

}

while(i<=mid)

{

c[k]=a[i];

k++;

i++;

}

while(j<=high)

{

c[k]=a[j];

k++;

j++;

}

for(i=low;i<k;i++)

{

a[i]=c[i];

}

}

//mergesort

//sorts the array elements using merge sort

void mergeSort(int a[], int low, int high)

{

int mid;

if(low<high)

{

mid=(low+high)/2;

mergeSort(a,low,mid);

mergeSort(a,mid+1,high);

merge(a,low,high, mid);

}

}

//main funciton

int main(int argc, char* argv[])

{

int length = atoi(argv[1]);

int *arr = new int[length];

int *arr2 = new int[length];

srand(time(0));

time_t start, end, insertionsort, mergesort;

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

{

arr[i] = (rand()%30000)+1;

arr2[i] = arr[i];

}

//display(arr,length);

start = time(NULL);

insertionSort(arr,length);

end = time(NULL);

insertionsort = end - start;

//display(arr,length);

//cout<<endl<<endl;

//display(arr2,length);

start = time(NULL);

mergeSort(arr2,0,length-1);

end = time(NULL);

mergesort = end - start;

//display(arr2,length);

cout<<"sort time"<<endl;

cout<<"---------------------------------"<<endl;

printf("insertion %.3f ",insertionsort);

printf("mergesort %.3f ",mergesort);

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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