Question

(40 points) Program the following sorting algorithms: InsertionSort, MergeSort, and QuickSort. There are 9 test les uploaded for you on D2L (under the same folder as the assignment), each containing a list of numbers. There are 3 les for each of the input sizes 10, 100, and 1000, and for each input size, there are 3 les that contain the same numbers, but arranged in di erent orders: sorted, sorted in reverse order, and random. Your program should read the input from the test les, sort the numbers in the le using each of the above sorting algorithms, and output the sorted numbers to the screen. You can use any standard programming language such as C, C++, Visual C++, C#, Java, Python.

Answer 1

Answer:

Explanation:

MERGE SORT

#include<stdlib.h>

#include<stdio.h>

#include<string.h>

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];

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

R[j] = arr[m + 1+ j];

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

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 printArray(int A[], int size)

{

int i;

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

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

printf("\n");

}

int main()

{

int arr[1000] = {0};

int arr_size =0;

int data;

char file1[20];

strcpy(file1,"data.txt");

FILE *fp;

fp = fopen(file1,"r+");

if (fp == NULL) // if file not opened return error

{

perror("Unable to open file");

return -1;

}

else

{

fscanf (fp, "%d", &data);    

arr[arr_size]=data;

arr_size++;

while (!feof (fp))

{  

fscanf (fp, "%d", &data);  

arr[arr_size]=data;

arr_size++;    

}

}

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array Using MERGE SORT is \n");

printArray(arr, arr_size);

return 0;

}