ARRAYS

• DEFINITION

– It is a finite and ordered collection of homogeneous

data elements
– Finite: has limited no. of elements
– Ordered: elements are stored one by one in
contiguous memory locations
– Homogeneous: all elements are of the same data type

Example:
An array of integers to store age of students
An array of strings to store student names
 TERMINOLOGY
• SIZE – no. of elements in an array
• TYPE – data type of elements
• BASE – address of memory location
where first element is stored
..

456

455

454

453 Base address

 TERMINOLOGY….
• INDEX – all elements in an array are
referenced by a subscript
eg: a[i], where i=index

Index is always an integer value

• RANGE OF INDEX – indices vary from lower

bound (L) to upper bound (U) called boundary
of the array

eg: int A[100]

range : 0 - 99
 TERMINOLOGY….
• Index of ith element is A[i] = L + i – 1
• To get index of 3rd element:
• 0+3–1=2

• Size of array : U – L + 1
• To get the size of array A[5]
• 4–0+1=5

• WORD – size of an element

Word size varies from machine to machine
 ONE-DIMENSIONAL ARRAY
• If only one subscript or index is required to reference all the elements in
an array, then the array is termed one-dimensional array
• Memory representation of Array
• In an array, all the elements or their references are stored in contiguous
memory locations. This allows for efficient access and manipulation of
elements.
 MEMORY ALLOCATION
Memory address of element = Base address + (Index × Size of each element)

1000
A[0]
1004
A[1]
1008
Address ( A[i] ) = M + ( i – L ) * w .
where M = base address
.
i = index j
L = lower bound .
w = word length
.
Address of A[1]=
=1000 + (1 – 0 ) * 4 100
=1004

A[100]
 MEMORY ALLOCATION ….
Address mapping between logical and physical views of an array

Address ( A[i]) = M + (i – L ) * w

where M=base address

L=lower bound
w=word length
 Two-dimensional array
• In Matrix form elements store in 2D array

A two-dimensional array is stored in contiguous memory, but because memory is

linear, it is stored using either::

1. Row-Major Order

2. Column-Major Order
In Row-Major Order, elements are stored row by row.
A[0][0] A[0][1] A[0][2]
A[1][0] A[1][1] A[1][2]
A[2][0] A[2][1] A[2][2]
Stored in memory (Row-Major):
1,2,3,4,5,6,7,8,9
Address Calculation Formula (Row-Major)

LOC(A[i][j]) = Base(A) + [(i * N) + j] *W

Where:
LOC(A[i][j]) = address of element A[i][j],Base(A) = address of first element A[0][0]
i = row index,j = column index
N = total number of columns
W = size of each element (bytes)

Example : If the Base(A) = 1000

W = 4 bytes,N = 3 columns,Find address of A[2][1]

Here i=2,j=1,N=3,w=4
LOC(A[2][1]) = 1000 + [(2 * 3) + 1] * 4
= 1000 + (6+1)*4
= 1000 + 28=1028
In Column-Major Order, elements are stored column by column.

Address Calculation Formula (Column-Major):

LOC(A[i][j]) = Base(A) + [(j * M) + i] * W

Where:
LOC(A[i][j]) = address of element A[i][j],
Base(A) = address of first element A[0][0]
i = row index,j = column index
M = number of rows, W = size of each element (bytes)

Example: If Base(A) = 1000,W = 4 bytes,M = 3 [Link] address of A[2][1]

Here i=2,j=1,M=3,w=4
LOC(A[2][1]) = 1000 + [(1 *3) + 2] * 4
= 1000 + (3+2)* 4
= 1000 + 20
= 1020
If bounds are given as (A[LR…... UR][LC .....UC]):

•M = (UR - LR) + 1

•N = (UC - LC) + 1

LR: Lower Row Bound (starting index of rows; assumed 0 if unspecified)

LC: Lower Column Bound (starting index of columns; assumed 0 if unspecified)

M: Total Number of Rows in the array

N: Total Number of Columns in the array

Row major :
Address 𝐴 𝑖 𝑗 = 𝐵 + 𝑊 × 𝑁 × 𝑖 − 𝐿𝑅 + 𝑗 − 𝐿𝐶

Column major:
Address 𝐴 𝑖 𝑗 = 𝐵 + 𝑊 × 𝑖 − 𝐿𝑅 + 𝑀 × 𝑗 − 𝐿𝐶
QUESTION:

An array ARR[-5…15, 10…20] stores elements in Row

Major Wise with each element requiring 2 bytes of
storage. Find the address of ARR[10][15] when the
base address is 2500
ANSWER:
N = 20 – 10 + 1 = 11
Address of ARR[10][15] = B + W[N*(I – Lr) + (J – Lc)]
= 2500 + 2[11(10 – (-5)) + (15 – 10)]
= 2500 + 2[11(15) + 5]
= 2500 + 2[165 + 5]
= 2500 + 2[170]
= 2500 + 340
= 2840
QUESTION:

