UNIT II - ARRAYS AND STRINGS

UNIT II ARRAYS AND STRINGS

Introduction to Arrays: Declaration, Initialization – One dimensional array – Example Program:

Computing Mean, Median and Mode - Two dimensional arrays – Example Program: Matrix
Operations (Addition, Scaling, Determinant and Transpose) - String operations: length, compare,
concatenate, copy – Selection sort, linear and binary search.

INTRODUCTION
In this computerized world, Data structures and Algorithms are the nuts-and-bolts used
by programmers to store and manipulate the data efficiently in computer memory. To develop
the software for any real world problem, having an in-depth understanding on every component
of software engineering is not mandatory. However it is important to understand that, the subject
of data structures and algorithms which are majorly concerned in coding phase of the software.
Different types of data structures can be applied to an application but, only some of them
provide the efficient results. No single data structure works well for all purpose, and so it is
important to know the strengths and limitations of several of them. This chapter will get you
started in thinking about the necessity of data structures, classification of data structures and
many of the fundamental in C language for developing the complex data structures.

BASIC TERMINOLOGIES
Data
Data is a basic fact of entity that is utilized in calculation or manipulation. It may be a
single or set of values that plays a vital role in the computational procedures. In general, Data are
classified as Numerical and Alphanumerical data.
Example: Name of the person (Alphanumerical), Roll number of the student
(Numerical).

Structuring of Data
Whether data is a single or group of values, it must be organized in a particular fashion
for computer processing (Storing, retrieving and manipulating). This organization leads to
structuring of data.
Example1: Consider the data {23, 4, 8, 35, 11, 90}. These are belonging to numerical
type, so it’s organized in a single group such as “Integer Array”. Due to this type of
organization, we can perform operation like sorting, adding new values, delete a value and
searching.
Example2: Consider the data {“Arun”, 65, “Employee”, 15000} which indicate person
information such as name, age, designation, salary. These are belonging to Numerical as well as
Alphanumerical data. So it’s best to organize like a multiple group such as two “2-Dimensional
Character Array” for storing name and designation respectively, and two “Integer Array” for
storing age and salary. But accessing a person information is become complex using these
multiple array. Instead of that, we can organize these data using single group which has an
ability to handle multiple data type such as “Structure”. So structuring of data plays important
role in problem solving.

Need for Studying “Data Structures”

Program = Algorithm + Data structures

 UNIT II - ARRAYS AND STRINGS

A computer is an electronic programmable device that manipulates information

presented in the form of data. The student of computer science should be aware of, how data is
manipulated in a system and the methods for utilization of those data.
Program is a combination of data structures and algorithms (procedures), so the Software
developer must know the concepts of Data Structures to develop a computerized solution for a
given problem. To develop an efficient program (for any problem), the person should know
about, How the data are going to be organized (Storing)?, How it will be processed (Retrieving)?
and What is the logic behind it?. The first two query states the usage of data structures and last
one states the algorithm.
For example, consider the sorting problem for a given numbers. To perform sorting, first
we know about how to structure the data (i.e., whether data are going to be stored in a linear
array or not). After that, we know how to process the data (i.e., all data are taken at a same time
for processing or it may be processed one by one). Finally we know that how we perform the
sorting process (i.e., by using predefined sorting algorithms such as selection sort, bubble sort,
insertion sort or by using their own procedures).
Therefore it is very essential to study the concepts of data organization and manipulation
which is dealt by the Data Structures. So a data structure is a basic thing to do any problem
solving concept.

ALGORITHM
To solve a well-defined computational problem, an algorithm is a step-by-step finite
sequence of definite instructions while terminates with the production of correct output from the
given input. It is generally written in Pseudo-English like statements. Algorithm is independent
of programming language. It can be easily converted into any programming language, based on
its syntactic and semantic constructs. It should be concise and free of ambiguity.

Example1: Exchanging the value of variables using intermediate variable.

Step 1: Get the values of x & y.
Step 2: Assign the value of x to the intermediate variable t. (i.e. t=x)
Step 3: Assign y value to x. (i.e. x=y)
Step 4: Assign t value to y. (i.e. y=t)
Step 5: Print the values of x & y.

Example 2: Exchanging the value of variables without using intermediate variable.

Step 1: Get the values of x & y.
Step 2: Use the mathematical formula, x=x+y, y=x-y, and x=x-y.
Step 3: Print the values of x & y.

