Arrays

Introduction
A variable, be it of any fundamental data type, can hold only one value at a time. However,
sometimes handling of large data may be required. So, to process a large amount of data, we
need a data structure, known as array. An array is a sequenced collection of similar data
elements. These elements have to be of the same data type and they are stored in consecutive
memory locations. The elements can be accessed by an index, also called the subscript. Arrays
are of two types: one dimensional and multidimensional.

Declaration of One Dimensional Array

To declare a one dimensional array requires three things:
a) Data type: the kind of values, it can store. For e.g.: int, char, float, double.
b) Name: name of the array to identify it.
c) Size: the maximum number of elements the array can hold.
And the syntax to declare an array is as follows:
data_type array_name [size];
For e.g.: int marks [10];
This statement declares an array called ‘marks’ which can hold maximum 10 integer type
elements. This can be shown as follows:
0 1 2 3 4 5 6 7 8 9

Marks 10 20 30 40 50 60 70 80 90 100
1000 1004 1008 1012 1016 1020 1024 1028 1032 1036

Representation of One Dimensional Array in Memory

The array indexing should preferably start from 0. The first element will be stored in marks [0],
second element in marks [1], and so on. Therefore, the 10 th element will be stored in marks [9].
The numbers 0, 1, 2, etc written within the square brackets represent the index or subscript. All
the elements of the array will be stored in contiguous memory locations. Total memory that will
be allocated to an array will be size of the array × size of the data type. In the above case, the
total memory allocated will be 40 bytes.

The array name is a pointer that points to the base address of the array. Base address is the
starting address where the 1st element of an array is stored. The base address is 1000 in the above
example. With the array name and the index or subscript, the address of any element from the
array can be calculated as follows:

Address of any array element, a[i] = base address + index × size of the data type
E.g.: Address of element 40, i.e marks [3] = 1000 + 3 × 4
= 1012
And the formula to find the length of an array is as follows:
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
element of the array. The length of array ‘marks will be = 9 – 0 + 1 = 10.

Initialization of One Dimensional Array

Declaring an array simply allocates space for its elements. No values are stored in the array. An
array can be initialized either at the time of declaration (compile-time initialization) or values can
be entered by a user (run-time initialization). Some examples of compile-time initialization are as
follows:
1. int a[5] = {10, 20, 30, 40, 50};
- This statement will declare ‘a’ to be an array which can hold 5 integer type elements
and will simultaneously initialize all the 5 elements to the respective values.
2. int a[5] = {2};
- This statement will initialize all the 5 elements of the array to 2.
3. int a[10] = {1, 2, 3};
- This will initialize the 1st three elements of the array to the respective values and will
either set the remaining values to 0 or some junk values automatically.
If some processing is to be done on all the elements of an array, the concept of loops has to be
used. An example of run-time initialization of an array is as follows:
int a[5], i;
for (i = 0; i<5; i++)
scanf(“%d”, &a[i]);
In the code, we start the index, i, at 0 and input the value for the 1st element of the array. Since
the array has 5 elements, we must input values for elements whose index ranges from 0 to 9.

Two Dimensional Arrays

One-dimensional arrays are organized linearly in one direction. But at times, data need to be
stored in the form of tables. So, the concept of one-dimensional arrays is extended to incorporate
two-dimensional data structures. A two-dimensional array is specified using two subscripts
where the 1st subscript denotes the rot and the 2 nd denotes column. A two dimensional array is
declared as follows:
data_type array_name [row_size][column_size];
For e.g.: int a [2][5];
Here, a is a two-dimensional array or a matrix which has 2 rows and 5 columns, thereby holding
a total of 2×5=10 elements and each element in it is accessed using two subscripts. The first
element is denoted by a[0][0], the second element by a[0][1] and so on.

Representation of Two Dimensional Arrays in Memory

The elements of a two-dimensional array are stored sequentially in the memory. There are two
ways of storing a two-dimensional array in memory. First is the row major order and the second
is column major order. In row major order, the elements of the 1st row are stored before the
elements of the second and third row. That is, elements are stored row by row. This can be
shown as follows:

