Book Image

Practical C Programming

By : B. M. Harwani
Book Image

Practical C Programming

By: B. M. Harwani

Overview of this book

Used in everything from microcontrollers to operating systems, C is a popular programming language among developers because of its flexibility and versatility. This book helps you get hands-on with various tasks, covering the fundamental as well as complex C programming concepts that are essential for making real-life applications. You’ll start with recipes for arrays, strings, user-defined functions, and pre-processing directives. Once you’re familiar with the basic features, you’ll gradually move on to learning pointers, file handling, concurrency, networking, and inter-process communication (IPC). The book then illustrates how to carry out searching and arrange data using different sorting techniques, before demonstrating the implementation of data structures such as stacks and queues. Later, you’ll learn interesting programming features such as using graphics for drawing and animation, and the application of general-purpose utilities. Finally, the book will take you through advanced concepts such as low-level programming, embedded software, IoT, and security in coding, as well as techniques for improving code performance. By the end of this book, you'll have a clear understanding of C programming, and have the skills you need to develop robust apps.
Table of Contents (20 chapters)

Merging two sorted arrays into a single array

In this recipe, we will learn to merge two sorted arrays into a single array so that the resulting merged array is also in sorted form.

How to do it…

  1. Let's assume there are two arrays, p and q, of a certain length. The length of the two arrays can differ. Both have some sorted elements in them, as shown in Figure 1.24:

Figure 1.24
  1. The merged array that will be created from the sorted elements of the preceding two arrays will be called array r. Three subscripts or index locations will be used to point to the respective elements of the three arrays.
  2. Subscript i will be used to point to the index location of array p. Subscript j will be used to point to the index location of array q and subscript k will be used to point to the index location of array r. In the beginning, all three subscripts will be initialized to 0.
  1. The following three formulas will be applied to get the merged sorted array:
    1. The element at p[i] is compared with the element at q[j]. If p[i] is less than q[j], then p[i] is assigned to array r, and the indices of arrays p and r are incremented so that the following element of array p is picked up for the next comparison as follows:
r[k]=p[i];
i++;
k++
  1. If q[j] is less than p[i], then q[j] is assigned to array r, and the indices of arrays q and r  are incremented so that the following element of array q is picked up for the next comparison as follows:
r[k]=q[j];
i++;
k++
  1. If p[i] is equal to q[j], then both the elements are assigned to array r.  p[i] is added to r[k]. The values of the i and k indices are incremented.  q[j] is also added to r[k], and the indices of the q and r arrays are incremented. Refer to the following code snippet:
r[k]=p[i];
i++;
k++
r[k]=q[j];
i++;
k++
  1. The procedure will be repeated until either of the arrays gets over. If any of the arrays is over, the remainder of the elements of the other array will be simply appended to the array r.

The mergetwosortedarrays.c program for merging two sorted arrays is as follows:

#include<stdio.h>
#define max 100

void main()
{
int p[max], q[max], r[max];
int m,n;
int i,j,k;
printf("Enter length of first array:");
scanf("%d",&m);
printf("Enter %d elements of the first array in sorted order
\n",m);
for(i=0;i<m;i++)
scanf("%d",&p[i]);
printf("\nEnter length of second array:");
scanf("%d",&n);
printf("Enter %d elements of the second array in sorted
order\n",n);
for(i=0;i<n;i++ )
scanf("%d",&q[i]);
i=j=k=0;
while ((i<m) && (j <n))
{
if(p[i] < q[j])
{
r[k]=p[i];
i++;
k++;
}
else
{
if(q[j]< p[i])
{
r[k]=q[j];
k++;
j++;
}
else
{
r[k]=p[i];
k++;
i++;
r[k]=q[j];
k++;
j++;
}
}
}
while(i<m)
{
r[k]=p[i];
k++;
i++;
}
while(j<n)
{
r[k]=q[j];
k++;
j++;
}
printf("\nThe combined sorted array is:\n");
for(i = 0;i<k;i++)
printf("%d\n",r[i]);
}

Now, let's go behind the scenes to understand the code better.

How it works...

A macro called max is defined of size 100. Three arrays, p, q, and r, are defined of size max. You will first be asked to enter the size of the first array, p, followed by the sorted elements for array p. The process is repeated for the second array q.

Three indices, i, j and k, are defined and initialized to 0. The three indices will point to the elements of the three arrays, p, q, and r, respectively.

The first elements of arrays p and q, in other words, p[0]  and q[0], are compared and the smaller one is assigned to array r.

Because q[0] is smaller than p[0], q[0] is added to array rand the indices of arrays q and r are incremented for the next comparison as follows:

Figure 1.25

Next, p[0] will be compared with q[1]. Because p[0] is smaller than q[1], the value at p[0] will be assigned to array r at r[1]:

Figure 1.26

Then, p[1] will be compared with q[1]. Because q[1] is smaller than p[1], q[1] will be assigned to array r, and the indices of the q and r arrays will be incremented for the next comparisons (refer to the following diagram):

Figure 1.27

Let's use GCC to compile the mergetwosortedarrays.c program as follows:

D:\CBook>gcc mergetwosortedarrays.c -o mergetwosortedarrays

Now, let's run the generated executable file, mergetwosortedarrays.exe, in order to see the output of the program:

D:\CBook>./mergetwosortedarrays
Enter length of first array:4
Enter 4 elements of the first array in sorted order
4
18
56
99

Enter length of second array:5
Enter 5 elements of the second array in sorted order
1
9
80
200
220

The combined sorted array is:
1
4
9
18
56
80
99
200
220

Voilà! We've successfully merged two sorted arrays into one.