PROGRAM
Computer solution to a problem is a set of explicit and unambiguous instruction
expressed in a programming language. This set of instruction is called Program. In other words,
a program is the expression of an algorithm in a programming language.
What do you meant by Efficient Program?
Efficient program is determined by its time and space complexity. Time complexity
states the time needed to execute (compile as well as run time) a given program. Space
complexity states the memory space needed to store and process the program.
Example: Addition of two given numbers.
Program-1 Program-2
#include<stdio.h> #include<stdio.h>
void main() void main()
 UNIT II - ARRAYS AND STRINGS

{ {
int a,b; int a,b,c,d;
printf(“Enter 2 nos for addition\n”); printf(“Enter 2 nos for addition\n”);
scanf(“%d %d”, &a,&b); scanf(“%d %d”, &a,&b);
printf(“Sum=%d\n”,a+b); c=a;
} d=b;
e=c+d;
printf(“Sum=%d\n”,e);
}

From the above example, Program-1 & Program-2 produces same output. But the time
complexity of Program-2 is greater than Program-1. Even though Program-2 gives same output,
number of lines of code (LOC) is high. Let we consider, each instruction needs 1 second for its
execution then execution time of Program-1 is 4 whereas Program-2 is 7. So Program-1 is
efficient than the Program-2.
We can say that, the efficiency of a given program is based on its time complexity. The
time complexity is not only depends on LOC, but also based on some properties that will be
discussed later in this chapter. Time complexity is represented or denoted by the Asymptotic
Notation which is universally accepted format. For instance, time complexity of “Insertion sort”
algorithm is denoted by O(N2). Pronounced like Big-O of N2.

ARRAY AND STRING

 Array is a structured type, which is a collection of homogeneous data elements described

by a single name.
 Individual values in the array are called as element.
 Array elements are differentiated by their position called index or subscript that are
always enclosed in square brackets [ ].
 Subscript must be expressed as a non-negative integer.
 The dimension of an array is determined by the number of subscripts.
 All the Array elements are numbered, starting from zero.
 The first item is stored at the address pointed by the array_name. This can also be
referred as position ‘0’.
 Length of the array is equal to the number of elements in array i.e., calculated by,
Length= UpperBound – LowerBound + 1. Where Upper bound is index of last element
and Lower bound is index of first element.
 Contiguous Memory will be allocated based on its size specification (i.e., Multiplication
of Length & Bytes of data type).

Arrays are widely used data type in ‘C’ language. It is a collection of elements of similar data
type. These similar elements could be of all integers, all floats or all characters. An array of
character is called as string whereas and array of integer or float is simply called as an array. So
array may be defined as a group of elements that share a common name and that are defined by
position or index. The elements of arrays are store in sequential order in memory.
There are mainly two types of Arrays are used:
 One dimensional Array
 Multidimensional Array
 UNIT II - ARRAYS AND STRINGS

One-Dimensional Array
Syntax Storagetype Datatype Arrayname[Size];
Where,
Storagetype => Define the scope of variable (i.e.) any one of the keyword such as
Auto(optional) / Register / Static / Extern.
Datatype => Type of value stored in array. E.g. int, char.
Arrayname => Name of the array represented by the user.
Size => Maximum no.of element stored in array.
Example int X[5];
 Address of array and the address of first element are same.
 The system need not keep track of the address of every element of A, but needs to keep
address of first element only, denoted by Base(A) and called as Base Address.
 We can obtain the address of variable using the Address operator (&). For instance, ‘&A’
display the Base address of variable A.
 The computer calculates the address of any element of A by the following formula.

Address of Nth element = Base(A) + ( Index(N) * Bytes per element )

Example, consider the statement int X[5]; The Memory allocation will be,
420 422 424 426 428

X[0] X[1] X[2] X[3] X[4]

 Here Base address is “420” and Bytes per element is 2. Suppose the system need to
calculate the address of 3rd element,
Address of 3rd element= 420 + (3 * 2)
= 426
Initialization of One-Dimensional Array

SyntaxDatatype arrayname [size] = {list of values};

Example
1. int mark[7]={100,7,45,75,88};

Memory address 0001 0002 0003 0004 0005 0006 0007

100 7 45 75 88 0 0

mark[0] mark[1] mark[2] mark[3] mark[4] mark[5] mark[6]

 Here, only 5 elements are initialized to the array “mark”. In default, the compiler will
assign zero to the uninitialized elements of an integer array and Garbage values to the
character array.

2. char nam[6]={‘G’,’U’,’N’,’A’,’\0’}; or char nam[6]=”GUNA”;

