Prof. N.

Guruprasad UNIT 1 - ARRAYS 1

 UNIT 1
ARRAYS

Prof. N. Guruprasad UNIT 1 - ARRAYS 2

 Those in this world who have courage & try to
solve in their own lives new problems of life R the
ones who raise the society to greatness.

Those who merely live according to rules do not

advance the society, they can only carry it along.

Prof. N. Guruprasad UNIT 1 - ARRAYS 3

 Definition : It is an ordered collection of elements that share the
same name.

Two types : single dimensional & multi dimensional

Each of these array type can be of either static array or dynamic

array.

Static arrays have their sizes declared from the start and the size
cannot be changed after declaration.

Dynamic arrays that allow you to dynamically change their size at

runtime, but they require more advanced techniques such as
pointers and memory allocation.

Prof. N. Guruprasad UNIT 1 - ARRAYS 4

 Syntax:
data-type array_name[<dim>];

Ex: int marks[5];

int  type of variable. / marks  name of an array. / 5  dimension of an array.

You can also use Macro substitution:

Ex: #define SUM 5;
int marks[SUM];

Memory Map of an array

The first element in an array is numbered 0 (zero) so last element is 1 less than
size of an array

Prof. N. Guruprasad UNIT 1 - ARRAYS 5

 /* code to find average marks of 5 students in a class */

/* body of main is omitted */

for(i=0;i<5;i++){
printf(“\n Enter marks”);
scanf(“%d”,&marks[i]);
}

for(i=0;i<5;i++)
sum+=marks[i];
avg=sum/5;
printf(“\n %f”,avg);

Prof. N. Guruprasad UNIT 1 - ARRAYS 6

 Initializing an array : Can be
initialized when they are declared.

Ex : int marks[5]={1,2,3,4,5};

ARRAYS Not necessary to specify dimension

of an array if it is being initialized.
C does it automatically for you.

Ex : int marks[]={1,2,3,4,5};

Prof. N. Guruprasad UNIT 1 - ARRAYS 7

 BOUNDS CHECKING :
In C there is no check to see if
subscript used for an array exceeds
the size of an array.

ARRAYS Ex : main(){
int num[40],i;
for(i=0;i<100;i++)
num[i]=i;
}

Data will be placed outside the

array probably on top of other
data.

Prof. N. Guruprasad UNIT 1 - ARRAYS 8

 Find the validity of the following code:

int main() {
int arr[2] = {1, 2, 3, 4, 5};
printf("%d", arr[3]);
}

Sol : Garbage Value

Here the size of an array is 2, but the value inside array is exceed 2.
Thus it prints garbage value for index more than 1

Prof. N. Guruprasad UNIT 1 - ARRAYS 9

 Find the validity of the following code:

int main() {
int a, b, c;
int arr[5] = {1, 2, 3, 25, 7};
a = ++arr[1];
b = arr[1]++;
c = arr[a++];
printf(“\n %d %d %d", a, b, c);
}

Sol : 4 3 25

Prof. N. Guruprasad UNIT 1 - ARRAYS 10

 Applications :
Sorting : 1) Bubble sort
2) Selection sort

Searching :
1) Linear search
2) Binary search

Prof. N. Guruprasad UNIT 1 - ARRAYS 11

 Bubble sort :
The most widely known
among beginning students
of programming – BUBBLE
SORT.
Bubble sort
One of the main
characteristic of this sort is
that it is easy to understand
and code.

Prof. N. Guruprasad UNIT 1 - ARRAYS 12

 BUBBLE SORT - Procedure:
Suppose list of numbers A[1], A[2] . . . A[N] is in memory.
Step 1) Compare A[1] with A[2] and arrange them in desired order such that
A[1] < A[2].
Then compare A[2] with A[3] and arrange such that A[2] < A[3].
Finally we arrange A[N-1] with A[N]

Step 2) Repeat Step 1 with one less comparison. During which the second
largest element will occupy its proper position. i.e we stop after we
compare and finally rearrange A[N-2] with A[N-1]

