ARRAY
ARRAY is a collection of homogeneous data type (elements)
Characteristics of Array
1. All element stored on consecutive memory location
2. All element can be accessed using a set of index
Defining ARRAY
In C language:
Data type name [size] 0 1 2 3 4
A[0] A[1] A[2] A[3] A[4]
int A[5]
Assuming each size 2 bytes
Starting Index 0 Lower Bound (LB)
Last Index size -1 Upper Bound (UB)
Defining ARRAY
In Data Structure:
name [LB: UB] Size = UB – LB + 1
Ex: A[2 : 15]
B [5: 18]
C [-2 : 6]
D [-15: -5]
Location of an ARRAY element
Loc(A[i]) = B + W * ( i - LB) W = size of each element
B = Base address of Array
0 1 2 3 4
A[0] A[1] A[2] A[3] A[4]
200
1 2 3 4 5
A[0] A[1] A[2] A[3] A[4]
200
2 3 4 5 6
A[0] A[1] A[2] A[3] A[4]
200
Relative index of i = no of elements stored in array before element at index
Questions on ARRAY
Q1. Consider an array A[8: 16]. Total number of elements in array
Q2. Consider an array A[-7 : 13]. Each element take 2 locations in
the memory. Total Space needed to store the array?
Q3. Consider an Array A[-5 : 18], which is stored in array starting
memory location 1000. Each element take 4 locations in memory.
The location of element A[5] is?
Traversing in ARRAY
for ( i = LB ; i<=UB ; i++)
{
Visit A[i];
}
Runtime complexity = Theta(n) [always run n times]
Insertion in ARRAY
Insertion in Array : At the end
0 1 2 3 4
A[0] A[1] A[2] A[3] A[4]
Algo:
Insertion (item);
{
if (UB = = Array_max_index) ## condition of overflow
UB + +;
A[UB] = item;
n + +;
}
Runtime complexity = O(1)
Insertion in ARRAY
Insertion in Array : At the end
Algo:
Case 1: index = UB + 1
0 1 2 3 4 Insertion (item, index);
A[0] A[1] A[2] A[3] A[4] {
for (K = UB; K>= index; K- -)
Case 2: index = LB < index < UB {
0 1 2 3 4 A[ k+1] = A[k];
}
A[0] A[1] A[2] A[3] A[4]
A[index] = item;
UB + +;
n + +;
Case 3: index = LB }
0 1 2 3 4
A[0] A[1] A[2] A[3] A[4]
Runtime complexity = O(n)
Finding Minimum in ARRAY
15, 8, 9, 7, 12, 19, 20, 4, 21, 2, 11, 6, 1, 5
Min =
No. of Comparison = n-1 Runtime complexity = Theta(n)
Algo:
Min = A[LB];
for ( i = LB +1 ; i<=UB ; i++)
{
if (A[i]) < min
{
min = A[i];
}
}
Return min;
Finding Maximum in ARRAY
15, 8, 9, 7, 12, 19, 20, 4, 21, 2, 11, 6, 1, 5
Max =
No. of Comparison = n-1 Runtime complexity = Theta(n)
Algo:
Max = A[LB];
for ( i = LB +1 ; i<=UB ; i++)
{
if (A[i]) > max
{
max = A[i];
}
}
Return max;
Linear Search in ARRAY
Linear Search
0 1 2 3 4
A[0] A[1] A[2] A[3] A[4] A[5] A[6]
Algo:
for (K = LB; K<= UB; K+ +)
{
if (A[ k] = = item) ## successful search
return k;
}
return (LB – 1); ## Unsuccessful search
}
Runtime complexity = O(n)
Binary Search in ARRAY
0 1 2 3 4 5 6
A[0] A[1] A[2] A[3] A[4] A[5] A[6]
Binary Search in ARRAY
Algo:
Binary_search (A[], LB, UB, item)
{
L= LB; H = UB; mid = [(L+H)/2]
while ((A[mid]!= = item) && (L<= H)))
{
if (item > A[mid]) then L= mid + 1;
else H = mid – 1;
mid = [(L+H)/2]; ## successful search
}
if (A[mid] = = item) then
return mid;
else
return LB-1; ## Unsuccessful search
}
Runtime complexity = O(log n)
2 D ARRAY
In C language:
type name [size 1] [size 2]
int A[3] [4]
2 D ARRAY
In Data Structure:
Here we have no fixed Lower Bound A2-3 A2-2 A2-1 A20
A3-3 A3-2 A3-1 A20
type name [Lbi : UBi] [LBj: UBj] A4-3 A4-2 A4-1 A20
A5-3 A5-2 A5-1 A20
int A[2:5] [-3:0]
How to get the no. of rows (m) = Ubi – Lbi + 1
How to get the no. of columns(n) = Ubj – Lbj + 1
-----------------------------------------------------------------
Total no of element in array = m*n
2 D ARRAY
In Data Structure:
A A A A
A[0: 2][0:3] A A A A
A A A A
B[2:6][3:9] A A A A
C[-2: 2] [-9 : -5]
2 D ARRAY
In Data Structure:
A A A A
How to store this array in memory ? A A A A
A A A A
1. Row major Order A A A A
2. Column Major order
Row Major Order (RMO)
In Data Structure:
A2-3 A2-2 A2-1 A20
A3-3 A3-2 A3-1 A30
A4-3 A4-2 A4-1 A40
A5-3 A5-2 A5-1 A50
A2-3 A2-2 A2-1 A20 A3-3 A3-2 A3-1 A30 A3-3 A3-2 A3-1 A40 A3-3 A3-2 A3-1 A50
Column Major Order (CMO)
In Data Structure:
A2-3 A2-2 A2-1 A20
A3-3 A3-2 A3-1 A30
A4-3 A4-2 A4-1 A40
A5-3 A5-2 A5-1 A50
A2-3 A3-3 A4-3 A5-3 A2-2 A3-2 A4-2 A5-2 A2-1 A3-1 A4-1 A5-1 A20 A30 A40 A50
Find Location: RMO
In Data Structure:
Loc(A[i][j]) = Base + w * (relative index of A[i][j])
= Base + w * (no. of element from LBi to i-1 rows
+ no. of element from LBj to j-1
column with i-th rows )
Loc(A[i][j]) = Base + w * [(i-LBi)n + (j-LBj)]
Find Location: CMO
In Data Structure:
Loc(A[i][j]) = Base + w * (relative index of A[i][j])
= Base + w * (no. of element from LBj to j-1 rows
+ no. of element from LBi to i-1
within column j)
Loc(A[i][j]) = Base + w * [(j-LBj)m + (i-LBi)]
Lower Triangular Matrix
Should be the square matrix
If (I < j) A11 A12 A13 A14
Aij = 0 A21 A22 A23 A24
Else
A31 A32 A33 A34
Aij 0
A41 A42 A43 A44
A11 A21 A22 A31 A32 A33 A41 A42 A43 A44
Loc(A[i][j]) = Base + w * [no. of element from 1 to i-1 rows + (j-LBj)]
= Base +w * [i(i-1)/2 + (j-1)]
-----------------------------------------------------------------------------------------------------------
Loc(A[i][j]) = Base + w * [no. of element from 1 to j-1 + (i-LBi)]
= Base +w * [n(j-1) – (j-1)(j-2)/2 + (i-j)]
Upper Triangular Matrix
Should be the square matrix
If (i > j) A11 A12 A13 A14
Aij = 0 A21 A22 A23 A24
Else
A31 A32 A33 A34
Aij 0
A41 A42 A43 A44
A11 A21 A22 A31 A32 A33 A41 A42 A43 A44
Loc(A[i][j]) = Base +w * [n(i-1) – (i-1)(i-2)/2 + (j-i)]
-----------------------------------------------------------------------------------------------------------
Loc(A[i][j]) = Base +w * [j(j-1)/2 - (i - 1 )]