.

CHAPTER - 3
ARRAYS
Data structures are classified into two categories- linear and non-linear. A data structure is said to
be linear if its elements form a sequence, or a linear list. Elements in a non-linear data structure
do not form a sequence. There are two ways of representing linear structures in memory. One
way is to have the linear relationship between the elements by means of sequential memory
locations. Such linear structures are called Arrays.

Arrays are useful when the number of elements to be stored is fixed. They are easy to traverse,
search and sort.

An Array is a finite collection of homogeneous values stored in adjacent memory locations. Here
‘finite’ mean that there are specific number of elements in an array and by ‘similar’ mean that
the all the elements in an array are of the same type. The data type could be of type char, in
which case we have a string. The data type could just as easily be of type int, float or even
another array.

The operations that can performed on any linear structure, whether it may be an array or linked
list, include the following:

OPERATIONS ON ARRAYS

Traversal: Processing each element in the array.

Search: Finding the location of an element with a given value.

Insertion: Adding a new element to an array.

Deletion: Removing an element from an array.

Sorting: Organizing the elements in some order.

Merging: Combining two arrays into a single array.

Reversing: Reversing the elements of an array.

An array containing n number of elements is referenced using an index that varies from 0 to n-1.
For example, the elements of an array a[n] containing n elements are denoted by a[0],a[1],a[2]…
a[n-1], where 0 is the lower bound and n-1 is the upper bound of the array.

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 1

The lowest index of an array is the lower bound and the highest index is the upper bound. The
number of elements in the array is called the range. The elements of an array are stored in
contiguous memory locations.

An array is a set of pairs of an index and a value. For each index there is a value associated with
it. For each index, there is a value associated with it. For example,

Figure: Elements in an array with indices

The number of elements is called the length or size of the array. In the above situation n is the
length of the array.

TRAVERSAL
Let ‘a’ be a collection of data elements stored in the memory of the computer. In order to print
the contents of each element of ‘a’ or suppose to count the number of elements of a with a given
property. This is accomplished by traversing ‘a’, i.e., by accessing and processing each element
of ‘a’ exactly once.

Algorithm TRAVERSE (LA, N, K, LB, UB)

1) Start

2) // Initialize counter

Set k: =LB.

2) Repeat steps 3 and 4 while k <=UB.

{
3) // APPLY PROCESS TO LA[K]. PROCESS is scaling the array elements by 2.

LA[K] = LA[K] * 2;

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 2

 4) // Increase Counter

Set k: =k + 1.

[End of step 2 loop]

5) Stop

Analysis of the Algorithm

Time Complexity: O(n)
Space Complexity: O(n)
SEARCHING
Searching refers to the operation of finding the location of an element in an array or printing
message that element does not appear there. The search is said to be successful if the element is
found and unsuccessful otherwise. Below is the algorithm to find an element with a value of ITEM
using Sequential search/Linear search.
Algorithm LINEAR SEARCH (LA, N, K, ITEM)
1) Start
2) Set K=0
3) Repeat steps 4 and 5 while K < N
4) IF LA [K] = ITEM then go to step 6
5) Set K=K+1
6) Print K, ITEM
7) Stop
Analysis of the Algorithm
Time Complexity: O(n)
Space Complexity: O(n)
INSERTION
Let a be a collection of data elements in the memory of the computer. ‘Inserting’ refers to the
operation of adding another element to the collection a. Inserting an element at the end of the array
can be easily done provided the memory space allocated for the array is large enough to
accommodate the additional element.

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 3

To insert an element in the middle of the array, on the average, half of the elements must be moved
downward to new locations to accommodate the new element and keep the order of the other
elements.
Figure: Inserting an element

Algorithm
INSERT (LA, N, K, ITEM)

// Here LA is a linear array with N elements and k is a positive integer such that K <= N. This

// algorithm inserts an element ITEM into the Kth position in LA.

1) // Initialize counter

Set J := N.

2) Repeat Steps 3 and 4 while J >= K.

3) // Move Jth element downward

Set LA[J + 1] := LA[J]

4) // Decrease counter

Set J : = J – 1

[ END OF STEP2 loop]

5) // Insert element

Set LA[K] := ITEM.

6) // Reset N

Set N:=N+1.

7) Exit.

Analysis of the Algorithm

Time Complexity: O(n)

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 4

Space Complexity: O(n)