Step N-1) Finally we compare A[1] with A[2] and arrange them in such a
way that A[1] < A[2].

Prof. N. Guruprasad UNIT 1 - ARRAYS 13

 BUBBLE SORT - Example
We have following N numbers :
25 57 48 37 12 92 86 33

During the first pass the following comparisons are made.

A[0] with A[1] i.e 25 with 57. 25 < 57 hence no interchange.

A[1] with A[2] i.e 57 with 48. 57 > 48 hence interchange.

25 48 57 37 12 92 86 33

A[2] with A[3] i.e 57 with 37. 57 > 37 hence interchange.

Prof. N. Guruprasad UNIT 1 - ARRAYS 14

 25 48 37 57 12 92 86 33

A[3] with A[4] i.e 57 with 12. 57 > 12 hence interchange.

25 48 37 12 57 92 86 33

A[4] with A[5] i.e 57 with 92. 57 < 92 hence no interchange.

25 48 37 12 57 92 86 33

A[5] with A[6] i.e 92 with 86. 92 > 86 hence interchange

25 48 37 12 57 86 92 33

Prof. N. Guruprasad UNIT 1 - ARRAYS 15

 A[5] with A[6] i.e 92 with 86. 92 > 86 hence interchange

25 48 37 12 57 86 92 33

A[6] with A[7] i.e 92 with 33. 92 > 33 hence interchange.

25 48 37 12 57 86 33 92

Thus at the end of first pass array will look like :

25 48 37 12 57 86 33 92

Prof. N. Guruprasad UNIT 1 - ARRAYS 16

 Complete set of iterations

Iteration Array Elements

#
1 25 48 37 12 57 86 33 92
2 25 37 12 48 57 33 86 92
3 25 12 37 48 33 57 86 92
4 12 25 37 33 48 57 86 92
5 12 25 33 37 48 57 86 92
6 12 25 33 37 48 57 86 92
7 12 25 33 37 48 57 86 92

Prof. N. Guruprasad UNIT 1 - ARRAYS 17

 BUBBLE SORT – Formal Algorithm:
Here DATA is an array with N elements.
1. Repeat steps 2 & 3 for K = 1 to N-1
2. Set PTR:=1 [ Initializes pass pointer PTR]
3. Repeat while PTR <= N-K [ Execute pass ]
a. If DATA[PTR] > DATA[PTR+1] then
interchange DATA[PTR] and DATA[PTR+1]
[ end of if structure ]
b. Set PTR := PTR+1
[ end of inner loop ]
[ end of step 1 loop ]
4. Exit

Prof. N. Guruprasad UNIT 1 - ARRAYS 18

 Advantages:

Simple to understand
Easy to implement.

Disadvantages :

Most inefficient sorting technique

Slowest sorting technique

Prof. N. Guruprasad UNIT 1 - ARRAYS 19

 Selection sort :
Selection sort is a simple sorting
algorithm.

This sorting algorithm is an in-

Selection sort place comparison-based
algorithm in which the list is
divided into two parts, the sorted
part at the left end and the
unsorted part at the right end.

Initially, the sorted part is empty

and the unsorted part is the
entire list.

Prof. N. Guruprasad UNIT 1 - ARRAYS 20

 SELECTION SORT - Example
We have following N numbers :
20 12 10 15 2

During the first pass the following comparisons are made.

A[0] with A[1] i.e 20 with 12. 20 > 12 hence interchange.

We get:
12 20 10 15 2

Now A[0] with A[2] i.e 12 with 10. 12 > 10 hence interchange.
We get:
10 20 12 15 2

Prof. N. Guruprasad UNIT 1 - ARRAYS 21

 Now A[0] with A[3] i.e 10 with 15. 10 < 15 - hence no interchange.
We have:
10 20 12 15 2

Now A[0] with A[4] i.e 10 with 2. 10 > 2 - hence interchange.

We have:
2 20 12 15 10

This is the end of first pass. The lowest element is in first position.