Program 1: Write a ‘C’ program to find the biggest number among the given ten numbers using
array.
#include<stdio.h> Output
 UNIT II - ARRAYS AND STRINGS

#include<conio.h>
void main( ) enter any 10 numbers
{ 1 5 6 10 9 2 3 4 7 8
int value[10],i,big=0; the biggest number is 10
clrscr( );
printf("enter any 10 numbers\n");
for(i=0;i<10;i++)
scanf("%d",&value[i]);
big=value[0];
for(i=1;i<10;i++)
if(big<value[i])
big=value[i];
printf("the biggest number is: %d",big);
getch( );
}

One dimensional Array

So far, we've been declaring simple variables: the declaration
int i;
declares a single variable, named i, of type int.

It is also possible to declare an array of several elements.

The declaration
int a[10];
declares an array, named a, consisting of ten elements, each of type int. Simply speaking, an
array is a variable that can hold more than one value.
You specify which of the several values you're referring to at any given time by using a numeric
subscript. (Arrays in programming are similar to vectors or matrices in mathematics.)

We can represent the array a above with a picture like this:

In C, arrays are zero-based: the ten elements of a 10-element array are numbered from 0 to 9.
The subscript which specifies a single element of an array is simply an integer expression in
square brackets.

The first element of the array is a[0], the second element is a[1], etc. You can use these ``array
subscript expressions'' anywhere you can use the name of a simple variable, for example:
a[0] = 10;
a[1] = 20;
a[2] = a[0] + a[1];

Notice that the subscripted array references (i.e. expressions such as a[0] and a[1]) can appear on
either side of the assignment operator. it is possible to initialize some or all elements of an array
when the array is defined. The syntax looks like this:
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 UNIT II - ARRAYS AND STRINGS

The list of values, enclosed in braces {}, separated by commas, provides the initial values for
successive elements of the array.

The subscript does not have to be a constant like 0 or 1; it can be any integral expression. For
example, it's common to loop over all elements of an array:
int i;

for(i = 0; i < 10; i = i + 1)

a[i] = 0;

This loop sets all ten elements of the array a to 0.

Arrays are a real convenience for many problems, but there is not a lot that C will do with them
for you automatically. In particular, you can neither set all elements of an array at once nor
assign one array to another; both of the assignments
a = 0; /* WRONG */
and
int b[10];
b = a; /* WRONG */
are illegal.

To set all of the elements of an array to some value, you must do so one by one, as in the loop
example above. To copy the contents of one array to another, you must again do so one by one:
int b[10];

for(i = 0; i < 10; i = i + 1)

b[i] = a[i];

Remember that for an array declared

int a[10];
there is no element a[10]; the topmost element is a[9]. This is one reason that zero-based loops
are also common in C. Note that the for loop
for(i = 0; i < 10; i = i + 1)
...
does just what you want in this case: it starts at 0, the number 10 suggests (correctly) that it goes
through 10 iterations, but the less-than comparison means that the last trip through the loop has i
set to 9. (The comparison i <= 9 would also work, but it would be less clear and therefore poorer
style.)

C program to find the mean, median and mode of a set of numbers