A matrix M[-6…10, 4…15] is stored in the

memory with each element requiring 4 bytes of
storage. If the base address is 1025, find the
address of M[4][8] when the matrix is stored in
column major wise.
ANSWER:

B = 1025, Lr = -6, Lc = 4,
R = 10 – (-6) + 1 = 10 + 6 + 1 = 17
I = 4, J = 8, W = 4
Address of M[4][8] = B + W[R*(J – Lc) + (I – Lr)]
= 1025 + 4[17(8 – 4) + (4 – (-6))]
= 1025 + 4[17 × 4 + (4 + 6)]
= 1025 + 4[68 + 10]
= 1025 + 4 × 78
= 1025 + 312
= 1337
1)A matrix MAT[10][15] is stored in the
memory in row major wise with each
element requiring 2 bytes of storage. If the
base address at MAT[1][2] is 2215, then
the address of MAT[3][7] will be?
Ans: 2285
2) A matrix M[-2…7, 2…10] is stored in the
memory with each element requiring 2 bytes
of storage. If the base address is 2140, find the
address of M[5][6] when the matrix is stored
in row major wise.
Ans:2274
MULTI DIMENTION ARRAY:
A multidimensional array is a data structure that stores
homogeneous data elements in a tabular or grid-like format
using multiple indices. It is essentially defined as an array of
arrays, expanding the concept of a linear 1D array into two or
more dimensions.
Syntax: Defined using multiple square brackets,
e.g.,data_type array_name[size1][size2]...[sizeN];. Int
A[i][j][k]………..[n]
Total Elements: Calculated by multiplying the sizes of all its
dimensions
Total Elements = ixjxkx…………n
Example:
2D Array (Matrix): Organized into rows and columns. Example: int
matrix[3][4] creates a grid with 3 rows and 4 columns.
3D Array (Cube): Stored as a collection of 2D arrays stacked on top of
each other, using depth, rows, and columns. Example: int
cube[2][3][4]
 Algorithm..
An algorithm is a step-by-step procedure to
solve a problem or achieve a desired result.
Characteristics of an Algorithm
[Link]: Takes zero or more inputs.
[Link]: Produces at least one output.
[Link]: Every step is clear and
unambiguous.
[Link]: Must terminate after a finite
number of steps.
[Link]: Each step should be simple
and executable
 AYSMPTOTIC NOTATION:
Asymptotic notations are mathematical tools used to describe the
time or space complexity of an algorithm as the input size (n) grows
toward infinity.
Three Main Asymptotic Notations
The efficiency of operations on data structures (like searching,
inserting, or deleting) is categorized into three primary bounds.
 OPERATIONS ON ARRAY
• Traversing
• Sorting
• Searching
• Insertion
• Deletion
• Merging
 Traversing
Traversing is the process of visiting or accessing each
element of a data structure exactly once in a
systematic order
Algorithm: Traversing an Array
[Link].
[Link] the array A and its size n.
[Link] i = 0.
[Link] i < n:
[Link] A[i].
[Link] i by 1.
[Link].
#include <stdio.h>
int main()
{
int A[] = {10, 20, 30, 40, 50};
int n = 5;
for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
return 0;
}
Complexity Analysis:

Time Complexity
•Best Case: O(n)
•Average Case: O(n)
•Worst Case: O(n)
Reason: The algorithm must visit all n elements of
the array, regardless of the input.
Space Complexity
•O(1) (Constant Space)
Reason: Traversing only uses a loop variable (such as
i) and does not require any additional memory
proportional to the array size.
 HOME WORK

[Link] a C program to read n integers into an

array and traverse the array to display the
elements in the same order.

[Link] a C program to traverse a two-

dimensional array and display its elements
row-wise.
 SORTING
This operation is used to arrange the elements in the array in
ascending or descending order
Algorithm :

