Problem 3. (20 points) Consider the pseudo-code below for both insertion sort an

Question

Problem 3. (20 points) Consider the pseudo-code below for both insertion sort and merge sort. Re-write the for-loop as a while loop in the merge sort pseudo-code. (You do not need to show the modified while-loop merge sort.) Then count how many lines need to execute to sort the array [3, 2, 1] for both algorithms. Show some work to receive full (and partial) credit. Only count lines the computer thinks on. Note: for merge sort, do not count the function calls, splits or array creation. Just the number of lines inside the merge function. Also, assume no work needs to be done merging a size 1 and 0 array. Example: sorting 12, 1] with insertion sort = 11 lines, merge = 14 lines.) TopDownMerge (A[], iBegin, iMiddle, iEnd, B[]) Merge sort i = iBegin, j = iMiddle; wnLLe nere are elements in the left or right runs... for (k - iBegin; k = and A[j] > x A[j+1] A[j] 1 end while i-i+ 1 end while

Explanation / Answer

for merge sort:

#include<stdlib.h>
#include<stdio.h>


void merge(int myarray[], int l, int m, int o)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = o - m;

  
int L[n1], O[n2];

  
for(i = 0; i < n1; i++)
L[i] = myarray[l + i];
for(j = 0; j < n2; j++)
O[j] = myarray[m + 1+ j];

  
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= O[j])
{
myarray[k] = L[i];
i++;
}
else
{
myarray[k] = O[j];
j++;
}
k++;
}

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

  
while (j < n2)
{
myarray[k] = O[j];
j++;
k++;
}
}


void mergeSort(int myarray[], int l, int o)
{
if (l < o)
{
int m = l+(o-l)/2;
mergeSort( myarray, l, m);
mergeSort( myarray, m+1, o);
merge( myarray, l, m, o);
}
}

void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf(" ");
}

int main()
{
  
setvbuf(stdout, NULL, _IONBF, 0);
int myarray[] = {343, 4, 123, 21, 6, 8};
int arr_size = sizeof( myarray)/sizeof( myarray[0]);

printf("Given array is ");
printArray(myarray, arr_size);

mergeSort( myarray, 0, arr_size - 1);

printf(" Sorted array is ");
printArray( myarray, arr_size);
return 0;
}

#include<stdio.h>

int main()

{

    int i,j,n,temp,a[30];

    printf("Enter the number of elements:");

    scanf("%d",&n);

    printf(" Enter the elements ");

    for(i=0;i<n;i++)

    {

        scanf("%d",&a[i]);

    }

    for(i=1;i<=n-1;i++)

    {

        temp=a[i];

        j=i-1;

        while((temp<a[j])&&(j>=0))

        {

            a[j+1]=a[j];

            j=j-1;

        }

        a[j+1]=temp;   

    }

    printf(" Sorted list is as shown ");

    for(i=0;i<n;i++)

    {

        printf("%d ",a[i]);

    }

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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