(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 0) (1, 1) (1, 2) (1, 3) (1, 4)
However, when elements are stores in a column major order, the elements of the 1 st column are
stored before the elements of second and third row. That is, elements are stored column by
column. This can be shown as follows:

(0, 0) (1, 0) (2, 0) (3, 0) (4, 0) (0, 1) (1, 1) (2, 1) (3, 1) (4, 1)
As, the name of any one-dimensional array points to the first address of it, same is the case with
two-dimensional arrays. Here also, the compiler keeps track of its base address and the address
of the other elements can be calculated as:
Address of a[i][j] =base address+(no of columns × i + j) × size of data type// row major order
OR
Address of a[i][j] =base address+(no of rows × j + i) × size of data type // column major order

Sparse Matrices
Sparse Matrix is a matrix that has large number of elements with a value 0. There are two types
of sparse matrix. In the first type, all elements above the main diagonal have a 0 value. This type
of matrix is also called a lower triangular matrix. In such a matrix, the first row has one non-zero
element, the second row has two non-zero elements, and so on. In an upper triangular matrix, all
the elements below the main diagonal have a 0 value. Here, the first row has no non-zero
element; the second row has one non-zero element, and so on. There is another variant of a
sparse matrix in which elements with a non-zero value can appear only on the diagonal or
immediately above or below the diagonal. Such a matrix is called tri-diagonal matrix.

Operations on Arrays
The list of operations that can be performed on an array includes traversing an array, inserting
an element in an array, deleting an element from an array, searching an element in an array and
sorting arrays in either ascending or descending order.
1. Traversing an Array: Traversing an array means accessing each and every element of
the array for a specific purpose. This operation can be done for printing every element,
counting the number of elements, or performing any process on all the elements of an
array. Since array is a linear data structure, so traversing is simple and straightforward.
The algorithm for array traversal is as follows:
Step 1: [INITIALIZATION] Set I = lower_bound //Initialization
Step 2: Repeat Steps 3 and 4 while I <= upper_bound // Condition
Step 3: Apply Process to A[i]
Step 4: Set I = I + 1 //Updation
[END OF LOOP]
Step 5: EXIT
 In Step 1, the index, I, is initialized to the lower bound of the array. In Step 2, a while
loop is executed. Step 3 processes the individual array element as specified by the array
name, A, and index value. Step 4 increments the index value so that the next array
element could be processed. The while loop in Step 2 is executed until all the elements in
the array are processed, i.e., until I is less than or equal to the upper bound of the array.
2. Inserting and Deleting an Element in an Array: Inserting refers to the operation of
adding another element to the collection of elements of an array. And deleting refers to
the operation removing any one element from the collection.
Inserting an element at the end of the array can be easily done provided the memory
space allocated to the array is large enough to hold the new element. On the other hand,
suppose, if insertion has to be done in the middle of an array, then, on the average, half of
the elements must be moved downwards to new locations to accommodate the new
element. The algorithm for inserting an element into an array will be declared as
INSERT(A,N,POS,VAL). The arguments include the name of the array in which element
is to be inserted, A, the size of the array before insertion, N, the position at which the
element has to be inserted, POS, and the value that will be inserted, VAL.
Step 1: [INITIALIZATIO] Set I = N-1
Step 2: Repeat Steps 3 and 4 while I >= POS
Step 3: Set A[I + 1] = A[I]
Step 4: Set I = I - 1
[END LOOP]
Step 5: [INSERT ELEMENT] Set A[POS] = VAL
Step 6: [RESET N] Set N = N + 1
Step 7: EXIT
Here, in Step 1, the index, I, is initialized to the total number of elements in the array. In
Step 2, a while loop is executed which will move all the elements having an index greater
than POS one position towards the right to create space for the new element. In Step 5,
the new value is inserted at the desired position and Step 6 the size of the new array is
reset.
Similarly, deleting an element at the end of an array presents no difficulties. But deleting
an element from some other position would require each subsequent element to be moved
one location upward in order to fill up the array. The algorithm for deleting an element
from an array will be declared as DELETE(A,N,POS). The arguments include the name of
the array from which element is to be deleted, A, the size of the array before deletion, N,
and the position from which the element has to be deleted, POS.
Step 1: [INITIALIZATIO] 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 LOOP]
Step 5: [RESET N] Set N = N - 1
Step 6: EXIT
Here, in Step 1, the index, I, is initialized to the position from which the element has to be
deleted. In Step 2, a while loop is executed which will move all the elements having an
 index greater than POS one position towards the left to occupy the space vacated by the
