4 Programming Question (40 points 4.1 Instructions You need to write the code by

Question

4 Programming Question (40 points 4.1 Instructions You need to write the code by yourself. Your implementation must use C/C++ and your code must run on the Linux machine general.asu.edu. Please refer to the programming guide (available under the Assignments folder on Blackboard) for using the general.asu.edu server, as well as compiling and running C/C+code under Linux. For this question, you need to provide a Makefile that compiles your program to an executable named a2 that runs on the Linux machine general.asu.edu. Our TA will write a script to compile and run all student submissions; therefore, executing the command make in the Code folder must produce the executable a2 also located in the Code folder 4.2 Requirements question, you will write a serial individual files. Valid commands include: 1 program that executes a sequence of commands that operate orn Start Name, where Name is a character string of maximum length 20 alphabetic characters representing the name of the data file (Name.txt). The structure of Name.txt is an integer N indicating the total number of data entries contained in this file, followed by N additional lines of integers (the actual data entries). This command first reads N from the file Name.txt, dynamically allocates an array of integers of size N (if it has not already been allocated), and then reads the remaining N data entries into the array. The commands that follow until the End command are to be applied to the resulting data array The output of the Start command is: Processing data from: Name.txt End Name, which indicates the end of the processing for the data in file Name.txt. The Start and End commands will always come in pairs with matching names. Any memory dynamically allocated for Name must be freed on an End command. The output of the End command is: End of processing data from: Name.txt

Explanation / Answer

merge Sort Programme

#include<stdlib.h>

#include<stdio.h>

void mergeSort(int numArr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

int tempL[n1], tempR[n2];

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

tempL[i] = numArr[l + i];

for (j = 0; j < n2; j++)

tempR[j] = numArr[m + 1+ j];

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2)

{

if (tempL[i] <= tempR[j])

{

numArr[k] = tempL[i];

i++;

}

else

{

numArr[k] = tempR[j];

j++;

}

k++;

}

while (i < n1)

{

numArr[k] = tempL[i];

i++;

k++;

}

while (j < n2)

{

numArr[k] = tempR[j];

j++;

k++;

}

}

void mergeSortFun(int array[], int l, int r)

{

if (l < r)

{

int m = l+(r-l)/2;

mergeSortFun(array, l, m);

mergeSortFun(array, m+1, r);

mergeSort(array, l, m, r);

}

}

void printArray(int Arr[], int size)

{

int i;

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

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

printf(" ");

}

int main()

{

int array[] = {20, 11, 15, 8, 10, 6};

int arrSize = sizeof(array)/sizeof(array[0]);

printf("Array is ");

printArray(array, arrSize);

mergeSortFun(array, 0, arrSize - 1);

printf(" Sorted array is ");

printArray(array, arrSize);

return 0;

}

Insertion Sort Programme

#include <stdio.h>

#include <math.h>

void insertionSortFunc(int numArr[], int n)

{

int i, key, j,count;

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

{

key = numArr[i];

j = i-1;

while (j >= 0 && numArr[j] > key)

{

numArr[j+1] = numArr[j];

j = j-1;

count++;

}

numArr[j+1] = key;

}

}

void printArray(int array[], int n)

{

int i;

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

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

printf(" ");

}

int main()

{

int arrValue[] = {12, 11, 13, 5, 6};

int num = sizeof(arrValue)/sizeof(arrValue[0]);

insertionSortFunc(arrValue, num);

printArray(arrValue, num);

return 0;

}

Number of comparision made by insertion sort. n+2;

Time Complexity : O(n*n)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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