#include<stdio.h>
main()
{
int i,j,a[20]={0},sum=0,n,t,b[20]={0},k=0,c=1,max=0,mode;
float x=0.0,y=0.0;
printf("\nEnter the limit\n");
scanf("%d",&n);
printf("Enter the set of numbers\n");
for(i=0;i<n;i++)
 UNIT II - ARRAYS AND STRINGS

{
scanf("%d",&a[i]);
sum=sum+a[i];
}
x=(float)sum/(float)n;
printf("Mean\t= %f",x);

for(i=0;i<n;i++) {
for(j=i+1;j<n;j++) {
if(a[i]>a[j]) {
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
if(n%2==0)
y=(float)(a[n/2]+a[(n-1)/2])/2;
else
y=a[(n-1)/2];
printf("\nMedian\t= %f",y);

for(i=0;i<n-1;i++) {
mode=0;
for(j=i+1;j<n;j++) {
if(a[i]==a[j]) {
mode++;
}
}
if((mode>max)&&(mode!=0)) {
k=0;
max=mode;
b[k]=a[i];
k++;
}
else if(mode==max) {
b[k]=a[i];
k++;
}
}
for(i=0;i<n;i++) {
if(a[i]==b[i])
c++;
}
if(c==n)
printf("\nThere is no mode");
else {
printf("\nMode\t= ");
for(i=0;i<k;i++)
printf("%d ",b[i]);
 UNIT II - ARRAYS AND STRINGS

}
}

Two-dimensional array
 It is also referred as matrix. The total number of elements in array can be calculated by
the multiplication of row-size and column-size. For instance, row size is 3 and column
size is 2 then total element is 3x2 = 6.
 It is not compulsory that the row size and column size should be equal. All the elements
of the first row will be assigned and then second row and so on.
 While initializing an array, the row size is optional.
 An array of string can be represented as a two dimensional array of characters.
Syntax StorageType Datatype Arrayname[Row_size] [Column_size]
Example
1. int rank[ ][2]={1,2,3,4,5,6};
2. char nam[4][8] = { {“madhu”}, {“revathy”}, {“anand”}, {“vijaya”} }

Program 2: Write a ‘C’ program to calculate sum of all elements in a matrix.

#include<stdio.h> Output
#include<conio.h> enter the order of matrix
void main( ) 2 2
{ enter the element of matrix
int value[10][10], i,j,row,col,sum=0; 2 4 8 1
clrscr( ); the sum is: 15
printf("enter the order of matrix\n");
scanf("%d %d",&row,&col); printf("\
nenter the elements of matrix\n"); Memory Allocation 0 1
for(i=0;i<row;i++) 0 2 4
for(j=0;j<col;j++) 1 8 1
scanf("%d",&value[i][j]);
for(i=0;i<row;i++)
for(j=0;j<col;j++)
sum=sum+value[i][j];
printf("the sum is: %d", sum);
 UNIT II - ARRAYS AND STRINGS

getch( );
}

Transpose
The transpose of a matrix is a new matrix whose rows are the columns of
the original. (This makes the columns of the new matrix the rows of the
original). Here is a matrix and its transpose:

The superscript "T" means "transpose".

Another way to look at the transpose is that the element at row r column c in
the original is placed at row c column r of the transpose. The element arc of
the original matrix becomes element acr in the transposed matrix.
Usually we will work with square matrices, and it is usually square matrices
that will be transposed. However, non-square matrices can be transposed, as
well:

C Program for Addition , Multiplication , Subtraction & Transpose of Matrices

#include<stdio.h>
#include<conio.h>
int main()
{
int m,n,a[20][20],b[20][20],i,j,sum[20][20],sub[20][20],opt,tr[20][20],opt1,ch,e,f;
printf("Note : For Addition or Subtraction , no. of rows and columns should be same and for
transpose of matrices , your first matrices entered should be the desired matrices .\n");
printf("Enter the no. of rows: ");
scanf("%d",&m);
printf("Enter the no. of columns: ");
scanf("%d",&n);
printf("Enter the Data Elements of first matrices\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
} printf("Enter the no. of rows for second matrices: ");
scanf("%d",&e);
printf("Enter the no. of columns: ");
scanf("%d",&f);
 UNIT II - ARRAYS AND STRINGS

printf("Enter the Data Elements of second matrices\n");

for(i=0;i<e;i++)
{
for(j=0;j<f;j++)
{
scanf("%d",&b[i][j]);
}
}
do
{
if(m==e&&n==f)
{
printf("Enter 1 for addtion or subtraction of matrices\n");
if(n==e){printf("Enter 2 for multiplication of matrices\n");}
printf("Enter 3 for transpose of first matrices\n");
}
else if(m!=n&&n==e)
{
printf("Enter 2 for multiplication of matrices\n");
printf("Enter 3 for transpose of first matrices\n");
}
else
{
printf("Enter 3 for transpose of first matrices\n");
}
scanf("%d",&ch);
switch(ch)
{
case 1 :
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
sum[i][j]=a[i][j]+b[i][j];
sub[i][j]=a[i][j]-b[i][j];
}
}
printf("Enter 1 for Addition or 2 for Subtraction: ");
scanf("%d",&opt);
switch(opt)
{
case 1 :
printf("The resultant matrices is :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
 UNIT II - ARRAYS AND STRINGS

printf("%3d",sum[i][j]);
}
printf("\n");
}
break;
case 2 :
printf("The resultant matrices is :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%3d",sub[i][j]);
}
printf("\n");
}
}
break;
case 2 :
printf("The resultant matrices is : \n");
int k;
for(i=0;i<m;i++)
{
for(j=0;j<f;j++)
{ sum[i][j]=0;
for(k=0;k<m;k++)
{
sum[i][j]+=a[i][k]*b[k][j];
}
printf("%d\t",sum[i][j]);
}
printf("\n");
}
break;
case 3 :
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
tr[j][i]=a[i][j];
}
}
printf("The resultant matrices is :\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%3d",tr[i][j]);
 UNIT II - ARRAYS AND STRINGS

}
printf("\n");
}