deleted element. When we delete an element from an array, we actually overwrite the
value with the value of its successive element. In Step 5, the size of the new array is reset.
3. Searching an Element in an Array: Searching means to find whether a particular value
is present in an array or not. If the value is present, the search is said to be successful and
the searching process gives the location of that value in the array. However, if value is
not present, the search is said to be unsuccessful. There are two types of searching: linear
and binary. For sorted arrays, binary search is to be employed and linear search is used
for unordered arrays.
a. Linear Search: This is a simple technique of searching 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. The algorithm for searching an
element linearly is as follows:
LINEAR_SEARCH (A, N, VAL)
Step 1: [INITIALIZE] Set I = 0
Step 2: Repeat Steps 3 while I < N
Step 3: If A[I] = VAL
PRINT “Element present at position I”
Go to Step 6
[END OF IF]
Set I = I + 1
[END OF LOOP]
Step 4: If I = N
PRINT “Value is Not Present in the Array”
[END OF IF]
Step 5: EXIT
In Step 1, we initialize the value of I. In Step 2, a while loop is executed that will
continue till I is less than N. In Step 3, a check is made to see if a match is found
between the current array element and VAL. If a match is found, then position of
the array element is printed, else, value of I is incremented to match the next
element with VAL. However, if no match is found, then VAL is not present in the
array.
Complexity of Linear Search Algorithm: Linear Search executes in O(n) time,
where n is the number of elements in the array. The best case is when VAL is
equal to the first element of the array. In this case, only one comparison will be
made. Likewise, the worst case will happen when either VAL is not present in the
array or it is equal to the last array element. In such a case, n comparisons will
have to be made.
b. Binary Search: It works efficiently with a sorted list. This is a divide and
conquer algorithm which halves the number of items to be checked, with each
iteration. The algorithm for binary search is as follows:
 BINARY_SEARCH (A, lower_bound, upper_bound, VAL)
Step 1: [INITIALIZE] Set Beg = lower_bound,
End = upper_bound
Step 2: Repeat Steps 3 and 4 while Beg < = End
Step 3: Set Mid = (Beg + End) / 2
Step 4: If A [Mid] = VAL
PRINT “Element present at position Mid”
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 Beg>End
PRINT “Value is not present in the array”
[END OF IF]
Step 6: EXIT
In Step 1, the value of Beg and End are initialized. In Step 2, a while loop is
executed until Beg is less than or equal to End. In Step 3, value of Mid is
calculated. Step 4 checks if the value at Mid is equal to VAL. If a match is found,
its position is printed and the algorithm exits. However, if a match is not found,
and if the value of A[Mid] is greater than VAL, then the value of End is updated
and process is repeated on the upper half array excluding the middle element.
Otherwise the value of Beg is updated and process is repeated on the lower half
array excluding the middle element. And if the value does not match with any of
the array element, i.e., Beg > End, then a suitable message is printed in Step 5.
Complexity of Binary Search Algorithm: The complexity in binary search is
calculated depending on the number of comparisons that are made. Here, it has
been observed that the size of the array segment where search has to be made gets
reduced to half. So the total number of comparisons that will be made is given as
O(log2 n).

4. Sorting Arrays: Sorting means arranging the elements of an array so that they are placed
in some relevant order which may be either ascending or descending. Some of the sorting
algorithms are discussed below:
a. Bubble Sort: It is a simple algorithm that sorts the array elements by repeatedly
moving the largest element to the highest index position of the array (for
ascending order). Here, consecutive adjacent pairs of elements 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. At the end of each pass, the largest element in the array will
be placed in its correct position. This process will continue till the list becomes
sorted. The algorithm for bubble sort is as follows:
 BUBBLE_SORT (A, N)