[Link].
[Link] the number of elements n.
[Link] the array elements.
[Link] for i = 0 to n - 2:
[Link] for j = 0 to n - i - 2:
[Link] A[j] > A[j + 1], swap A[j] and A[j + 1].
[Link] the sorted array.
[Link].
BUBBLE SORT: if(a[j] > a[j + 1])
#include <stdio.h> {
int main() temp = a[j];
{ a[j] = a[j + 1];
int a[10], n, i, j, temp; a[j + 1] = temp;
printf("Enter the number of elements: "); }
scanf("%d", &n); }
printf("Enter the array elements:\n"); }
for(i = 0; i < n; i++) printf("Sorted array in ascending
{ order:\n");
scanf("%d", &a[i]); for(i = 0; i < n; i++)
} {
for(i = 0; i < n - 1; i++) printf("%d ", a[i]);
{ }
for(j = 0; j < n - i - 1; j++) return 0;
{ }
• Complexity Analysis:

• Time Complexity
• Best Case: O(n) (when the array is already
sorted, with an optimized Bubble Sort)
• Average Case: O(n²)
• Worst Case: O(n²)
• Space Complexity
• O(1) (constant extra space)
SEARCHING:
This operation is used to search for an element in the given array.
This method involves traversing the dataset sequentially, checking
every element one by one(sequential /linear searching).

ALGORITHM:
[Link]
[Link] I = 0
[Link] steps 4 and 5 while I < N
[Link] A[I] is equal ITEM THEN GOTO STEP 6
[Link] I= I +1
[Link] I, ITEM
[Link]
#include <stdio.h>
void linear_search(int a[], int n, int key)
{
int i, count = 0;
for(i = 0; i < n; i++)
{
if(a[i] == key) //compares each element in array
{
printf("The element is found at %d position\n",
i+1);
count = count + 1;
}
else
printf("The element is not present in the
array\n");
}}
int main()
{
int key=18; n = 6;
int a[10] = {12, 44, 32, 18, 4, 10};
linear_search(a, n, key);
return 0;
• Complexity Analysis
• Best Case (O(1)): The target element sits at the
very first position of the collection.
• Worst Case (O(N)): The target element sits at the
last position or is missing entirely.
• Average Case (O(N)): The target element is found
somewhere in the middle of the collection.
• Space Complexity (O(1)): It requires a constant
amount of memory as no additional data
structures are created
 INSERTION….
This operation is used to insert an element into the
array i.e adding a new element into an existing container
at a specific position
 INSERTION …..
Algorithm : InsertArray(KEY, LOCATION)

Input: KEY is item to insert,

LOCATION is index where KEY is to be inserted

Output: The array A with KEY element

Data Structure: Array A [ L …. U ] // L=lower bound & U=upper bound of A

Insertion…

While i >= LOCATION do

DELETION…This operation is used to delete an
element into the array
DELETION…

Algorithm DELETE(KEY)

Input: KEY is the element to be deleted

Output: Array A without KEY element

Data Structure: Array A [ L …. U ] // L=lower bound & U=upper bound of A

Deletion…
MERGING… This operation is used to compact the elements
from two different arrays into a single array
MERGING…

Algorithm MERGE(A1, A2, A)

Input: Two arrays A1[L1….U1] and A2[L2….U2]

Output: Resultant Array A[L…U] where L=L1 and U=U1+ ( U2-L2+1)

when A1 is appended after A2

Data Structure: Array structure

Merging…
 SPARSE MATRICES
• A matrix is a two-dimensional data object made
of m rows and n columns having most of the
elements of the matrix 0 value, then it is called a
sparse matrix.
• Why to use Sparse Matrix instead of simple
matrix ?
• Storage: Lesser memory can be used to store
only non zero elements.
• Computing time: Computing time can be saved
by logically designing a data structure traversing
only non-zero elements..
example

• 00304
00570
00000
02600
SPARSE MATRICES- CLASSIFICATION
Different symmetric sparse matrices

-Triangular matrices
-Upper left, upper right, lower-left, lower-right
-Diagonal matrices
-Diagonal matrices
-Tridiagonal matrices
TRIANGULAR MATRICES
 DIAGONAL MATRIX - a matrix having non-zero
elements only in the diagonal running from the upper left to the
lower right or upper right to lower left
TRIDIAGONAL MATRICES -hasnonzero
elements only on the main diagonal, the first diagonal below
this, and the first diagonal above the main diagonal

EXAMPLE :
αβ- BAND MATRIX : non-zero entries are
confined to a diagonal band, comprising the main
diagonal and zero or more diagonals on either side
Array representation of Sparse matrix

2D array is used to represent a sparse matrix in which there are three rows named
as
•Row: Index of row, where non-zero element is located

•Column: Index of column, where non-zero element is located

•Value: Value of the non zero element located at index - (row,column)

#include<stdio.h>
Sparse matrix
int main()
{
// Assume 4x5 sparse matrix
int sparseMatrix[4][5] = { {0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 }, {0 , 0 , 0 , 0 , 0 }, {0 , 2 , 6 , 0 , 0 }
};
int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;
int compactMatrix[3][size];
// Making of new matrix
int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
• {
• compactMatrix[0][k] = i;
• compactMatrix[1][k] = j;
• compactMatrix[2][k] = sparseMatrix[i][j];
• k++;
• }
• for (int i=0; i<3; i++)
• {
for (int j=0; j<size; j++)
printf("%d ",compactMatrix[i][j]); printf("\n");
• }
return 0;
}