break; }}
while(ch>0);
getch();
}

Determinant of a Matrix
What is Determinant of a Matrix?
Determinant of a Matrix is a special number that is defined only for square matrices (matrices
which have same number of rows and columns). Determinant is used at many places in calculus
and other matrix related algebra, it actually represents the matrix in term of a real number which
can be used in solving system of linear equation and finding the inverse of a matrix.
How to calculate?
The value of determinant of a matrix can be calculated by following procedure –
For each element of first row or first column get cofactor of those elements and then multiply the
element with the determinant of the corresponding cofactor, and finally add them with alternate
signs. As a base case the value of determinant of a 1*1 matrix is the single value itself.
Cofactor of an element, is a matrix which we can get by removing row and column of that
element from that matrix.
Determinant of 2 x 2 Matrix:

Determinant of 3 x 3 Matrix:
 UNIT II - ARRAYS AND STRINGS

C program to find Determinant of a matrix

// Dimension of input square matrix
#define N 4
 
// Function to get cofactor of mat[p][q] in temp[][]. n is current
// dimension of mat[][]
void getCofactor(int mat[N][N], int temp[N][N], int p, int q, int n)
{
    int i = 0, j = 0;
 
    // Looping for each element of the matrix
    for (int row = 0; row < n; row++)
    {
        for (int col = 0; col < n; col++)
        {
            //  Copying into temporary matrix only those element
            //  which are not in given row and column
            if (row != p && col != q)
            {
                temp[i][j++] = mat[row][col];
 
                // Row is filled, so increase row index and
                // reset col index
                if (j == n - 1)
                {
                    j = 0;
                    i++;
                }
            }
        }
    }
}
 
/* Recursive function for finding determinant of matrix.
   n is current dimension of mat[][]. */
int determinantOfMatrix(int mat[N][N], int n)
{
    int D = 0; // Initialize result
 
    //  Base case : if matrix contains single element
    if (n == 1)
        return mat[0][0];
 
    int temp[N][N]; // To store cofactors
 
    int sign = 1;  // To store sign multiplier
 
     // Iterate for each element of first row
    for (int f = 0; f < n; f++)
    {
 UNIT II - ARRAYS AND STRINGS

        // Getting Cofactor of mat[0][f]

        getCofactor(mat, temp, 0, f, n);
        D += sign * mat[0][f] * determinantOfMatrix(temp, n - 1);
 
        // terms are to be added with alternate sign
        sign = -sign;
    }
 
    return D;
}
 
/* function for displaying the matrix */
void display(int mat[N][N], int row, int col)
{
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
            printf("  %d", mat[i][j]);
        printf("n");
    }
}
 
// Driver program to test above functions
int main()
{
    /* int mat[N][N] = {{6, 1, 1},
                     {4, -2, 5},
                     {2, 8, 7}}; */
 
    int mat[N][N] = {{1, 0, 2, -1},
                     {3, 0, 0, 5},
                     {2, 1, 4, -3},
                     {1, 0, 5, 0}
                    };
 
    printf("Determinant of the matrix is : %d",
            determinantOfMatrix(mat, N));
    return 0;
}

Multidimensional Array

The declaration of an array of arrays looks like this:

int a2[5][7];
You have to read complicated declarations like these ``inside out.'' What this one says is that a2
is an array of 5 something’s, and that each of the something’s is an array of 7 ints. More briefly,
``a2 is an array of 5 arrays of 7 ints,'' or, ``a2 is an array of array of int.'' In the declaration of a2,
the brackets closest to the identifier a2 tell you what a2 first and foremost is. That's how you
 UNIT II - ARRAYS AND STRINGS

know it's an array of 5 arrays of size 7, not the other way around. You can think of a2 as having
5 ``rows'' and 7 ``columns,'' although this interpretation is not mandatory. (You could also treat
the ``first'' or inner subscript as ``x'' and the second as ``y.'' Unless you're doing something fancy,
all you have to worry about is that the subscripts when you access the array match those that you
used when you declared it, as in the examples below.)
To illustrate the use of multidimensional arrays, we might fill in the elements of the above array
a2 using this piece of code:
int i, j;
for(i = 0; i < 5; i = i + 1)
{
for(j = 0; j < 7; j = j + 1)

a2[i][j] = 10 * i + j;
}
This pair of nested loops sets a[1][2] to 12, a[4][1] to 41, etc. Since the first dimension of a2 is 5,
the first subscripting index variable, i, runs from 0 to 4. Similarly, the second subscript varies
from 0 to 6.
We could print a2 out (in a two-dimensional way, suggesting its structure) with a similar pair of
nested loops:
for (i = 0; i < 5; i = i + 1)
{
for (j = 0; j < 7; j = j + 1)
printf ("%d\t", a2[i][j]);
printf ("\n");
}
(The character \t in the printf string is the tab character.)
Just to see more clearly what's going on, we could make the ``row'' and ``column'' subscripts
explicit by printing them, too:
for(j = 0; j < 7; j = j + 1)
printf("\t%d:", j);
printf ("\n");

