Array
overview
Ø Collection of homogeneous data elements stored at
contiguous memory location
Ø Size of array is to be decided during
declaration
Ø Size can not be changed at later stages
For
1D array:
Let n is number
of elements in array then size of array is n. If lb is lowest index and ub is the largest index
then,
size of array = ub – lb + 1
Ø To access an element in array, we write
name_array[subscript] like
ARR[i]
OR
name_array(subscript) like ARR(i)
OR
name_arraysubscript like ARRi
Memory
representation 1D–
Address of first element of array a is known as base
address – base(a)
So, kth element address is given by,
loc(a[k]) = base(a) + w * (k - lb) where, w is number of bytes per element
Ø To access any element in array constant time
is needed because other elements
scanning is
not required.
For
2D array (matrices):
Ø Two subscripts are needed to access any
element.
Let m and n are
the number of rows and columns in array then,
Size
of 2D array = m x n
Ø To access an element in array, we write
name_array[rsubscript][csubscript] like ARR[i][j]
OR
name_array(rsubscript, csubscript) like ARR(i][j)
OR
name_arrayrsubscript csubscript like ARRi,j
OR
name_array[rsubscript, csubscript] like ARR[i,j] used in PASCAL
Memory
representation of 2D Array–
Address of first element of array a is known as base
address – base(a)
Row
major order:
Let w is number of bytes per element, lbc is lower bound of
columns and lbr is lower bound of
rows.
So, ij
element address in array of mxn is given by,
loc(a[i] [j]) = base(a) + w
* [n*(i - lbr) + (j - lbc)] In Fortran
loc(a[i]
[j]) = base(a) + w * [n* i + j ] In
C/C++
00
|
01
|
02
|
03
|
10
|
11
|
12
|
13
|
20
|
21
|
22
|
23
|
30
|
31
|
32
|
33
|
40
|
41
|
42
|
43
|
Let base(a) = 2013
loc[2][1] = 2013
+ 2 * [ 4 * 2 + 1]
= 2013 + 2 * 9
= 2031
NOTE: C uses row major order
for 2D arrays.
Column
major order:
Let w is number of bytes per element, lbc is lower bound of
columns and lbr is lower bound of
rows.
So, ij
element address in array of mxn is given by,
loc(a[i] [j]) = base(a) + w
* [m*(j - lbc) + (i - lbr)]
loc(a[i]
[j]) = base(a) + w * [m* j + i ] In C/C++
00
|
01
|
02
|
03
|
10
|
11
|
12
|
13
|
20
|
21
|
22
|
23
|
30
|
31
|
32
|
33
|
40
|
41
|
42
|
43
|
Let base(a) = 2013
loc[2][1] = 2013
+ 2 * [ 5 * 1 + 2]
= 2013 + 2 * 7
= 2027
NOTE: Fortran uses row major
order for 2D arrays.
Problem1
Find the time complexity in term of Big-Oh
for (int i = 0; i < 100; i++){
for (int j = 0; j < n; j++)
//do something in constant time
}
Ans: O(n)
Problem
2
double
percentage[50];
If this array percentage
is stored in memory
starting from address 3000. then what will be the address of percentage[20] element.
Ans: 3000+20*8= 3160
What will be size of array in bytes?
Ans:400
Sparse
Matrices
Ø Many of its elements
are zero
Ø If not sparse then it is called dense
matrix
Ø As many of its elements are zero, we can
save space by storing only non-zero elements.
Example1:
Example2:
Advantage
of Sparse Matrices
Using
sparse matrices to store data that contains a large number of zero-valued
elements can both save a significant amount of memory and speed up the
processing of that data.
Operations
on arrays
Traversing – Visiting each element exactly once. Complexity
is O(n)
Searching – 1. Linear Search 2. Binary Search
Insertion – Insert an
element at given position. Complexity is O(n)
Deletion – Remove an
element from given position. Complexity is O(n)
Sorting – Arrange the
elements of array on some logical order
1. Bubble sort 2.
Insertion sort 3. Selection sort 4. Quick sort 5.
Merge sort
Insertion – Insert an
element at index location k.
Insert(A[N],k,P)
1.Set i=N
2.While(i>=k)
3. A[i+1]=A[i]
4. i=i-1
5.A[k]=P
6.N=N+1
7.STOP
Deletion – Remove an element from index location k.
Delete(A[N],k)
1.Set D=A[k]
2.i=k
3.While(i<=N-2)
4. A[i]=A[i+1]
5. i=i+1
6.N=N-1
7. STOP
No comments:
Post a Comment