Data Structure & Algorithms

Chapter 3:
Arrays
Contents
• Introduction
• Memory Representation of Array
• Types of Array
– 1D/ Single Dimensional Array
– Multi-Dimensional Array
• Operations of arrays
Introduction
• An array is a collection of variables of the same
type that are referenced by a common name.
OR
• A list of finite number n of similar(homogeneous) data
elements.
• A[1],A[2],A[3]…..A[N]
• The number K in A[K] is called a subscript and A[K] is
called subscripted variable.
• Arrays are a way to group a number of items into larger
unit.
Introduction
• The elements of the array are referenced respectively
by an index set.
• The elements of the array are stored respectively in
successive memory locations.
• The number of elements is called the length or size of
the array.
• LENGTH = UB-LB+1
• UB: Upper bound (largest index)
• LB: Lower
10 20 bound
30 5(smallest
2 0 index)
4 100 LB=0
0 1 2 3 4 5 6 7 UB=7
Representation of Array in Memory
• Memory of computer is simply a sequence of addressed
locations.
1001 1002 1003 1004 1005

… … … … …

… … … … 1015

• Computer does not need to keep track of the address of

every element of LA.
• Needs to keep track only of the address of the first element
of LA, denoted by Base(LA), called the base address of LA.
• LA: Linear Array
Representation of Array in Memory
• Using this address Base(LA),
• The computer calculates the address of any
element of LA by the following formula:
• LOC(LA[K]) = Base(LA) + w(K – Lower bound)
• Where w is size of data type of LA.
LOC(LA[K]) = Base(LA) + w(K – Lower bound)
• LOC(AUTO[1964]) = 200 + 4(1964 - 1932)
• LOC(AUTO[1964]) = 200 + 4(32)
• LOC(AUTO[1964]) = 200 + 128
• LOC(AUTO[1964]) = 328
Types of Arrays
• Arrays are of different types:
1. Single-dimensional arrays, consist of finite
homogenous(same type) elements.
2. Multi-dimensional arrays
Two-dimensional arrays, consist of elements, each of
which is itself an array.
Single Dimensional Arrays
• The simplest form of an array.
• The array is given a name and its elements are
referred to by their subscripts or indices.
• Index of first element is known as lower bound.
• Index of the last element is known as upper bound.
Declaration of Single-dimensional Array
data_type array-name[ size ];
• data_type declares the base type of array.
– Type of each element in the array
• array-name specifies the name with which the array
will be referenced.
• Size defines how many elements the array will hold.
– The size must be an integer value or integer constant
without any sign.
• For e.g. int marks[10];
• The above statement declared array marks with 10 elements, marks[0] to marks[9].
Initialization of Array
• data_type array-name[size]={elmnt-1,elmnt-2,..,elmnt-n};
or
• data_type array-name[ ]={elmnt-1,elmnt-2,..,elmnt-n};
For example:
• int marks[5]={50,25,72,45,30};
• float price[5] = {30.50, 250.5, 50.50, 175.50, 90.50};
• char grade[5 ] = {‘A’ , ‘B’ , ‘C’ , ‘D’ , ‘E’ };
or
• int marks[ ]={50,25,72,45,30};
• float price[ ] = {30.50, 250.5, 50.50, 175.50, 90.50};
• char grade[ ] = {‘A’ , ‘B’ , ‘C’ , ‘D’ , ‘E’ };
Algorithm for an array
1. Start
2. Set MARKS[] = {1,2,3,4,5}
3. Set SIZE = 5
3. Repeat i = 0 to SIZE-1, i++
WRITE: MARKS[i]
[End of loop]
4. Exit
Operations of Arrays
1. Traversing : Pass through / Visiting
2. Searching : Finding
3. Insertion : Adding
4. Deletion : Removing
5. Sorting : Arranging
6. Merging : Combining
Traversing Linear Array
• It means processing or visiting each element in the
array exactly once;
• Let ‘A’ is an array stored in the computer’s
memory. If we want to display the contents of
‘A’, it has to be traversed i.e. by accessing and
processing each element of ‘A’ exactly once.
Inserting into Array
• Inserting an element at the end of a array can be easily done .
• Inserting an element at the middle or beginning of LA , first we
move downwards remaining elements.

