Unit-IV

Module – 4: (Arrays & Basic Algorithms)

Arrays: Array notation and representation, manipulating array elements, using multi dimensional arrays. Character
arrays and strings, Structure, union, enumerated data types, Array of structures, passing arrays to functions.
Basic Algorithms: Searching &Basic Sorting Algorithms (Bubble, Insertion and Selection), Finding roots of equations,
Notion of order of complexity.

Introduction
 The fundamental data types, namely char, int, float, double are used to store only one value at any
given time.
 Hence these fundamental data types can handle limited amounts of data.
 In some cases, we need to handle large volume of data in terms of reading, processing and printing.
 To process such large amounts of data, we need a powerful data type that would facilitate efficient
storing, accessing and manipulation of data items.
 “C” supports a derived data type known as array that can be used for suchapplications.

Arrays:

 An array is a collection of similar data type or homogenous data types.

 It allocates sequential memory locations.
 Individual values are called as elements.
 It is simply grouping of like type data such as list of numbers, list of names.

Some examples where arrays can be used are

1) List of temperatures recorded every hour in a day, or a month, or ayear.
2) List of employees in an organization.
3) List of products and their cost sold by a store.
4) Test scores of a class of students
5) List of customers and their telephonenumbers.

Types of Arrays:

 One – dimensional arrays (1-D)

 Two – dimensional arrays (2-D)
 Multidimensional arrays

ONE – DIMENSIONAL ARRAY (1-D)

A list of items can be given one variable name using only one subscript and such a variable is called a single
subscripted variable or a one – dimensional array.
int a[5];

float b[7];

char c[7];

Declaration of One-Dimensional Arrays:

 Like any other variables, arrays must be declared before they are used. The general

form of array declaration is

 Syntax:
<datatype> <array_name>[size of array];

 The datatype specifies the type of element that will be contained in the array, such as int, float, or char.

 The size indicates the maximum number of elements that can be stored inside the array.

 The size of array should be a constant value

Examples: float height[50];

 Declares the height to be an array containing 50 real elements. Any subscripts 0 to 49 are valid.

int group[10];

 Declares the group as an array to contain a maximum of 10 integer values.

 To represent a set of five numbers, say (35, 40, 20, 57, 19) by an array variable num. We may declare
the variable num as

int num[5];
 Hence the computer reserves five storage locations as shown
num[0] num[1] num[2] num[3] num[4]
num 35 40 20 57 19

 The values to the array elements can be assigned as

num[0] = 35;

num[1] = 40;

num[2] = 20;

num[3] = 57;

num[4] = 19;

Valid Statements:

 a = number[0] + 10;
 number[4] = number[0] + number[2];

Example-1: Write a program using a single dimensional array to read and display the array elements.
#include<stdio.h>
#include<conio.h>
void main( )
{
int i, x[10];
printf("Enter 10 real numbers: \n");
for (i=0; i <10; i++)
{
scanf(" %d ", &x[i]);
 }
printf("The array elements are:"); Output:
for(i=0; i < 10; i++) Enter 10 real numbers: 1 2 3 4 5 6 7 8 9 10
The array elements are: 1 2 3 4 5 6 7 8 9 10
{
printf("%d \t", x[i]);
}
getch();
}

Initialization of One – Dimensional Arrays:

 After an array is declared, its elements must be initialized. Otherwise they will contain “garbage”
value.
 The elements of an array can be initialized by using an initialization list (comma separated list).
 An initializer is an expression that determines the initial value of elements of array.

The general form of initialization of array is

datatype array_name[size] = {list of values};

Example: int number[3] = {1,2,4};
i.e. we will declare the variable number as an array of size 3 and will assign 1,2 and 4 to number[0],
number[1] and number[2] respectively0.
Example-2: Write a C program to input 10 integer numbers and print their average, minimum and maximum.

#include<stdio.h>
#include<conio.h>
void main( )
{
int a[10],i,small,large;
float sum,avg ;
clrscr();
printf(“ \n Array elements are \n”); for(i=0; i<=9; i++)
scanf(“ %f ”, &a[ i ]);
sum=a[0];
large = a[0];
small = a[0]; Output:
Array elements are: 1 2 3 4 5 6 7 8 9 10
for(i=1; i<=9; i++)
Average is 5.5
{ Largest element in array is 10
sum=sum+a[i]; Smallest element in array is 1
if(a[ i ] > large)
large = a[ i ];
else if( a[ i ] < small)
small = a[ i ];
}
avg=sum/10;
printf(“\n Average is %f \n”, avg);
printf(“\n Largest element in array is %f\n”, large);
printf(“ \n smallest element in array is %f \n”, small);
getch( );
}
Example 3: Given an array of 20 integers. Write a program in C to search for a given integer in that array.
#include<stdio.h>
#include<conio.h>
int main()
{
int a[10],i,n,c=0;
printf("\nEnter the elements of the array: ");
for(i=0; i<=19; i++)
{
scanf("%d",&a[i]);
}
printf("\nEnter the number to be search: ");
scanf("%d",&n);
for(i=0; i<=19; i++)
{
if(a[i]==n)
{
c=1;
break;
}
}
if(c==0)
printf("\nThe %d number is not in the list",n);
else
printf("\nThe %d number is found at postion %d",n,i+1);
return 0;
getch();
} Output:
Enter the elements of the
array: 1
2
3
4
5
5
6
6
7
8
65
1
2
2
3
3
3
5
9
4
Enter the number to be search: 65
The 65 number is found at position 11
Assignment

1. Write a program in C to print the elements of an array in reverse order.

2. Write a program in C to calculate sum of an array.
3. Write a program in C to calculate average of an array.
4. Write a program in C to find the largest element of an array.
 TWO DIMENSIONAL ARRAYS:

 A two-dimensional array has its elements in a rectangular grid of rows and columns.
 The elements of a two-dimensional array can be accessed by using a row index (i.e. row number)