Prof. N. Guruprasad UNIT 1 - ARRAYS 22

 Second Pass:
We have:
2 20 12 15 10

Now A[1] with A[2] i.e 20 with 12. 20 > 12 - hence interchange.
We get:
2 12 20 15 10

Now A[1] with A[3] i.e 12 with 15. 12 < 15 - hence no interchange.
We have:
2 12 20 15 10

Now A[1] with A[4] i.e 12 with 10. 12 > 10 - hence interchange.
We get :
2 10 20 15 12

Prof. N. Guruprasad UNIT 1 - ARRAYS 23

 Complete set of iterations

Iteration Array Elements

#
1 2 20 12 15 10
2 2 10 20 15 12
3 2 10 12 20 15
4 2 10 12 15 20

Prof. N. Guruprasad UNIT 1 - ARRAYS 24

 BINARY SEARCH:

Suppose DATA is an array which is sorted in increasing numerical order

or equivalently or alphabetically.

Then there is an extremely efficient searching algorithm called binary

search which can be used to find the location LOC of given ITEM of
information of DATA.

Prof. N. Guruprasad UNIT 1 - ARRAYS 25

 BINARY SEARCH - Algorithm:

Abbreviations used :

DATA  sorted array

LB  lower bound
UB  upper bound
ITEM  given item of information
BEG  beginning of the segment
END  end of the segment
MID  middle location of segment

Prof. N. Guruprasad UNIT 1 - ARRAYS 26

 BINARY SEARCH – Algorithm (cont):
1) Initialize segment variable :
Set BEG:=LB
END:=UB
MID:=INT((BEG+END)/2)

2) Repeat steps 3 & 4 while

BEG <= END and DATA[MID] != ITEM

3) If ITEM < DATA[MID] then

Set END:=MID-1
else
Set BEG:=MID+1
[ end of if structure ]
Prof. N. Guruprasad UNIT 1 - ARRAYS 27
 4) Set MID:=INT((BEG+END)/2)

5) If DATA[MID] = ITEM then

Set LOC:=MID
else
Set LOC:=NULL
[ end of if structure ]

6) Exit

Whenever ITEM does not appear in DATA, the algorithm

eventually arrives at the stage BEG=END=MID

Prof. N. Guruprasad UNIT 1 - ARRAYS 28

 BINARY SEARCH – Example:
Let DATA be the following sorted 13 element array.

11 22 30 33 40 44 55 60 66 77 80 88 99

We apply binary search to search for an element 40.

1) Initially BEG=1 and END=13

therefore MID:=INT(1+13)/2 = 7
hence DATA[MID]=DATA[7]=55.

2) Since 40 < 55 ( ITEM<DATA[MID]) END has its value changed by :

END=MID-1=7-1=6
therefore MID=INT(1+6)/2=3
hence DATA[MID]=DATA[3]=30

Prof. N. Guruprasad UNIT 1 - ARRAYS 29

 3) Since 40 > 30 ( ITEM>DATA[MID]) BEG has its value changed to :
BEG=MID+1=3+1=4
therefore MID=INT(4+6)/2=5
hence DATA[MID]=DATA[5]=40

Now since DATA[MID]=ITEM V draw conclusion that ITEM is

found and search is successful. V have found the ITEM in
location LOC=MID=5.

Prof. N. Guruprasad UNIT 1 - ARRAYS 30

 LINEAR SEARCH:

Linear search is a very simple search algorithm. In this type of

search, a sequential search is made over all items one by one.
Every item is checked and if a match is found then that particular
item is returned, otherwise the search continues till the end of the
data collection.

Also called as SEQUENTIAL SEARCH

Prof. N. Guruprasad UNIT 1 - ARRAYS 31

 ALGORITHM:

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

Prof. N. Guruprasad UNIT 1 - ARRAYS 32

 Difference:

LINEAR SEARCH BINARY SEARCH

1 Sorted list is not required. Sorted list is required.