DELETION
Deleting an element at the end of an array presents no difficulties. But deleting an element from
the middle of the array would require that each subsequent element be moved one location
upward in order to fill up the array.

Figure: Deleting an element

Algorithm
DELETE (LA, N, K, ITEM)
// Here LA is a linear array with N elements and k is a positive integer such that K <= N. This

// algorithm deletes the Kth element from LA.

1) Set ITEM := LA[K]

2) Repeat for J = K to N – 1:

3) // Move J + 1st element upward

Set LA[J] := LA[J+1]

[End of loop]

4) // Reset the number N of elements in LA

Set N := N – 1.

4) Exit

Analysis of the Algorithm

Time Complexity: O(n)

Space Complexity: O(n)

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 5

SORTING
Sorting refers to the operation of organizing the elements in some order. The Bubble sort
algorithm will sort the elements of the array in either ascending/descending order.

Algorithm
BUBBLESORT( int A[ ], N)
// This algorithm sorts the elements in the array in ascending order
1) Start
2) Repeat steps 2 and 3 for K = 1 to N-1
{
PTR = 1;
3) Repeat steps while ptr <= N - K
{
4) IF A[PTR] > A[PTR + 1]
{
temp = A[PTR];
A[PTR] = A[PTR+1];
A[PTR+1] = temp;
}
5) Stop
Complexity
Time Complexity:
Worst case: O(n*n).
Average case: O(n*n).
Best Case: O(n).
Space Complexity: O(1)
MERGING
Merging of arrays involves two steps- sorting the arrays that are to be merged, and adding the
sorted elements of both the arrays to a new array in a sorted order.

Method
1) Declare two arrays and input the array elements in both the arrays

2) Traverse both the arrays

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 6

3) Find the minimum element among the current two elements of both the arrays and update the
output array with the least value and increment its index to next position.

Array A elements:1 2 3 4 5
Array B elements: 6 7 8 9 10
Output- The Merged Sorted Array C: 1 2 3 4 5 6 7 8 9 10
Algorithm MERGE (int A[ ], int B[ ], int c, int m, int n)

// This algorithm combines two sorted arrays into third array

int i,j,k;

1) Initialize i=0, j = 0, k = 0;
2) Repeat steps while(i<m && j<n)
{
3) if(A[i] <= B[j])
{
C[k] = A[i];
i++;
}
else
{
C[k] = B[j];
j++;
}
k++;
}
4) for(int p=i; p<m; p++)
{
C[k] = A[P];
k++;
}
5) for(int p=j; p<n; p++)
{

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 7

C[k] = B[P];
k++;
}
}
}
Complexity
Time Complexity: O(n*m)
Space Complexity: O(1)

REVERSING

Reverse the entire array by swapping the elements.

Figure: Reversing

Algorithm
REVERSE ARRAY (int arr[], int start, int end){

1) Initialize start and end indexes.

start = 0, end = n-1

2) In a loop, swap arr[start] with arr[end]

int temp;

while (start < end)

temp = arr[start];

arr[start] = arr[end];

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 8

 arr[end] = temp;

3) Change start and end as follows.

start = start +1

end = end – 1

} end of while loop

4) for (i=0; i < size; i++)

print(arr[i]); }}

MULTI DIMENSIONAL ARRAYS

Two-Dimensional Arrays

A 2-dimensional array is a collection of elements placed in m rows and n columns. The syntax
used to declare a 2-D array includes two subscripts, of which one specifies the number of rows
and the other specifies the number of columns of an array. These two subscripts are used to
reference an element in an array.

Example: a[4][3] is a 2-D array containing 4 rows and 3 columns and a[0][2] is an element
placed at 0th row and 2nd column in the array. The two-dimensional array is also called a matrix.
The pictorial representation of a matrix is shown in figure below:

Figure: Matrix

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 9

Matrix operations

The horizontal lines in a matrix are called rows and the vertical lines are called columns. A
matrix with m rows and n columns is called an m-by-n matrix (or m×n matrix) and m and n are
called its dimensions. Information that is stored in a rectangular array may not require every
position in the rectangle for its representation.

The entry of a matrix A that lies in the i -th row and the j-th column is called the i,j entry or (i,j)-
th entry of A. This is written as Ai,j or A[i,j].

We often write to define an m × n matrix A with each entry in the matrix

A[i,j] called aij for all 1 ≤ i ≤ m and 1 ≤ j ≤ n.

Example: The matrix