and column index (i.e. column number).
 Both the number index and column index are required to select an element of a two-dimensional
array.
 A two-dimensional array is popularly known as a matrix.

int a[4][5]={1,5,4,7,5,8};

Declaration of a two-dimensional Array:

 A two-dimensional array declaration consists of a type specifier (i.e. element type) and identifier
(i.e. name of an array), row size specifier (i.e. number of rows in an array) and column size
specifier (i.e. number of columns in each row).
 The size specifier is enclosed within square brackets.

Example

int arr[2][3]; //arr is an integer type array of 2 rows and 3 columns.

float ab[5][1];// ab is floating point type array of 5X1.

Char name[2][3]; //name is a character type array of 2 rows and 3 columns.

Initialization of two–Dimensional Arrays:

 Like the one-dimensional arrays, two-dimensional arrays may be initialized by following

their declaration with a list of initial values enclosed in braces.
1 2 3
int table[2] [3] = {1,2,3,4,5};
4 5 0
 This initializes the elements of first row to zero and the second row to one.
 This initialization is done row by row.
 The above statement can be equivalently written as int table [2][3] = {{1,2,3}, {4,5}};

(1) Write a program to display the elements of two-dimensional array.

#include<stdio.h>
Output:

void main( ) Elements of an Array

{
int i,j; 1 2 3
int a[3][3] ={{1,2,3},{4,5,6},{7,8,9}};
printf("elements of an array \n \n"); 4 5 6
for( i=0; i<3; i++) 7 8 9
{
for ( j=0; j<3; j++)
{
 printf ("%d\t", a[i][j]);

}
printf("\n");

}
}

(2) Write a program in C to read the elements of the matrix of 3x3 & transpose its element.

# include<stdio.h>
# include<conio.h>
void main( )
{
int i,j, a[3][3], b[3][3];
clrscr( );
printf(“\n Enter Elements of matrix A: \n”);
for( i=0; i < 3; i++)
{
for( j=0; j<3; j++)
{
scanf(“ %d ”, &a[ i ][ j ]);

}
}
/* transposing logic simply copying one matrix elements to another in reverse order */
for( i=0; i < 3; i++)
{
for( j=0; j < 3; j++) Output:
{ Enter Elements of matrix A:
b[ j ][ i ]=a[ i ][ j ]; 3 5 8
} 4 8 5
} 8 5 4
printf(“ \n The Matrix Transpose is \ n”); The Matrix Transpose is
for( i=0; i<3; i++) 3 4 8
{ 5 8 5
for( j=0; j<3; j++) 8 5 4
{
printf(“%d\t”, b[ i ][ j ]);
}
printf (“ \ n”);
}
getch( );
}

(3) Write a program in C to perform addition and subtraction of two matrices of 3X3.
# include<stdio.h>
# include<conio.h>
void main( )
{
int i,j, a[3][3], b[3][3],sum[3][3]={0},subt[3][3]={0};
clrscr( );
printf(“Enter Elements of Matrix of A: \n”);
for( i=0; i < 3; i++)
{
 for( j=0; j<3; j++)
{
scanf(“ %d ”, &a[i][j]);

}
}

printf(“Enter Elements of Matrix of B: \ n”);

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

{
for( j=0; j < 3; j++) Output:
{ Enter Elements of Matrix of A:
scanf(“ %d ”, &b[i][j]);
} 4 5 8
} 2 9 8
2 9 4
printf(“\n Matrix Addition \n”);
for( i=0; i < 3; i++) Enter Elements of Matrix of B:
{ 1 3 5
for( j=0; j < 3; j++) 0 5 4
{ 6 7 2
sum[i][j]= a[i][j] + b[i][j];
printf(“%d\t”,sum[i][j]);
}
printf (“ \n”); Matrix Addition
}
printf(“n Matrix Subtraction/Difference \n”); 5 8 13
for( i=0; i < 3; i++) 2 14 12
{ 8 16 6
for( j=0; j < 3; j++)
{ Matrix Subtraction
Subt[i][j]= a[i ][j] – b[i][j]; 3 2 3
printf(“%d\t”,subt[i][j]);
2 4 4
}
printf(“\n”); -4 2 2
}
getch( );
}

(4) Write a program in C to perform multiplication of two matrices of 3x3.

# include<stdio.h> Output:
# include<conio.h> Enter Element of Matrix of A:
void main( ) 4 5 8
{ 2 9 8
int i,j,k,a[3][3], b[3][3],multi[3][3]={0}; 2 9 4
clrscr( ); Enter Elements of Matrix of B:
printf(“Enter Element of Matrix of A: \n”); 1 3 5
for( i=0; i < 3; i++) 0 5 4
{ 6 7 2
for( j=0; j<3; j++) Matrix Multiplication
{ 52 93 56
scanf(“ %d ”, &a[i][j]); 50 107 62
}
26 79 54
}
 printf(“Enter Elements of Matrix of B: \ n”);
for( i=0; i < 3; i++)
{
for( j=0; j < 3; j++)
{

scanf(“ %d ”, &b[i][j]);
}
}
printf(“\n Matrix Multiplication \n”);

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

{
for( j=0; j < 3; j++)
{
for( k=0; k < 3; k++)
{
multi[i][j]=multi[i][j]+a[i][k]*b[k][j];
}
}
}

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

{
for( j=0; j < 3; j++)
{
printf(“%d\t”,multi[i][j]);
}
printf(“\n”);
}

getch();

}
C Structures
Structure is a user-defined data type in C language which allows us to combine data of different types
together. Structure helps to construct a complex data type which is more meaningful. It is somewhat
similar to an Array, but an array holds data of similar type only. But structure on the other hand, can
store data of any type, which is practical more useful.
For example: If I have to write a program to store Student information, which will have Student's
name, age, branch, permanent address, father's name etc, which included string values, integer
values etc, how can I use arrays for this problem, I will require something which can hold data of
different types together. In structure, data is stored in form of records.