2 It can be used in linked list It cannot be used in liked list
Implementation. Implementation.
3 It is suitable for a list changing It is only suitable for static lists,
very frequently. because any change requires resorting
of the list.
4 The average number of The average number of comparison is
comparison is very high. relatively slow.

Prof. N. Guruprasad UNIT 1 - ARRAYS 33

 Program:

Develop a program to sort the given set of N

elements using BUBBLE SORT.

Prof. N. Guruprasad UNIT 1 - ARRAYS 34

 #include<stdio.h>
void main() {
int n,i,j,temp,a[20];
printf(“\n Enter the number of elements :”);
scanf(“%d”,&n);
printf(“\n Enter the elements to sort :);
for (i = 0; i < n; i++)
scanf(“%d”,&a[i]);

Prof. N. Guruprasad UNIT 1 - ARRAYS 35

 for(j=1;j<n;j++) { // sorting
for(i=0;i<n-j;i++) {
if(a[i]>a[i+1]) {
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
printf(“\n Sorted array is : “);
for (i = 0; i < n; i++)
printf(“%d”,a[i]);
}
Prof. N. Guruprasad UNIT 1 - ARRAYS 36
 Multi dimensional array:
Initializing a 2-D array:
static int marks[5][2]={
{11,12},
{13,14},
{15,16},
{17,18},
{19,20}
};
Can also be written as :

static int marks[5][2]={11,12,13,14,15,16,17,18,19,20};

Of course with corresponding loss in readability.

Prof. N. Guruprasad UNIT 1 - ARRAYS 37

 NOTE : necessary to mention second column whereas first
row is optional.

Ex : static int marks[5][2]={11,12,13,…};

and
static int marks[][2]={11,12,13,…}; are perfectly
acceptable.

Whereas
static int marks[5][]={11,12,13,…};
and
static int marks[][]={11,12,13,…}; would never work.

Prof. N. Guruprasad UNIT 1 - ARRAYS 38

 MATRIX MULTIPLICATION:

To multiply two matrices, the number of columns of the

first matrix should be equal to the number of rows of the
second matrix.
1 2 5 6 1*5+2*0 1*6+2*7
* =
3 4 0 7 3*5+4*0 3*6+4*7

5 20
=
15 46

Prof. N. Guruprasad UNIT 1 - ARRAYS 39

 Program:
#include <stdio.h>
int main() {
int i,j,k,m,n,p,q;
int a[10][10], b[10][10], c[10][10]
printf(“\n Enter the size of matrix A : ");
scanf("%d %d", &m, &n);
printf(“\n Enter the size of matrix B : ");
scanf("%d%d", &p, &q);
if (n != p) {
printf(“\n Matrix multiplication not possible.\n");
exit(0);
}

Prof. N. Guruprasad UNIT 1 - ARRAYS 40

 printf(“\n Enter elements of matrix A : \n”);
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++)
scanf(“%d”, &a[i][j]);
}
printf(“\n Enter elements of matrix B : \n”);
for (i = 0; i < p; i++) {
for (j = 0; j < q; j++)
scanf(“%d”, &b[i][j]);
}

Prof. N. Guruprasad UNIT 1 - ARRAYS 41

 /* Matrix multiplication */
for (i = 0; i < m; i++) {
for (j = 0; j < q; j++) {
c[i][j]=0;
for (k = 0; k < p; k++) {
c[i][j] += a[i][k] * b[k][j];
}
}

Prof. N. Guruprasad UNIT 1 - ARRAYS 42

 /* printing the Matrix */
printf(“\n Product of matrix A and B is : \n “);
for (i = 0; i < m; i++) {
for (j = 0; j < q; j++) {
printf(“%3d”,c[i][j]);
}
printf(“\n”);
}
}

Prof. N. Guruprasad UNIT 1 - ARRAYS 43

 Matrix Transpose:

The transpose of a matrix is a new matrix that is obtained

by exchanging the rows and columns.

1 4 0 1 -5
= 4 2
-5 2 7 0 7

Prof. N. Guruprasad UNIT 1 - ARRAYS 44

 Program:
#include <stdio.h>
int main() {
int a[10][10], transpose[10][10], r, c, i, j;
printf("Enter rows and columns: ");
scanf("%d %d", &r, &c);
/* Assigning elements to the matrix */
printf("\nEnter matrix elements:\n");
for (i = 0; i < r; ++i)
for (j = 0; j < c; ++j) {
printf("Enter element a[%d][%d]: ", i + 1, j + 1);
scanf("%d", &a[i][j]);
}

Prof. N. Guruprasad UNIT 1 - ARRAYS 45

 // Finding the transpose of matrix a
for (i = 0; i < r; ++i)
for (j = 0; j < c; ++j) {
transpose[j][i] = a[i][j];
}

// Displaying the transpose of matrix a

printf("\nTranspose of the matrix:\n");
for (i = 0; i < c; ++i)
for (j = 0; j < r; ++j) {
printf("%d ", transpose[i][j]);
if (j == r - 1) printf("\n");
}
}
Prof. N. Guruprasad UNIT 1 - ARRAYS 46
 Find validity of following code :

Assume array starts at 101 and int occupies 2 bytes

main() {
int n[3][3]={1,2,3,4,5,6,7,8,9};
printf(“\n %d”,n);
printf(“\n %d”,n[2]);
printf(“\n %d ”,n[2][2]);
}

Sol : 101 113 9

Prof. N. Guruprasad UNIT 1 - ARRAYS 47

 Programs
1) Bubble sort.
2) Selection sort
3) Binary search
4) Linear search
5) Matrix programs :
1) addition of matrix / multiplication of matrix
2) transpose of matrix / trace of matrix
3) norm of matrix
4) sum of diagonal elements
5) sparse matrix
6) row sum & column sum of matrix
7) insert & delete an element