Step 1: [INITIALIZE] Set I=0
Step 2: Repeat Step 3 to 7 while I < N – 1
Step 3: Set J=0
Step 4: Repeat Step 5 and 6 while J < N – 1 – I
Step 5: If A[J] > A[J + 1]
SWAP A[J] and A[J + 1]
[END OF IF]
Step 6: J=J+1
[END OF INNER LOOP]
Step 7: I=I+1
[END OF OUTER LOOP]
Step 8: EXIT
In this algorithm, the outer loop is for the total number of passes which is N – 1.
For every pass, the inner loop will be executed. However, the number of
occurrence of 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 –1- I times, where N is the number of elements in the
array and I is the count of the pass
Complexity of Bubble Sort: In bubble sort, there are N – 1 passes in total. In the
first pass, N -1 comparisons are made to place the highest element in its correct
position. There are N – 2 comparisons in the second pass which places the 2 nd
largest element just one position before the largest element. Thus, complexity of
bubble sort will be given as:
f(n) = (n-1) + (n-2) + (n-3)+ … + 3 + 2 + 1
f(n) = n (n-1) / 2 = (n2 – n)/2 = O(n2)

b. Insertion Sort: The main idea behind insertion sort is that it inserts each item in
its proper place in the final list. It is a less efficient than other sorting algorithms.
The technique behind it is as follows: Keeping the first element intact, it picks the
second element and compares it with the 1 st. After putting them in order, the third
element is picked and compared with the 1 st two elements and the process
continues till the entire array becomes sorted.
Complexity of Insertion Sort: The best case occurs when the array is sorted. In
such a case, the complexity will be O(n). The worst case occurs when the array is
sorted in the reverse order and the complexity in this case will be O(n2).
c. Selection Sort: This sorting algorithm is known for its simplicity. It works as
follows: It first finds the smallest value in the array and interchanges it with the 1 st
element of the array, thereby keeping it in its correct position. Again the second
smallest element is found out and interchanged with the 2 nd element and the
process continues till the entire array becomes sorted.
Complexity of Selection Sort: Selection sort is independent of the original order
of elements in the array. In all cases, the complexity of selection sort will be
O(n2).
d. Merge Sort: It is a sorting algorithm that used the divide, conquer and combine
algorithmic paradigm. Divide means partitioning the n-element array into two
sub-arrays of n/2 elements. Conquer means sorting the two sub arrays recursively
using merge sort. Combine means merging the two sorted sub-arrays of size n/e to
produce the sorted array of n elements.
Complexity of Merge Sort: The running time of quick sort in the average and
worst case is O(n log n). In addition, this sorting algorithm needs an additional
space of O(n) for some temporary storage.
e. Quick Sort: It is a widely used algorithm. Basically, it has an efficient
implementation. It is also known as partition exchange sort. It also works by
using divide and conquer strategy to divide a single unsorted array into two
smaller sub-arrays. The technique behind it is as follows: A pivot element
selected from the array elements (generally the first element of the array). The
elements are arranged in such a way that all the elements that are less than the
pivot appear before the pivot and all the elements that are greater than the pivot
element come after it. After such a partitioning, the pivot is placed in its final
position. Then, the two sub-arrays obtained thus are recursively sorted.
Complexity of Quick Sort: The complexity of quick sort in all cases will be O(n
log n). However, its efficiency will greatly depend on the selection of pivot
element. The worst case will occur if the array is already sorted and leftmost
element is chosen as pivot.
f. Radix Sort: It is a linear sorting algorithm. Here sorting is done on each of the
digits in the number. The sorting procedure proceeds by sorting the least
significant to the most significant digit. The number of passes will depend on the
length of the number having maximum number of digits.
Complexity of Radix Sort: Radix sort takes O(n) time to complete its execution.