for(i = 0; i < 5; i = i + 1)
{
printf("%d:", i);
for(j = 0; j < 7; j = j + 1)
printf("\t%d", a2[i][j]);
printf("\n");
}
This last fragment would print
0: 1: 2: 3: 4: 5: 6:
0: 0 1 2 3 4 5 6
1: 10 11 12 13 14 15 16
2: 20 21 22 23 24 25 26
3: 30 31 32 33 34 35 36
4: 40 41 42 43 44 45 46

STRING
String are the combination of number of characters these are used to store any word in any
variable of constant. A string is an array of character. It is internally represented in system by
 UNIT II - ARRAYS AND STRINGS

using ASCII value. Every single character can have its own ASCII value in the system. A
character string is stored in one array of character type.
e.g. “Ram” contains ASCII value per location, when we are using strings and then these strings
are always terminated by character ‘\0’. We use conversion specifies %s to set any string we can
have any string as follows:-
char nm [25].
When we store any value in nm variable then it can hold only 24 character because at the end of
the string one character is consumed automatically by ‘\0’.
#include<string.h>
There are some common inbuilt functions to manipulation on string in string.h file. these are as
follows:
1. strlen - string length
2. strcpy - string copy
3. strcmp - string compare
4. strups - string upper
5. strlwr - string lower
6. strcat - string concatenate
In C, string.h includes various build in functions for string operations. The main operations are
1. Length of the string (strlen)
The syntax of strlen is :
strlen(string);

It calculates the length of the string and returns its length. For example:

#include<string.h>

string = "Mumbai";

printf("Length = %d",strlen(string));

The above code displays 5 because Mumbai consists of 5 characters. Note: it does not count null
character.

2. Joining two strings (strcat)

The syntax of strcat is

strcat(string1,string2);

Now it removes the null character from string1 and joins the first character of string2 at that
position. Now, string1 consists of both string1 and string2 in joined form. Example:

#include<string.h>=

char string1[] = "Anti";

char string2[] = "Particle";

strcat(string1,string2);=
 UNIT II - ARRAYS AND STRINGS

printf("%s",string1); //display AntiParticle

3. Comparing two strings(strcmp)

The syntax of strcmp is

strcmp(string1,string2);

It returns 0 if string1 is same as string2 and returns 1 if they are not same. Example:

#include<string.h>

char string1 = "Nepal";

char string2 = "Srilanka";