is a 4×3 matrix. The element A[2,3] or a2,3 is 7.

Common matrix operations are addition, subtraction, multiplication, transposition, evaluation of

determinant of a square matrix, etc.

Matrix addition is the sum or difference of the individual elements and this is the same as the
simple array arithmetic operations. If two matrices have the same dimensions, they may be added
together. The result is a new matrix with the same dimensions in which each element is the sum
of the corresponding elements of the previous matrices.

Matrix subtraction is like addition. Each element of one matrix is subtracted from the
corresponding element of the other. If a scalar is subtracted from a matrix, the former is
subtracted from every element of the latter.

A transpose of a matrix is obtained by interchanging the rows with corresponding columns of a

given matrix.

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 10

Representation of Two-Dimensional Array

Let A be a two-dimensional m x n array. Although A is pictured as a rectangular array of

elements with m rows and n columns, the array will be represented in memory by a block of m.n
sequential memory locations. Specifically, the programming language will store the array a
either (1) column by column, is what is called column-major order, or (2) row by row, in row-
major order. Figure shows these two ways when A is a two-dimensional 3 x 4 array. Here the
particular representation used depends upon the programming language, not the user.

For a linear array LA, the computer does not keep track of the address

LOC(a[n]) = Base(a) + w(n – 1)

To find the address of a[n] in time independent of n. (Here w is the number of words per memory
cell for the array LA, and 1 is the lower bound of the index set of a.)

A similar situation also holds for any two-dimensional m x n array a. That is, the computer keeps
track of Base(a) – the address of the first element a[1, 1] of a – and computes the address
LOC(a[j,k]) of a[j,k] using the formula

(Column-major order) LOC(a[j,k]) = Base (a) + w[M(n – 1) + (j – 1)]

(Row-major order) LOC(a[j,k] = Base(a) + w[N(j – 1) + (k – 1)].

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 11

Example:

int a[3][4] = {
{ 22, 10,-3,4 } ,
{ 15, 9, 81, 123 },
{ 7, 87, 59, 34 }
}
Shown below are the possible arrangements of 2-D array.

Since the array elements are stored in adjacent memory locations we can access any element of
the array once we know the base address (starting address) of the array and number of rows and
columns are present in the array.

Example, if the base address of the array shown in Figure is 502 and we wish to refer the element
123, then the calculation involved would be as follows.

Row Major arrangement:

Element 123 is present at a[1][3]. Hence location of 121 would be

= 300 + 1 * 4 + 3
= 300 + 7
= 314
In general for an array a[m][n] the address of element a[i][j] would be Base address + i* n + j .

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 12

Column Major arrangement:

Element 123 is present at a[1][3]. Hence location of 121 would be

= 300 + 3 * 3 +1
= 300 + 10
= 322
In general for an array a[m][n] the address of element a[i][j] would be Base address + j * n + i.
POINTERS AND ARRAYS
Pointers are variables that hold addresses of other variables. Not only can a pointer store the
address of a single variable, it can also store the address of cells of an array.

Example:

int *ptr;

int arr[5];

// store the address of the first

// element of arr in ptr

ptr = arr

Here, ptr is a pointer variable while arr is an int array. The code ptr = arr; stores the address of
the first element of the array in variable ptr.

Pointer to Every Array Elements

int *ptr;

int arr[5];

ptr = arr;

ptr + 1 is equivalent to &arr[1];

ptr + 2 is equivalent to &arr[2];

ptr + 3 is equivalent to &arr[3];

ptr + 4 is equivalent to &arr[4];

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 13

AN OVERVIEW OF POINTERS
Whenever a variable is declared in a program, system allocates a location i.e an address to that
variable in the memory, to hold the assigned value.

Let us assume that system has allocated memory location 80F for a variable a.

int a = 10;

We can access the value 10 either by using the variable name a or by using its address 80F.

The variables which are used to hold memory addresses are called Pointer variables.

A pointer variable is therefore nothing but a variable which holds an address of some other
variable. And the value of a pointer variable gets stored in another memory location.

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 14

Benefits of using pointers

 Pointers are more efficient in handling Arrays and Structures.

 Pointers allow references to function and thereby help in passing of function as

arguments to other functions.

 It reduces length of the program and its execution time as well.

 It allows C language to support Dynamic Memory management.

Prepared by Dr.B.GOPI, Asst.Professor, KIST, Kakutur, Nellore, A.P Page 15