Write a C program, in a file mergesort.c to implement one step of merge sort , i

Question

Write a C program, in a file mergesort.c to implement one step of merge sort, i.e., sort two list of numbers and merge them into a single sorted list, as specified below.

Input: Two sequence of integers read in from stdin, each line consisting of a non-empty sequence of non-negative decimal integers, with adjacent numbers separated by whitespace. (Thus, leading negative signs are not allowed.) The number of integers contained in two lines may be different. An integer may appear multiple times in one line or both lines. Input guarantees that the first two lines are two non-empty sequences of integers.

Output: A sorted sequence in ascending order that contains all the integers from the input sequences. For each integer in the sorted list, printed to stdout using the following statement:

printf("%d ", num)

where num is one integer number being printed out.

Assumptions:

You can assume that each integer input is smaller than the maximum integer size and larger than the minimum integer size. (In other words, you can store them in an integer variable.)

Error Conditions: None

Algorithm: The algorithm for this program should be as follows:

sort the two sequences in ascending order individually;

set two pointers as iterators at the beginning of the two sorted sequence;

create a new empty list for the result of merge;

repeat

read one integer pointed to by the iterator from each sorted sequence;

compare the two integers and append the smaller one to the new list;

move the iterator that points to the smaller integer to the next integer in that sorted sequence;

until no more integers can be read from at least one sorted sequence;

if the iterator of a longer sorted sequence hasn't reach the end, append the integers at and after this iterator to the new list;

Suggested Approach: Reading in the input numbers using scanf won't work. Instead, read in each line using getline() (see man page). Iterate over the line thus read in using sscanf() to read the numbers one after another, and keep track of the largest number in the line.

Note that in order for this to work, once a number is read from the string, the string that is passed into sscanf() the next time should be the "rest of the string" so that you don't read the same number over and over again. You can do this by using a pointer to keep track of where you are in the string, and moving this pointer past each number that is read.

Example: Suppose the input consists of the following lines:

12 128 23 54
34 11 276 455 78 40

Then the output should be

11
12
23
34
40
54
78
128
276
455  

Explanation / Answer

** BRIEF INTRODUCTION OF MINE**

I AM CURRENTLY WORKING WITH INDIAN RAILWAYS AS SOFTWARE ENGINEER.

*****************************************************************************************************************************

// Approach is to first sort both the arrays using merge sort and combine the sorted arrays into final array which shows the result.

#include<stdlib.h>

#include<stdio.h>

// Merges two subarrays of arr[]. First subarray is arr[l..m] Second subarray is arr[m+1..r]

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

// create temp arrays

int L[n1], R[n2];

// Copy data to temp arrays L[] and R[]

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

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

// Merge the temp arrays back into arr[l..r]

i = 0; // Initial index of first subarray

j = 0; // Initial index of second subarray

k = l; // Initial index of merged subarray

while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of L[] to arr[], if there are any

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

// Copy the remaining elements of R[], if there are any

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

/* l is for left index and r is right index of the

sub-array of arr to be sorted */

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

// Sort first and second halves

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(" ");

}

// This function will merge two sorted arrays to produce final third sorted array.

void mergeArrays(int arr1[], int arr2[], int n, int m, int arr3[])
{
int i = 0, j = 0, k = 0;

while (i<n && j <m)
{
// Simple comparison between two sorted arrays using iterator i and j
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}

// Store remaining elements of first array
while (i < n1)
arr3[k++] = arr1[i++];

// Store remaining elements of second array
while (j < n2)
arr3[k++] = arr2[j++];
}

int main()

{

int n,m; // n is size of first array and m is size od second array

int array1[m],array2[n];
int array3[m+n]; // This array will store the result

printf("Enter size of first array");
scanf("%d",&n);
printf("Enter elements of first array");
for(int i=0;i<n;i++)
scanf("%d",&array1[i]);

printf("Enter size of second array ");
scanf("%d",&m);
printf("Enter elements of second array");
for(int i=0;i<m;i++)
scanf("%d",&array2[m]);

mergeSort(array1, 0, n-1);

printf(" First Sorted array is ");
printArray(array1, n);

mergeSort(array2, 0, m-1);

printf(" Second Sorted array is ");
printArray(array2, m);

// Merging sorted arrays
mergeArrays(int array1[], int array2[], int n, int m, int array3[])

printf("Final Output");
for (int i=0; i<(n+m); i++)
printf("%d",array3[i]);
return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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