Defining a structure
struct keyword is used to define a structure. struct defines a new data type which is a collection of
primary and derived datatypes.
Syntax: struct structure_name
{
member variable1;
member variable2;
member variable3;
……..
} structure variables;
As you can see in the syntax above, we start with the struct keyword, then provide your structure a
name, then inside the curly braces, we have to mention all the member variables, which are nothing
but normal C language variables of different types like int, float, array etc.
After the closing curly brace, we can specify one or more structure variables, again this is optional.
Note: The closing curly brace in the structure type declaration must be followed by a semicolon( ;).

Example of Structure
struct Student

char name[25];

int age;

char branch[10];

char gender; // F for female and M for male

};

Here struct Student declares a structure to hold the details of a student which consists of 4 data
fields, namely name, age, branch and gender. These fields are called structure elements or
members. each member can have different data type, like in this case, name is an array of char type
and age is of int type etc. Student is the name of the structure and is called as the structure tag.

Declaring Structure Variables

It is possible to declare variables of a structure, either along with structure definition or after the
structure is defined. Structure variable declaration is similar to the declaration of any normal variable
of any other data type. Structure variables can be declared in following two ways:
1) Declaring Structure variables separately
struct Student

char name[25];

int age;

char branch[10];

//F for female and M for male

char gender;

};

struct Student S1, S2; //declaring variables of struct Student

2) Declaring Structure variables with structure definition

struct Student

char name[25];

int age;

char branch[10];

//F for female and M for male

char gender;

}S1, S2;

Here S1 and S2 are variables of structure Student. However this approach is not much recommended.

Accessing Structure Members

Structure members can be accessed and assigned values in a number of ways. Structure members
have no meaning individually without the structure. In order to assign a value to any structure
member, the member name must be linked with the structure variable using a dot . operator also
called period or member access operator.
For example:
#include<stdio.h>

#include<string.h>

struct Student

char name[25];

int age;

char branch[10];

//F for female and M for male

char gender;

};

int main()

struct Student s1; /* s1 is a variable of Student type and age is a member of Student */

s1.age = 18;

strcpy(s1.name, "Viraaj"); /* using string function to add name */

printf("Name of Student 1: %s\n", s1.name); /* displaying the stored values */

printf("Age of Student 1: %d\n", s1.age);

return 0;

Ouptput: Name of Student 1: Viraaj

Age of Student 1: 18

We can also use scanf() to give values to structure members through terminal.
scanf(" %s ", s1.name);

scanf(" %d ", &s1.age);

Structure Initialization
Like a variable of any other datatype, structure variable can also be initialized at compile time.
struct Patient

float height;

int weight;
 int age;

};

struct Patient p1 = { 180.75 , 73, 23 }; //initialization

or,
struct Patient p1;

p1.height = 180.75; //initialization of each member separately

p1.weight = 73;

p1.age = 23;

Array of Structure
We can also declare an array of structure variables. in which each element of the array will represent
a structure variable. Example : struct employee emp[5];
The below program defines an array emp of size 5. Each element of the array emp is of type Employee.
#include<stdio.h>

struct Employee

char ename[10];

int sal;

};

struct Employee emp[5];

int i, j;

void ask()

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

printf("\nEnter %dst Employee record:\n", i+1);

printf("\nEmployee name:\t");

scanf("%s", emp[i].ename);

printf("\nEnter Salary:\t");

scanf("%d", &emp[i].sal);

}
 printf("\nDisplaying Employee record:\n");

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

printf("\nEmployee name is %s", emp[i].ename);

printf("\nSlary is %d", emp[i].sal);

void main()

ask();

Nested Structures
Nesting of structures, is also permitted in C language. Nested structures means, that one structure
has another stucture as member variable.
Example:
struct Student

char[30] name;

int age;

/* here Address is a structure */

struct Address

char[50] locality;

char[50] city;

int pincode;

}addr;

};

Structure as Function Arguments

We can pass a structure as a function argument just like we pass any other variable or an array as a
function argument.
Example:
#include<stdio.h>

struct Student

char name[10];

int roll;

};

void show(struct Student st);

void main()

struct Student std;

printf("\nEnter Student record:\n");

printf("\nStudent name:\t");

scanf("%s", std.name);

printf("\nEnter Student rollno.:\t");

scanf("%d", &std.roll);

show(std);

void show(struct Student st)

printf("\nstudent name is %s", st.name);

printf("\nroll is %d", st.roll);

}
C Unions
Unions are conceptually similar to structures. The syntax to declare/define a union is
also similar to that of a structure. The only differences are in terms of storage.
In structure each member has its own storage location, whereas all members
of union uses a single shared memory location which is equal to the size of its largest
data member.

This implies that although a union may contain many members of different types, it can
not handle all the members at the same time. A union is declared using
the union keyword.
union item

int m;

float x;

char c;

}It1;
This declares a variable It1 of type union item. This union contains three members
each with a different data type. However only one of them can be used at a time. This is
due to the fact that only one location is allocated for all the union variables, irrespective
of their size. The compiler allocates the storage that is large enough to hold the largest
variable type in the union.
In the union declared above the member x requires 4 bytes which is largest amongst
the members for a 16-bit machine. Other members of union will share the same
memory address.

Accessing a Union Member in C

Syntax for accessing any union member is similar to accessing structure members,
union test

int a;

float b;

char c;

}t;

t.a; //to access members of union t

t.b;

t.c;

Time for an Example

#include <stdio.h>

union item

int a;

float b;

char ch;

};
int main( )

union item it;

it.a = 12;

it.b = 20.2;

it.ch = 'z';

printf("%d\n", it.a);