if(strcmp(string1,string2)==0){

printf("They are equal");

}else{

printf("They are not equal"); //this is executed

4. Copying one string to another (strcpy)

The syntax of strcpy is

strcpy(destination_string, source_string);

It copies the content of source_string to destination_string. Example:

#include<string.h>

char source[] = "Hello";

char destination[10]; //uninitialized

strcpy(destination,source);

printf("%s",destination); //prints Hello

These are some of the functions in string.h for string operation. To use these functions you must
include header file <string.h>. But we can make our own functions to perform above task
without including string,h. Here is the complete source code that has own functions find_length
(like strlen) to find the length, join_strings( like strcat) for joining strings, compare_strings(like
 UNIT II - ARRAYS AND STRINGS

strcmp) for comparing two strings and copy_string(like strcpy) to copy one string from another.
Observer carefully the code, if you are a beginner, you will learn a lot of things about string
operation.

///fundamental string operation, lenth, concatenation, compare and copy strings without
string.h
#
include < stdio.h > #include < stdlib.h >
  int find_length(char string[]) {
    int len = 0, i;
    for (i = 0; string[i] != '\0'; i++) {
      len++;
    }
    return len;
  }
void join_strings(char string1[], char string2[]) {
    int i, len1, len2;
    len1 = find_length(string1);
    len2 = find_length(string2);
    for (i = len1; i < len1 + len2; i++) {
      string1[i] = string2[i - len1];
    }
    string1[i] = '\0'; //adding null character at the end of input
  }

  /*returns 0 if thery are same otherwise returns 1*/

int compare_strings(char string1[], char string2[]) {
  int len1, len2, i, count = 0;
  len1 = find_length(string1);
  len2 = find_length(string2);
  if (len1 != len2)
    return 1;
  for (i = 0; i < len1; i++) {
    if (string1[i] == string2[i])
      count++;
  }
  if (count == len1)
    return 0;
  return 1;
}
void copy_string(char destination[], char source[]) {
  int len, i;
  len = find_length(source);
  for (i = 0; i < len; i++) {
    destination[i] = source[i];
  }
  destination[i] = '\0';
}
int main() {
  char string1[20], string2[20]; //string variables declaration with size 20
 UNIT II - ARRAYS AND STRINGS

  int choice;
  while (1) {
    printf("\n1. Find Length \n2. Concatenate \n3. Compare \n4. Copy \n5. Exit\n");
    printf("Enter your choice: ");
    scanf("%d", & choice);
    switch (choice) {
    case 1:
      printf("Enter the string: ");
      scanf("%s", string1);
      printf("The length of string is %d", find_length(string1));
      break;
    case 2:
      printf("Enter two strings: ");
      scanf("%s%s", string1, string2);
      join_strings(string1, string2);
      printf("The concatenated string is %s", string1);
      break;
    case 3:
      printf("Enter two strings: ");
      scanf("%s%s", string1, string2);
      if (compare_strings(string1, string2) == 0) {
        printf("They are equal");
      } else {
        printf("They are not equal");
      }
      break;
    case 4:
      printf("Enter a string: ");
      scanf("%s", string1);
      printf("String1 = %s\n");
      printf("After copying string1 to string 2\n");
      copy_string(string2, string1);
      printf("String2 = %s", string2);
      break;
    case 5:
      exit(0);
    }
  }
  return 0;
}

SORTING TECHNIQUES
INTRODUCTION
It is a process rearranging a group (or) a sequence of elements either in ascending or
descending order depends upon their relationship among the data items. In other words, sorting
is the process of rearranging records in order of their keys.
Application
They are used in many applications such as,
1. Dictionaries
 UNIT II - ARRAYS AND STRINGS

2. Telephone directories
3. Students information system etc,
Sorting algorithms have a wide range of usage. Hence there is a need for faster sorting
algorithms. We consider about the analysis of their complexities. Most sorting algorithms are
comparison Based and therefore mainly comparison statements are taken into account in
complexity analysis.
The factors to be considered while choosing a sorting technique are,
1. Execution time of sorting technique
2. Number of comparisons required for sorting
3. Main or auxiliary memory space needed for sorting techniques
4. Programming time
 Sorting algorithms are often classified by behavior of algorithm that is computational
complexity,
Good behavior – O(N log N)
Worst behavior – O( N 2)
Average behavior – O(N)
 Sorting techniques are categorized into 2 types based on “Memory utilization” and are
often classified by the stability (Maintaining relative orders of records with equal keys)
of algorithms.
 Internal & External Sorting: Internal sorting takes place in a main memory of a
computer. E.g. Bubble sort, Insertion sort, Quick sort, heap sort etc. External sorting
takes place in the secondary memory of a computer, since the number objects to be
sorted is too large to fit in main memory. E.g. Merge sorting, Multiway merge,
Polyphase merge etc.
 Stable sort & Unstable sort: In stable sort, after each pass any one of element is placed
in their appropriate (i.e.) Actual position, in list. It won’t change the position in future
pass. In unstable sort, it is not maintain the stability. After the completion of execution
only, the elements are placed in their position.

Implementation of Sorting algorithms

a) Write a C program to sort the array of elements using Insertion sort.
b) Write a C program to sort the array of elements using Selection sort.
c) Write a C program to sort the array of elements using Shell sort.
d) Write a C program to sort the array of elements using Bubble sort.
e) Write a C program to sort the array of elements using Quick sort.

Procedure & Solution

a) Write a C program to sort the array of elements using Insertion sort.

#include<stdio.h>
void ins(int a[],int n)
{
int i,j,temp;
for(i=1;i<=n-1;i++)
{
temp=a[i];
for(j=i;j>=1;j--)
 UNIT II - ARRAYS AND STRINGS

{
if(temp<a[j-1])
a[j]=a[j-1];
else
break;
}
a[j]=temp;
}
}
void main()
{
int a[10],i,n;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
ins(a,n);
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}

b) Write a C program to sort the array of elements using Selection sort.

