Arrays
• Introduction:
• We will explain the concept of arrays using an analogy Take a situation in
which we have 20 students in a class and we have been asked to write a
program that reads and prints the marks of all these 20 students. In this
program, we will need 20 integer variables with different names.
• Now to read values for these 20 different variables, we must have 20 read
statements.
• Similarly, to print the value of these variables, we need 20 write
statements.
• If it is just a matter of 20 variables, then it might be acceptable for the
user to follow this approach.
• But would it be possible to follow this approach if we have to read and
print marks of the students
• in the entire course (say 100 students)
• in the entire college (say 500 students)
• in the entire university (say 10000 students)
• DECLARATION OF ARRAYS We have already seen that
every variable must be declared before it is used.
• The same concept is true in case of array variables
also. An array must be declared before being used.
• Declaring an array means specifying three things:
• Data type—what kind of values it can store, for
example int, char, float, double
• Name—to identify the array
• Size—the maximum number of values that the array
can hold.
• Arrays are declared using the following syntax
type name[size];
int marks[10];
Points to Remember
• Note that C does not allow declaring an array whose number of elements is not known at the compile time.
Therefore, the following array declarations are illegal in C.
int arr[];
int n, arr [n];
• Generally it is a good programming practice to define the size of an array as a symbolic constant as shown in the
following code
# include <stdio.h>
#define N 100
main()
{
int arr(N);
}
• The size of the array can be specified using an expression. However, the components of the expression must be
available for evaluation of the expression when the program is compiled.
• Therefore, the following array declarations are valid in C language.
# include <stdio.h>
define N 100
main()
{
int i=10;
int arr[N+10], my_arr[i-5+10];
}
ACCESSING THE ELEMENTS OF AN ARRAY
• // Set each element of the array to -1
int i, marks[10};
for(i=0;i<10;i++)
marks[i]=-1;
Calculating the Address of Array Elements
• Address of data element,
• A[k] = BA(A) + w(k - lower_bound)
• Here, A is the array, k is the index of the
clement for which we have to calculate the
address,
• BA is the base address of the array A, w is the
word size of one element in memory (for
example, size of int is 2), and lower_bound is
the index of the first element in the array.
Given an array int marks[{] = {99, 67, 78, 56, 88, 90, 34, 85}.
Calculate the address of marks[4] if base address = 1000.
Calculating the Length of an Array
• Length of the array is given by the number of
elements stored in it.
• The general formula to calculate the length of
the array is:
• Length = upper_bound - lower_bound + 1
• where upper_bound is the index of the last
element and lower_bound is the index of the
first clement in the array.
STORING VALUES IN ARRAYS
• When we declare an array, we are just
allocating space for the elements; no values
are stored in the array.
• There are three ways to store values in an
array—first, to initialize the array element at
the time of declaration; second, to input value
for every individual clement at the run time;
third to assign values to the individual
elements.
Initializing Arrays during Declaration
• type array_name[size] = {list of values};
• int marks(5] = {90, 82, 78, 95, 88};
• While initializing the array at the time of
declaration, the programmer may omit the size of
the array.
• For example:
int marks(] = {98, 97, 90};
Inputting Values from the Keyboard :
int i, marks[10];
for(1=0;i<10;i++)
scanf (“%d”, &marks[i]);
Assigning Values to Individual Elements :
marks[3] = 100;
Example: Copying array-1 to array-2
int i, arr1[10], arr2[10};
arr1[1] = {0,1,2,3,4,5,6,7,8,9);
for (i=0;i<10;i++)
arr2[i] = arr1[i];
OPERATIONS ON ARRAYS
• Traversing an array
• Inserting an element in an array
• Deleting an element from an array
• Merging two arrays
• Searching an clement in an array
• Sorting an array in ascending or descending
order
Traversing an Array
• Traversing an array means accessing each and every element of
the array for a specific purpose.
• If A is an array of homogeneous data elements, then traversing
the data elements can include printing every element, counting
the total number of elements, or performing any process on these
elements.
• Since an array is a linear data structure (because all its elements
form a sequence), traversing its elements is very simple and
straightforward.
• The algorithm for array traversal is given in below.
Step 1: [INITIALIZATION] SET I = lower_bound
Step 2: Repeat Steps 3 to 4 while I< = upper_bound
Step 3: Apply Process to A[I]
Step 4: SET I=I+1 [END OF Loop}
Step 5: EXIT
Write a program to print the position of the smallest of n numbers using arrays.
#include <stdio.h>
int main() {
int i, n, arr[20], small, pos;
printf("\n Enter the number of elements in the array: ");
scanf("%d", &n);
printf("\n Enter the elements:");
for(i=n; i<n; i++)
scanf(“%d" ,&arr[i});
small=arr[0];
pos=0;
for(i=1; i<n; i++)
{
if (arr[i] < small)
{
small = arr[i};
pos = i;
}
}
printf("\n The smallest element is : %d", small);
printf("\n The position of the smallest element in the array is: %d", pos);
return 0;
}
• Output :
Enter the number of elements in the array: 5 Enter
The elements: 1 2 3 4 5
The smallest element is: 1
The position of the smallest element in the array is: 0
Inserting an Element in an Array
• Inserting an element in an array means adding a new
data clement to an already existing array.
• If the element has to be insertion at the end of the
existing array, then the task Of insertion is quite simple.
• We just have to add 1 to the upper_bound and assign
the value.
• Here we assume that the memory space allocated for
the array is still available.
• For example, if an array is declared to contain 10
elements, but currently it is having only 8 elements,
then obviously there is space to accommodate two
more elements. But if it already has 10 elements, then
we will not be able to add another element to it
Algorithm to insert a new element to the end of the
array
Step 1: Set upper_bound = upper_bound+1
Step 2: Set A[upper_bound] = VAL
Step 3: EXIT
• For example, if we have an array that is declared as
int marks[60);
• The array is declared to store marks of all the students in the class,
Now suppose there are 54 students and a new student comes and is
asked to give the same test. The marks of this new student would be
stored in marks [55].
• Assuming that the student secured 68 marks, we will assign the
value as,
marks[55] = 68;
Algorithm to Insert an Element in the
Middle of an Array
• The algorithm INSERT will be declared as
INSERT (A, N, POS, VAL). The arguments are
• (a) A, the array in which the element has to
be inserted
• (b) N, the number of elements in the array
• (c) POS, the position at which the clement has
to be inserted and
• (d) VAL, the value that has to be inserted,
Algorithm to insert a new element at a
specified position
Step 1: [INITIALIZATION] SET I = N
Step 2: Repeat Steps 3 and 4 while I > = POS
Step 3: SET A [I +1] = A[I]
SET A [I + 1] = A[I]
[END OF LOOP]
Step 4: SET N =N + 1
Step 6: SET A [POS] = VAL
Step 7: EXIT
Write a program to insert a number at a given location in an array.
#include <stdio.h>
int main()
{
int i, n, num, pos, arr[10];
printf(“\n Enter the number of elements in the array: ");
scanf("%d", &n);
printf(“\n Enter the values:”);
for(i=0;icn;i++)
{
scanf("%d", &arr[i));
}
printf("\n Enter the number to be inserted: ");
scanf("%d", &num);
printf(“\n Enter the position at which the number has to be added: “);
scanf("%d", &pos);
for(i=n-1; i>=pos; i--) {
arr[i+1] = arr[i]; }
arr[pos] = num;
n++;
printf("\n The array after insertion of %d is: “, num);
for(i=0;i<n; i++)
{
printf("\t Xd", arr[i));
}
return 0;
}
• Output
Enter the number of elements in the array: 5 Enter the values:
12345
Enter the number to be inserted: 7
Enter the position at which the number has to be added: 3
The array after insertion of 7 is: 1 2 3 7 4 5
Deleting an Element from an Array
• Deleting an element from an array means
removing a data element from an already
existing array.
• If the element has to be deleted from the end
of the existing array, then the task of deletion
is quite simple. We just have to subtract 1
from the upper_bound.
• Step 1: SET upper_bound =upper_bound -1
Step 2: EXIT
Algorithm to Delete an Element From the Middle of an
Array
• The algorithm DELETE will be declared as DELETE(A, N, Pos).
The arguments are as follows:
• (a) A, the array from which the clement has to be deleted
• (b) N, the number of elements in the array
• (c) POS, the position from which the element has to be
deleted
Step 1: [INITIALIZATION] SET I = POS
Step 2: Repeat Steps 3 and 4 while I<=N-1
Step 3: SET A [I] =A [I + 1]
Step 4: SET I =I+1
[END OF LOOP]
Step 5: SET N=N-1
Step 6: EXIT
Write a program to delete a number from a given location in an array
#include <stdio.h>
int main()
{
int i, n, pos, arr[10];
printf("\n Enter the size of the array:");
scanf(“%d", &n);
printf("\n Enter the elements of the array : “);
for(i=; i<n;i++)
scanf(“%d", &arr[i]);
printf("\n Enter the position from which the number has to be deleted: ");
scanf("%d", &pos);
for(i= pos; i<n-1;i++)
arr[i] = arr [i+1];
n--;
printf("\n The array after deletion is:”
for(i=0;i<n;i ++)
printf("\n arr[%d] = %d", i, arr[i]);
return 0;
}
Output
Enter the size of the array: 5
Enter the elements of the array: 1 2 3 4 5
Enter the position from which the number has to be
deleted: 3
The array after deletion is:
arr[0] =1
arr[1] = 2
arr[2] =3
arr[3] = 5
Merging Two Arrays
• Merging two arrays in a third array means first
copying the contents of the first array into the
third array and then copying the contents of
the second array into the third array.
• Hence, the merged array contains contents of
the first array followed by the contents of the
second array.
• If the arrays are unsorted then merging the
arrays is very simple as one just needs to copy
the contents of One array into another.
Write a program to merge two unsorted arrays
#include<stdio.h>
int main() {
int arr1[10], arr2[10], arr3[20];
int i, nl, n2, m, index=0;
printf("\n Enter the number of elements in array 1; “);
scanf("%d", &n1);
printf("\n Enter the elements of the first array");
for(i=0;i<n1;i++)
scanf("Xd", &arri[i));
printf("\n Enter the number of elements in array 2: ");
scanf("%d", &n2);
printf("\n Enter the elements of the second array");
for(i=O; i<n2; i++)
scanf("%d", &arr2[i]);
m = n1+n2;
for(i=0; i<n1; i++)
{
arr3[index] = arr1[i];
index++;
}
for(i=0; i<n2; i++)
{
arr3[index] = arr2[i];
index++;
}
printf("\n\n The merged array is”);
for(i=0; i<m; i++)
printf("\t Arr[%d] = %d", i, arr3[i]);
return 0;
}
Output
• Enter the number of elements in array 1: 3
Enter the elements of the first array 10 20 30
Enter the number of elements in array 2: 3
Enter the elements of the second array 15 25
35
• The merged array is
• Arr[0] = 10 Arr[1] = 20 Arr[2] = 30
• Arr[3] = 15 Arr[4] = 25 Arr[5] = 35
Assignment 2.0
• Write a program to merge two sorted arrays.
Searching for a Value in an Array
• Searching means to find whether a particular
value is present in the array or not.
• If the value is present in the array then search
is said to be successful and the search process
gives the location of that value in the array,
• Otherwise, if the value is not present in the
array, the search process displays the
appropriate message and in this case search is
said to be unsuccessful
Linear Search
• Linear search, also called sequential search, is a very simple
method used for searching an array for a particular value.
• It works by comparing every element of the array one by one
in 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 the search is successful and it returns the position
of occurrence of VAL, Here, POS = 3 (index starting from 0).
Algorithm for linear search
• 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
Write a program to implement linear search.
#include<stdio.h>
int main()
{
int arr[10], num, i, n, found = 0, pos = -1;
print#("\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, 4);
break;
}
}
if (found == 0)
printf("\n %d does not exist in the array", num);
return 0;
}
Binary Search
• We have seen that the linear search algorithm is very slow If we have
an array with 1 million entries then to search a value from that array,
we would need to make 1 million comparisons in the worst case.
• if the array is sorted, we have a better and efficient alternative known
as binary search.
• Binary search is a searching algorithm that works efficiently with a
sorted list.
• The algorithm finds the position of a particular element in the array.
• The mechanism of binary search can be better understood by using the
analogy of a telephone directory.
• When we are searching for a particular name in the directory, we will
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 second part of
the directory.
• Again we will open some page in the middle and the whole process will
be repeated until we finally find the name.
Algorithm for binary search
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, then
POS = MID
PRINT POS Go to Step 6
ELSE IF A[MID] > VAL, then
SET END = MID – 1
ELSE
SET BEG = MID +1
[END OF IF]
[END OF LOOP]
Step 5: IF POS = -1, then
PRINT “VAL IS NOT PRESENT IN THE ARRAY”
[END OF IF]
Step 6: EXIT
• int A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
• and the value to be searched is VAL = 9.
• 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 will now search for the value in
the latter 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
• Now, VAL = 9 and A[MID] = A[8] = 8
• A[8) is less than VAL, therefore, we will now search for the value in
the latter half of the array.
• 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.
Write a program to implement binary search.
#include <stdio.h>
int main() {
int arr[10], num, i, n, pos = -1, beg, end, mid, found =0;
print#("\n Enter the number of elements in the array: “);
scanf("%d", &n);
printf("\n Enter the elements: “);
for(i=0;i<nj 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)
{
print#("\n %d is present in the array at position = %d", num, mid);
founde1;
break;
}
else if (arr[mid])>num)
end = mid-1;
else
beg = mid+1;
}
if ( beg > end && found == 0)
printf("\n %d does not exist in the array", num);
return 0;
}
Output
Enter the number of elements in the array:
Enter the elements: 12345
Enter the number that has to be searched: 7
7 does not exist in the array
PASSING ARRAYS TO FUNCTIONS
• Like variables of other data types, we can also pass an
array to a function, While in some situations, you may
want to pass individual elements of the array, and in
other situations you may want to pass the entire array.
• Passing Individual Elements The individual elements of
an array can be passed to a function by passing either
their data values or their addresses.
• Passing Data Values The individual elements can be
passed in the same manner as we pass variables of any
other data type.
• The condition is just that the data type of the array
clement must match with the type of the function
parameter.
Passing Addresses
Passing the Entire Array
Write a program to read and print an array of n numbers.
#include <stdio.h>
void read_array( int arr[], int);
void display array( int arr{], int);
int main()
{
int num[10], n;
printf("\n Enter the size of the array:");
scanf("%d", &n);
read_array(num, n);
display_array(num,n );
return 0;
}
void read_array(int arr[10], int n)
{
int i;
printf("\n Enter the elements of the array:");
for(i=0; i<n; i++)
scanf(“%d", &arr[i]);
}
void display array(int arr[10], int n)
{
int I;
printf("\n The elements of the array are :");
for( i=0;i<n;i++)
printf("\t %d", arr(i]);
}
Output
Enter the size of the array: 5
Enter the elements of the array: 1234 5
The elements of the array are: 12345
Assignment 2.0
• Write a program to merge two integer arrays.
Also display the merged array in reverse order.
• Write a program to interchange the largest
and the smallest number in an array