Prof. N. Guruprasad UNIT 1 - ARRAYS 48

 Programs ( cont )

6) The first sequence D1 of a sequence A of N elements is obtained

by subtracting each element except the last, from the next
element in the array.
The second difference D2 is obtained as the first difference of D1
and so on
Ex : A : 1 4 8 7 11 14 21
Then
D1 : 3 4 -1 4 3 7
D2 : 1 -5 5 -1 4
D3 : -6 10 -6 5
D4 : -16 -16 11
D5 : 0 27
D6 : 27

Prof. N. Guruprasad UNIT 1 - ARRAYS 49

 7) Program that fills right to left diagonal of a square
matrix with zeros, the lower triangle with -1s and upper
left triangle with +1s.

Ex : 6*6 matrix

1 1 1 1 1 0
1 1 1 1 0 -1
1 1 1 0 -1 -1
1 1 0 -1 -1 -1
1 0 -1 -1 -1 -1
0 -1 -1 -1 -1 -1

Prof. N. Guruprasad UNIT 1 - ARRAYS 50

 Programs ( challenging ones )

8) Write a C code to develop magic square for odd

dimension of matrix.
9) To multiply two numbers using : LATTICE METHOD

NGP invented
10) Input : 5 digit
Output : 5 digit . . .

Prof. N. Guruprasad UNIT 1 - ARRAYS 51

 CONCLUSION:
Arrays in C act to store related data under a single variable name
with an index, also known as a subscript. It is easiest to think of an
array as simply a list or ordered grouping for variables of the same
type.

As such, arrays often help a programmer organize collections of data

efficiently and intuitively.

Even though arrays are supported in most of the programming

languages, in C it is little bit more special.

Apart from being more convenient and more educative, it is also

impressive in style and presentation.

Prof. N. Guruprasad UNIT 1 - ARRAYS 52

 We have seen different types of arrays and their examples.

And we also laid ourselves in the danger of exceeding array limits.

The computer won’t give you an error. It won’t stop you from
crossing borders.

So you better know what you’re getting into because here you’re
on your own.

Prof. N. Guruprasad UNIT 1 - ARRAYS 53