#include<stdio.h>
void sel(int a[],int n)
{
int i,j,temp,pos;
for(i=0;i<n-1;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(a[pos]>a[j])
pos=j;
}
if(pos!=i)
{
temp=a[i];
a[i]=a[pos];
a[pos]=temp;
}
}
}
void main()
{
int a[10],i,n;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
 UNIT II - ARRAYS AND STRINGS

for(i=0;i<n;i++)
scanf("%d",&a[i]);
sel(a,n);
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}

c) Write a C program to sort the array of elements using Shell sort.

#include<stdio.h>
void shel(int a[],int n)
{
int i,j,k,temp;
for(k=n/2;k>0;k=k/2)
{
for(i=k;i<n;i++)
{
temp=a[i];
for(j=i;j>=k;j=j-k)
{
if(a[j-k]>temp)
a[j]=a[j-k];
else
break;
}
a[j]=temp;
}
}
}
void main()
{
int a[10],i,n;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
shel(a,n);
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}

d) Write a C program to sort the array of elements using Bubble sort.

#include<stdio.h>
void bub(int a[],int n)
 UNIT II - ARRAYS AND STRINGS

{
int i,j,temp;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
void main()
{
int a[10],i,n;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bub(a,n);
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}

e) Write a C program to sort the array of elements using Quick sort.

#include<stdio.h>
void qsort(int a[],int left,int right)
{
int i,j,pivot,temp;
if(left<right)
{
pivot=left;
i=left+1;
j=right;
while(i<j)
{
while(a[pivot]>=a[i])
i=i+1;
while(a[pivot]<a[j])
j=j-1;
if(a[i]>a[pivot]&&a[j]<a[pivot]&&i<j)
{
temp=a[i];
a[i]=a[j];
 UNIT II - ARRAYS AND STRINGS

a[j]=temp;
}
}
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
qsort(a,left,j-1);
qsort(a,j+1,right);
}
}
void main()
{
int a[10],i,n;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
qsort(a,0,n-1);
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}

Linear Search Techniques

Linear search is the simplest search algorithm also referred as sequential search. It is a method
for finding a particular value in a list that checks each element in sequence until the desired
element is found or the list is exhausted. The list need not be ordered.

It is a special case of brute-force search. Its worst case cost is proportional to the number of
elements in the list.

If the list has large number of elements then it is not an appropriate method. Binary search or
Hashing methods have faster search times but require additional resources to attain that speed.

#include <stdio.h>
void main()
{
int i, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n);  
for (i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("Enter value to find\n");
scanf("%d", &search);
for (i = 0; i < n; i++)
{
if(array[i]==search)
{
 UNIT II - ARRAYS AND STRINGS

printf("%d found at location %d.\n", search, i+1);

break;
}
}
if(i==n)
{
printf("Not found! %d is not present in the list.\n", search);
}
}

Binary Search Techniques

Binary search is also referred as half-interval search algorithm. It finds the position of a
specified input value (the search "key") within sorted array. For binary search, the array should
be arranged in ascending or descending order. A binary search is a divide and conquer search
algorithm.

In each step, the algorithm compares the search key value with the key value of the middle
element of the array. If the keys match, then a matching element has been found and its index, or
position, is returned.

Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its
action on the sub-array to the left of the middle element or, if the search key is greater, on the
sub-array to the right. If the remaining array to be searched is empty, then the key cannot be
found in the array and a special "not found" indication is returned.

A binary search halves the number of elements to be checked in each iteration. So locating an
item takes logarithmic time.

#include <stdio.h>
 void main()
{
int c, first, last, middle, n, search, array[100];
  printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n); //to be in sorted order or call insertion sort
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter value to find\n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last)
{
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search)
{
printf("%d found at location %d.\n", search, middle+1);
 UNIT II - ARRAYS AND STRINGS

break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);
}

Complexity of Sorting and Searching algorithms

Time Time Time Space

Data
Algorithm Complexity: Complexity: Complexity: Complexity:
Structure
Best Average Worst Worst
Quick Sort Array O(n log(n)) O(n log(n)) O(n )
2
O(log(n))
Merge sort Array O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Heap sort Array O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Bubble sort Array O(n) O(n2) O(n2) O(1)
Insertion
Array O(n) O(n2) O(n2) O(1)
sort
Selection
Array O(n2) O(n2) O(n2) O(1)
sort
Linear
Array O(1) O(n) O(n) O(1)
search
Binary
Array O(log n) O(log n) O(log n) O(log n)
search