Deleting from Array

• Deleting an element from the end of a array can be easily
done .
• Deleting an element from the middle or beginning of
array , first we move upwards remaining elements.
Sorting in Linear Array:
• Sorting an array is the ordering the array
elements in
• Ascending (increasing from min to max) or
• Descending (decreasing – from max to min) order.
• Example:
• {2 1 5 7 4 3} -> {1, 2, 3, 4, 5,7} ascending order
• {2 1 5 7 4 3} -> {7,5, 4, 3, 2, 1} descending order
Sorting Techniques
1. Insertion Sort
2. Selection Sort
3. Bubble Sort
4. Shell Sort
5. Heap Sort
6. Quick Sort
7. Merge Sort
8. Radix Sort
9. Bucket Sort
Searching in Linear Array:
• The process of finding a particular element of an
array is called Searching”.
• If the item is not present in the array, then the
search is unsuccessful.
• If the item is present in the array, then the search is
successful.
• There are two types of search (Linear search and
Binary Search)
Linear Search:
• The linear search compares each element of the array with the
search key until the search key is found.
• To determine that a value is not in the array, the program must
compare the search key to every element in the array.
• It is also called “Sequential Search” because it traverses the data
sequentially to locate the element.
Binary Search:
• It is useful for the large sorted arrays.
• The binary search algorithm can only be used
with sorted array.
• Eliminates one half of the elements in the array
being searched after each comparison.
• The algorithm locates the middle element of the
array and compares it to the search key.
• If they are equal, the search key is found and
array subscript of that element is returned.
C Program for Array Initialization
#include<stdio.h> OUTPUT :
Marks of 5 students are :
int main( ) { 50 60 70 80 90

int marks[ ]={50,60,70,80,90} ;

printf("Marks of 5 students are”);
for( int i=0; i < 5; i++ )
printf(“%d”, marks[i]);
}
Multidimensional arrays:
• In Multi-D arrays, elements referenced by more
than one subscript.

• The general syntax of a multidimensional array is :

• data_type array_name[size-1][size-2]………[size-n];
Multidimensional arrays:
For example :
• int A[5][2][3];
• float B[2][5][3];

• The simplest form of a multidimensional array is a

two-dimensional array.

• Which is also known as array of an array.

Two-dimensional Arrays
• Also known as array of an array
• A double dimensional array is an array in which
each element is itself an array.
• For example, an array A[R][C] is an R by C table with R
rows and C columns containing R * C elements.
• The number of elements in a two-dimensional
array can be determined by multiplying number of
rows with number of columns.
• For example, the number of element in an array A[4]
[3] is calculated as 4 * 3 = 12.
Representation of 2-D Array in memory

A[1][2]
Implementation of Two-dimensional array in
Memory
• While storing the elements of a 2-D array in
memory, these are allocated contiguous memory
locations.
• A two-dimensional array can be implemented in a
programming language in two ways :
• 1. Row-major implementation
• 2. Column-major implementation
Row-major implementation :
• Row-major implementation is a linearization
technique in which elements of array are read
from the keyboard row-wise.
• i.e. the complete first row is stored, then the
complete second row is stored and so on.
• For example, an array A [3] [3]is stored in the
memory as shown in Fig.(1) below :
Row-major implementation :
• The storage can be clearly understood by arranging
array as matrix as shown below :
Column-major implementation :
• Column-major implementation is a linearization
technique in which elements of array are read from
the keyboard column-wise.
• i.e. the complete first column is stored, then the
complete second column is stored and so on.
• For example, an array a[3][3] is stored in the
memory as shown in Fig.(1) below :
Column-major implementation :
• The storage can be clearly understood by arranging
array as matrix as shown below :
Two Dimensional Array declartion :

• data_type array_name[rowSize][colSize];
• For e.g.
• int A[4][3];
• Where int is data type, A is array variable_name, 4
is row size and 3 is column size.
Two Dimensional Array initialization :
• data_type array_name[rowSize][colSize]={
{1st row elements},
{2nd row elements},
………
};
• For e.g.
• int A[4][3]={{1,2,3}, {4,5,6,}, {7,8,9}, {10,11,12}};