printf("%f\n", it.b);

printf("%c\n", it.ch);

return 0;

Output:

-26426

20.1999

As you can see here, the values of a and b get corrupted and only variable c prints the
expected result. This is because in union, the memory is shared among different data
types. Hence, the only member whose value is currently stored will have the memory.
In the above example, value of the variable c was stored at last, hence the value of
other variables is lost.
 Enum in C

Enumeration is a user defined datatype in C language. It is used to assign names to the integral
constants which makes a program easy to read and maintain. The keyword “enum” is used to declare
an enumeration.

Here is the syntax of enum in C language,

enum enum_name{const1, const2, ....... };

The enum keyword is also used to define the variables of enum type. There are two ways to define the
variables of enum type as follows.

enum week{sunday, monday, tuesday, wednesday, thursday, friday, saturday};

enum week day;

Here is an example of enum in C language,

Example
Live Demo

#include<stdio.h>
enum week{Mon=10, Tue, Wed, Thur, Fri=10, Sat=16, Sun};
enum day{Mond, Tues, Wedn, Thurs, Frid=18, Satu=11, Sund};
int main() {
printf("The value of enum week: %d\t%d\t%d\t%d\t%d\t%d\t%d\n\n",Mon , Tue, Wed, Thur, Fri,
printf("The default value of enum day: %d\t%d\t%d\t%d\t%d\t%d\t%d",Mond , Tues, Wedn, Thur
return 0;
}

Output
The value of enum week: 10 11 12 13 10 16 17
The default value of enum day: 0 1 2 3 18 11 12

In the above program, two enums are declared as week and day outside the main() function. In the
main() function, the values of enum elements are printed.

enum week{Mon=10, Tue, Wed, Thur, Fri=10, Sat=16, Sun};

enum day{Mond, Tues, Wedn, Thurs, Frid=18, Satu=11, Sund};
int main() {
printf("The value of enum week: %d\t%d\t%d\t%d\t%d\t%d\t%d\n\n",Mon , Tue, Wed, Thur, Fri,
Fri
printf("The default value of enum day: %d\t%d\t%d\t%d\t%d\t%d\t%d",Mond , Tues, Wedn, Thur
Thu
}
Introduction to SEARCHING
Searching means to find whether a particular value is present in an array or not. If the value is
present in the array, then searching is said to be successful and the searching process gives the
location of that value in the array. However, if the value is not present in the array, the searching
process displays a message and in this case searching is said to be unsuccessful.
There are two popular methods for searching the array elements:
Linear search and Binary search
The algorithm that should be used depends entirely on how the values are organized in the array.
For example, if the elements of the array are arranged in ascending order, then binary search
should be used.
Linear Search
Linear search, also called as sequential search, is a very simple method used for searching an
array for a particular value. It works by comparing the value to be searched with every element
of the array one by one in a sequence until a match is found. Linear search is mostly used to
search an unordered list of elements (array in which data elements are not sorted). For example,
if an array A[] is declared and initialized as, int A[] = {10, 8, 2, 7, 3, 4, 9, 1, 6, 5}; and the value
to be searched is VAL = 7, then searching means to find whether the value ‘7’ is present in the
array or not. If yes, then it returns the position of its occurrence. Here, POS = 3 (index starting
from 0).
Figure 14.1 shows the algorithm for linear search. In Steps 1 and 2 of the algorithm, we initialize
the value of POS and I. In Step 3, a while loop is executed that would be executed till I is less
than N (total number of elements in the array). In Step 4, a check is made to see if a match is
found between the current array element and VAL. If a match is found, then the position of the
array element is printed, else the value of I is incremented to match the next element with VAL.
However, if all the array elements have been compared with VAL and no match is found, then it
means that VAL is not present in the array.

LINEAR_SEARCH(A, N, VAL)
Step 1: [INITIALIZE] SET POS = -1
Step 2: [INITIALIZE] SET I = 1
Step 3: Repeat Step 4 while I<=N
Step 4: IF A[I] = VAL
SET POS = I
PRINT POS
Go to Step 6
[END OF IF]
SET I = I + 1
[END OF LOOP]
Step 5: IF POS = –1
PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
[END OF IF]
Step 6: EXIT

Figure 14.1 Algorithm for linear search

Write a program to Implement linear search.
#include <stdio.h>
#include <conio.h>
int main ()
{
int arr[10],i, n,num,found=0,pos= -1;
clrscr();
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
printf("\n Enter the elements: ");
for(i=0; i<n; i++)
scanf("%d", &arr[i]);
printf("\n Enter the number that has to be searched : ");
scanf("%d", &num);
for(i=0; i<n; i++)
{
if(arr[i]==num)
{
found=1;
pos=I;
printf(“\n %d is found in the array at position=%d”,num,i);
break;
}
}
if(found==0)
printf(“\n %d does not exist in the array ”,num);
getch();
return 0;
}

Binary Search
Binary search is a searching algorithm that works efficiently with a sorted list. The mechanism
of binary search can be better understood by an analogy of a telephone directory. When we are
searching for a particular name in a directory, we first open the directory from the middle and
then decide whether to look for the name in the first part of the directory or in the second part of
the directory. Again, we open some page in the middle and the whole process is repeated until
we finally find the right name.
Take another analogy. How do we find words in a dictionary? We first open the dictionary
somewhere in the middle. Then, we compare the first word on that page with the desired word
whose meaning we are looking for. If the desired word comes before the word on the page, we
look in the first half of the dictionary, else we look in the second half. Again, we open a page in
the first half of the dictionary and compare the first word on that page with the desired word and
repeat the same procedure until we finally get the word. The same mechanism is applied in the
binary search.
Now, let us consider how this mechanism is applied to search for a value in a sorted array.
Consider an array A[] that is declared and initialized as int A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
and the value to be searched is VAL = 9. The algorithm will proceed in the following manner.
BEG = 0, END = 10, MID = (0 + 10)/2 = 5
Now, VAL = 9 and A[MID] = A[5] = 5
A[5] is less than VAL, therefore, we now search for the value in the second half of the array. So,
we change the values of BEG and MID. Now, BEG = MID + 1 = 6, END = 10, MID = (6 + 10)/2
=16/2 = 8 VAL = 9 and A[MID] = A[8] = 8
A[8] is less than VAL, therefore, we now search for the value in the second half of the segment.
So, again we change the values of BEG and MID.Now, BEG = MID + 1 = 9, END = 10, MID =
(9 + 10)/2 = 9 Now, VAL = 9 and A[MID] = 9.
In this algorithm, we see that BEG and END are the beginning and ending positions of the
segment that we are looking to search for the element. MID is calculated as (BEG + END)/2.
Initially, BEG =lower_bound and END = upper_bound. The algorithm will terminate when
A[MID] = VAL. When the algorithm ends, we will set POS = MID. POS is the position at which
the value is present in the array.However, if VAL is not equal to A[MID], then the values of
BEG, END, and MID will be changed depending on whether VAL is smaller or greater than
A[MID].
(a) If VAL < A[MID], then VAL will be present in the left segment of the array. So, the value of
END will be changed as END = MID – 1.
(b) If VAL > A[MID], then VAL will be present in the right segment of the array. So, the value
of BEG will be changed as BEG = MID + 1.
Finally, if VAL is not present in the array, then eventually, END will be less than BEG. When
this happens, the algorithm will terminate and the search will be unsuccessful.
Figure 14.2 shows the algorithm for binary search.
In Step 1, we initialize the value of variables, BEG, END, and POS. In Step 2, a while loop is
executed until BEG is less than or equal to END. In Step 3, the value of MID is calculated.
In Step 4, we check if the array value at MID is equal to VAL (item to be searched in the array).
If a match is found, then the value of POS is printed and the algorithm exits. However, if a match
is not found, and if the value of A[MID] is greater than VAL, the value of END is modified,
otherwise if A[MID] is greater than VAL, then the value of BEG is altered. In Step 5, if the value
of POS = –1, then VAL is not present in the array and an appropriate message is printed on the
screen before the algorithm exits.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

Step 1: [INITIALIZE] SET BEG = lower_bound END = upper_bound, POS = - 1
Step 2: Repeat Steps 3 and 4 while BEG <= END
Step 3: SET MID = (BEG + END)/2
Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID - 1
ELSE
SET BEG = MID + 1
 [END OF IF]
[END OF LOOP]
Step 5: IF POS = -1
PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
[END OF IF]
Step 6: EXIT
Figure 14.2 Algorithm for binary search

Write a program to Implement binary search.

#include <stdio.h>
#include <conio.h>
int main ()
{
int arr[10],i, n,num,found=0,pos= -1,beg,end,mid;
clrscr();
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
printf("\n Enter the elements: ");
for(i=0; i<n; i++)
scanf("%d", &arr[i]);
printf("\n Enter the number that has to be searched : ");
scanf("%d", &num);
beg=0,end=n-1;
while(beg<=end)
{
mid=(beg+end)/2;
if(arr[mid]==num)
{
printf(“\n %d is present in the array at position=%d”,num,mid);
found=1;
break;
}
if(arr[mid]>num)
end=mid-1;
else if(arr[mid]<num)
beg=mid+1;
}
if(beg>end && found=0)
printf(“\n %d does not exist in the array ”,num);
getch();
return 0;
}
INTRODUCTION TO SORTING
Sorting means arranging the elements of an array so that they are placed in some relevant order
which may be either ascending or descending. That is, if A is an array, then the elements of A are
arranged in a sorted order (ascending order) in such a way that A[0] < A[1] < A[2] < ..... < A[N].
For example, if we have an array that is declared and initialized as int A[] = {21, 34, 11, 9, 1, 0,
22}; Then the sorted array (ascending order) can be given as:
A[] = {0, 1, 9, 11, 21, 22, 34;
A sorting algorithm is defined as an algorithm that puts the elements of a list in a certain order,
which can be either numerical order, lexicographical order, or any user-defined order.
There are two types of sorting:
• Internal sorting which deals with sorting the data stored in the computer’s memory.
• External sorting which deals with sorting the data stored in files. External sorting is applied
when there is voluminous data that cannot be stored in the memory.

BUBBLE SORT
Bubble sort is a very simple method that sorts the array elements by repeatedly moving the
largest element to the highest index position of the array segment (in case of arranging elements
in ascending order). In bubble sorting, consecutive adjacent pairs of elements in the array are
compared with each other. If the element at the lower index is greater than the element at the
higher index, the two elements are interchanged so that the element is placed before the bigger
one. This process will continue till the list of unsorted elements exhausts.This procedure of
sorting is called bubble sorting because elements ‘bubble’ to the top of the list. Note that at the
end of the first pass, the largest element in the list will be placed at its proper position (i.e., at the
end of the list).
Note If the elements are to be sorted in descending order, then in first pass the smallest element is moved
to the highest index of the array.

Technique
The basic methodology of the working of bubble sort is given as follows:
(a) In Pass 1, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared
with A[3], and so on. Finally, A[N–2] is compared with A[N–1]. Pass 1 involves n–1
comparisons and places the biggest element at the highest index of the array.
(b) In Pass 2, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared
with A[3], and so on. Finally, A[N–3] is compared with A[N–2]. Pass 2 involves n–2
comparisons and places the second biggest element at the second highest index of the array.
(c) In Pass 3, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is compared
with A[3], and so on. Finally, A[N–4] is compared with A[N–3]. Pass 3 involves n–3
comparisons and places the third biggest element at the third highest index of the array.
(d) In Pass n–1, A[0] and A[1] are compared so that A[0]<A[1]. After this step, all the elements
of the array are arranged in ascending order.
Example: To discuss bubble sort in detail,let us consider an array A[] that has the following
elements:
A[] = {30, 52, 29, 87, 63, 27, 19, 54}
Pass 1:
(a) Compare 30 and 52. Since 30 < 52, no swapping is done.
(b) Compare 52 and 29. Since 52 > 29, swapping is done.
 30, 29, 52, 87, 63, 27, 19, 54
(c) Compare 52 and 87. Since 52 < 87, no swapping is done.
(d) Compare 87 and 63. Since 87 > 63, swapping is done.
30, 29, 52, 63, 87, 27, 19, 54
(e) Compare 87 and 27. Since 87 > 27, swapping is done.
30, 29, 52, 63, 27, 87, 19, 54
(f) Compare 87 and 19. Since 87 > 19, swapping is done.
30, 29, 52, 63, 27, 19, 87, 54
(g) Compare 87 and 54. Since 87 > 54, swapping is done.
30, 29, 52, 63, 27, 19, 54, 87
Observe that after the end of the first pass, the largest element is placed at the highest index of
the array. All the other elements are still unsorted.
Pass 2:
(a) Compare 30 and 29. Since 30 > 29, swapping is done.
29, 30, 52, 63, 27, 19, 54, 87
(b) Compare 30 and 52. Since 30 < 52, no swapping is done.
(c) Compare 52 and 63. Since 52 < 63, no swapping is done.
(d) Compare 63 and 27. Since 63 > 27, swapping is done.
29, 30, 52, 27, 63, 19, 54, 87
(e) Compare 63 and 19. Since 63 > 19, swapping is done.
29, 30, 52, 27, 19, 63, 54, 87
(f) Compare 63 and 54. Since 63 > 54, swapping is done.
29, 30, 52, 27, 19, 54, 63, 87
Observe that after the end of the second pass, the second largest element is placed at the second
highest index of the array. All the other elements are still unsorted.
Pass 3:
(a) Compare 29 and 30. Since 29 < 30, no swapping is done.
(b) Compare 30 and 52. Since 30 < 52, no swapping is done.
(c) Compare 52 and 27. Since 52 > 27, swapping is done.
29, 30, 27, 52, 19, 54, 63, 87
(d) Compare 52 and 19. Since 52 > 19, swapping is done.
29, 30, 27, 19, 52, 54, 63, 87
(e) Compare 52 and 54. Since 52 < 54, no swapping is done.
Observe that after the end of the third pass, the third largest element is placed at the third highest
index of the array. All the other elements are still unsorted.
Pass 4:
(a) Compare 29 and 30. Since 29 < 30, no swapping is done.
(b) Compare 30 and 27. Since 30 > 27, swapping is done.
29, 27, 30, 19, 52, 54, 63, 87
(c) Compare 30 and 19. Since 30 > 19, swapping is done.
29, 27, 19, 30, 52, 54, 63, 87
(d) Compare 30 and 52. Since 30 < 52, no swapping is done.
Observe that after the end of the fourth pass, the fourth largest element is placed at the fourth
highest index of the array. All the other elements are still unsorted.
Pass 5:
(a) Compare 29 and 27. Since 29 > 27, swapping is done.
 27, 29, 19, 30, 52, 54, 63, 87
(b) Compare 29 and 19. Since 29 > 19, swapping is done.
27, 19, 29, 30, 52, 54, 63, 87
(c) Compare 29 and 30. Since 29 < 30, no swapping is done.
Observe that after the end of the fifth pass, the fifth largest element is placed at the fifth highest
index of the array. All the other elements are still unsorted.
Pass 6:
(a) Compare 27 and 19. Since 27 > 19, swapping is done.
19, 27, 29, 30, 52, 54, 63, 87
(b) Compare 27 and 29. Since 27 < 29, no swapping is done.
Observe that after the end of the sixth pass, the sixth largest element is placed at the sixth largest
index of the array. All the other elements are still unsorted.
Pass 7:
(a) Compare 19 and 27. Since 19 < 27, no swapping is done.
Figure 14.6 shows the algorithm for bubble sort. In this algorithm, the outer loop is for the total
number of passes which is N–1. The inner loop will be executed for every pass. However, the
frequency of the inner loop will decrease with every pass because after every pass, one element
will be in its correct position. Therefore, for every pass, the inner loop will be executed N–I
times, where N is the number of elements in the array and I is the count of the pass.
BUBBLE_SORT(A, N)
Step 1: Repeat Step 2 For 1 = to N-1
Step 2: Repeat For J = to N - I
Step 3: IF A[J] > A[J + 1]
SWAP A[J] and A[J+1]
[END OF INNER LOOP]
[END OF OUTER LOOP]
Step 4: EXIT
Figure 14.6 Algorithm for bubble sort
Write a program to enter n numbers in an array. Redisplay the array with elements being
sorted in ascending order.
#include <stdio.h>
#include <conio.h>
void main()
{
int i, n, temp, j, arr[10];
clrscr();
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
printf("\n Enter the elements: ");
for(i=0; i<n; i++)
{
scanf("%d", &arr [i]);
}
for(i=0; i<n; i++)
{
for(j=0; j<n–i–1; j++)
{
if(arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
printf("\n The array sorted in ascending order is :\n");
for(i=0;i<n;i++)
printf("%d\t", arr[i]);
getch();
}
Output
Enter the number of elements in the array : 10
Enter the elements : 8 9 6 7 5 4 2 3 1 10
The array sorted in ascending order is :
1 2 3 4 5 6 7 8 9 10
INSERTION SORT
Insertion sort is a very simple sorting algorithm in which the sorted array (or list) is built one
element at a time. We all are familiar with this technique of sorting, as we usually use it for
ordering a deck of cards while playing bridge.
The main idea behind insertion sort is that it inserts each item into its proper place in the final
list. To save memory, most implementations of the insertion sort algorithm work by moving
the current data element past the already sorted values and repeatedly interchanging it with the
preceding value until it is in its correct place. Insertion sort is less efficient as compared to other
more advanced algorithms such as quick sort, heap sort, and merge sort.
Technique
Insertion sort works as follows:
• The array of values to be sorted is divided into two sets. One that stores sorted values and
another that contains unsorted values.
• The sorting algorithm will proceed until there are elements in the unsorted set.
• Suppose there are n elements in the array. Initially, the element with index 0 (assuming LB
=0) is in the sorted set. Rest of the elements are in the unsorted set.
• The first element of the unsorted partition has array index 1 (if LB = 0).
• During each iteration of the algorithm, the first element in the unsorted set is picked up and
inserted into the correct position in the sorted set.
Initially, A[0] is the only element in the sorted set. In Pass 1, A[1] will be placed either before or
after A[0], so that the array A is sorted. In Pass 2, A[2] will be placed either before A[0], in
between A[0] and A[1], or after A[1]. In Pass 3, A[3] will be placed in its proper place. In Pass
N–1, A[N–1] will be placed in its proper place to keep the array sorted. To insert an element
A[K] in a sorted list A[0], A[1], ..., A[K–1], we need to compare A[K] with A[K–1], then with
A[K–2], A[K–3], and so on until we meet an element A[J] such that A[J] <= A[K]. In order to
insert A[K] in its correct position, we need to move elements A[K–1],A[K–2], ..., A[J] by one
position and then A[K] isinserted at the (J+1)th location. The algorithm for insertion sort is given
in Fig. 14.7.In the algorithm, Step 1 executes a for loop which will be repeated for each element
in the array. In Step 2, we store the value of the Kth element in TEMP. In Step 3, we set the Jth
index in the array. In Step 4, a for loop is executed that will create space for the new element
from the unsorted list to be stored in the list of sorted elements. Finally, in Step 5, the element is
stored at the (J+1) th location.

INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for K = 1 to N – 1
Step 2: SET TEMP = ARR[K]
Step 3: SET J = K - 1
Step 4: Repeat while TEMP <= ARR[J]
SET ARR[J + 1] = ARR[J]
SET J = J - 1
[END OF INNER LOOP]
Step 5: SET ARR[J + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
Figure 14.7 Algorithm for insertion sort
Advantages of Insertion Sort: The advantages of this sorting algorithm are as follows:
• It is easy to implement and efficient to use on small sets of data.
• It can be efficiently implemented on data sets that are already substantially sorted.
• It performs better than algorithms like selection sort and bubble sort. Insertion sort
algorithmis simpler than shell sort, with only a small trade-off in efficiency. It is over twice
as fast as the bubble sort and almost 40 per cent faster than the selection sort.
• it requires less memory space (only O(1) of additional memory space).
• It is said to be online, as it can sort a list as and when it receives new elements.

Write a program to sort an array using insertion sort algorithm.

#include <stdio.h>
#include <conio.h>
#define size 5
void insertion_sort(int arr[], int n);
void main()
{
int arr[size], i, n;
printf("\n Enter the number of elements in the array: ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0; i<n; i++)
{
scanf("%d", &arr[i]);
}
insertion_sort(arr, n);
printf("\n The sorted array is: \n");
for(i=0; i<n; i++)
printf(" %d\t", arr[i]);
getch();
}
void insertion_sort(int arr[], int n)
{
int i, j, temp;
for(i=1; i<n; i++)
{
temp = arr[i];
j = i-1;
while((temp < arr[j]) && (j>=0))
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
Output
Enter the number of elements in the array : 5
Enter the elements of the array : 500 1 20 23 76
The sorted array is : 1 20 23 76 500
SELECTION SORT
Selection sort is a sorting algorithm that has a quadratic running time complexity of O(n2),
thereby making it inefficient to be used on large lists. Although selection sort performs worse
than insertion sort algorithm, it is noted for its simplicity and also has performance advantages
over more complicated algorithms in certain situations. Selection sort is generally used for
sorting files with very large objects (records) and small keys.
Technique
Consider an array ARR with N elements. Selection sort works as follows:
First find the smallest value in the array and place it in the first position. Then, find the second
smallest value in the array and place it in the second position. Repeat this procedure until the
entire array is sorted. Therefore,
• In Pass 1, find the position POS of the smallest value in the array and then swap ARR[POS]
and ARR[0]. Thus, ARR[0] is sorted.
• In Pass 2, find the position POS of the smallest value in sub-array of N–1 elements. Swap
ARR[POS] with ARR[1]. Now, ARR[0] and ARR[1] is sorted.
• In Pass N–1, find the position POS of the smaller of the elements ARR[N–2] and ARR[N–1].
Swap ARR[POS] and ARR[N–2] so that ARR[0], ARR[1], ..., ARR[N–1] is sorted.

The algorithm for selection sort is shown in Fig. 14.8. In the algorithm, during the Kth pass, we
need to find the position POS of the smallest elements from ARR[K], ARR[K+1], ..., ARR[N].
To find the smallest element, we use a variable SMALL to hold the smallest value in the sub-
array ranging from ARR[K] to ARR[N]. Then, swap ARR[K] with ARR[POS]. This procedure
is repeated until all the elements in the array are sorted.

Advantages of Selection Sort

• It is simple and easy to implement.
• It can be used for small data sets.
• It is 60 per cent more efficient than bubble sort.
However, in case of large data sets, the efficiency of selection sort drops as compared to
insertion sort.
Write a program to sort an array using selection sort algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
int smallest(int arr[], int k, int n);
void selection_sort(int arr[], int n);
void main(int argc, char *argv[]) {
int arr[10], i, n;
printf("\n Enter the number of elements in the array: ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
selection_sort(arr, n);
printf("\n The sorted array is: \n");
for(i=0;i<n;i++)
printf(" %d\t", arr[i]);
}
int smallest(int arr[], int k, int n)
{
int pos = k, small=arr[k], i;
for(i=k+1;i<n;i++)
{
if(arr[i]< small)
{
small = arr[i];
pos = i;
}
}
return pos;
}

void selection_sort(int arr[],int n)

{
int k, pos, temp;
for(k=0;k<n;k++)
{
pos = smallest(arr, k, n);
temp = arr[k];
arr[k] = arr[pos];
arr[pos] = temp;
}
}
 Sorting Algorithms

A Sorting Algorithm is used to rearrange a given array or list elements according

to a comparison operator (less than or greater than) on the elements. The
comparison operator is used to decide the new order of element in the respective
data structure. Few sorting algorithms are:

1. Bubble sort
2. Insertion sort
3. Selection sort

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping
the adjacent elements if they are in wrong order.

Example:
First Pass:

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5
> 1.

( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm
does not swap them.

Second Pass:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Now, the array is already sorted, but our algorithm does not know if it is
completed. The algorithm needs one whole pass without any swap to know it is
sorted.

Third Pass:

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Write a C program for bubble sort.

#include<stdio.h>
#include<conio.h>
void main()

int A[20], i, j, c, n;
clrscr();
printf("How many numbers do you want to sort by Bubble Sort:");
scanf("%d",&n);
printf("\n Enter %d numbers: ",n);
for(i=0;i<n;i++)
scanf("%d",&A[i]);

for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
 {
if(A[j]>A[j+1])
{
c=A[j];
A[j]=A[j+1];
A[j+1]=c;
}
}
}
printf("\n Sorted array is \n");
for(i=0;i<n;i++)
printf("%d ",A[i]);
getch();
}

Output:

How many numbers do you want to sort by Bubble Sort: 10

Enter 10 numbers: 2 10 9 8 4 3 1 7 5 6

Sorted array is

1 2 3 4 5 6 7 8 9 10
 Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing
cards in our hands.
 C Program to sort an array in ascending order using Insertion Sort

#include <stdio.h>

void main()
{
int n, i, j, temp;
int arr[64];

printf("Enter number of elements\n");

scanf("%d", &n);

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

{
scanf("%d", &arr[i]);
}

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

{
j = i;
while ( j > 0 && arr[j-1] > arr[j])
{
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}

printf("Sorted list in ascending order:\n");

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

{
printf("%d\n", arr[i]);
}
getch();
}
 Assignment-5

1. Write an algorithm for Bubble sort. Explain its working for sorting 16,
23,12,2,43,60,54.

2. Write a program in C for Insertion sort to sort the following numbers in

descending order. 12, 23, 12, 2, 43, 60, 54.

3. Write down the difference between Bubble sort and insertion sort with
example.

4. Write a program in C to 25 in the given list by using linear search

technique.

2, 35, 12, 25, 43, 70, 54.

 Notion of order of Complexity of Algorithms
Time and Space Complexity of an Algorithm: Analyzing an algorithm means determining the
amount of resources (such as time and memory) needed to execute it. Algorithms are generally
designed to work with an arbitrary number of inputs, so the efficiency or complexity of an
algorithm is stated in terms of time and space complexity.
The time complexity of an algorithm is basically the running time of a program as a function of
the input size. Similarly, the space complexity of an algorithm is the amount of computer
memory that is required during the program execution as a function of the input size.

Notion of order of complexity: There are three notation used to describe the complexity of an
algorithm as stated below:

1. BIG O NOTATION:
If we have two different algorithms to solve the same problem where one algorithm executes in
10 iterations and the other in 20 iterations, the difference between the two algorithms is not
much. However, if the first algorithm executes in 10 iterations and the other in 1000 iterations,
then it is a matter of concern.
This factor is called efficiency of the algorithm and denoted by Big O, and is expressed as O(n).
The Big O notation, where O stands for ‘order of’, is concerned with what happens for very large
values of n. For example, if a sorting algorithm performs n2 operations to sort just n elements,
then that algorithm would be described as an O(n2) algorithm. If f(n) and g(n) are the functions
defined on a positive integer number n, then f(n) = O(g(n)) That is, f of n is Big–O of g of n if
and only if positive constants c and n exist, such that f(n) ≤ cg(n).
It means that for large amounts of data, f(n) will grow no more than a constant factor than g(n).
Hence, g provides an upper bound. Note that here c is a constant. The Big O notation provides a
strict upper bound for f(n). This means that the function f(n) can do better but not worse than the
specified value. Big O notation is simply written as f(n) ∈ O(g(n)) or as f(n) = O(g(n))
2. OMEGA NOTATION (Ω):
The Omega notation provides a tight lower bound for f(n). This means that the function can
never do better than the specified value but it may do worse.
Ω notation is simply written as, f(n) ∈ Ω(g(n)), where n is the problem size and
Ω(g(n)) = {h(n): ∃ positive constants c > 0, n0 such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n0}.
Hence, we can say that Ω(g(n)) comprises a set of all the functions h(n) that are greater than
or equal to cg(n) for all values of n ≥ n0.
3. THETA NOTATION (Q):
Theta notation provides an asymptotically tight bound for f(n). Θ notation is simply written as,
f(n) ∈ Θ(g(n)), where n is the problem size and Θ(g(n)) = {h(n): ∃ positive constants c1, c2, and
n0 such that 0 ≤ c1g(n) ≤ h(n) ≤ c2g(n), ∀ n ≥ n0}.
Hence, we can say that Θ(g(n)) comprises a set of all the functions h(n) that are between c1g(n)
and c2g(n) for all values of n ≥ n0.