Data Structure & Algorithms

Chapter 3:
Array / Linear Array
Contents
3.1 Introduction
3.2 Representation of Array in memory
3.3 Operations of arrays
3.3 Traversing Linear Array
3.4 Inserting and Deleting
3.5 Searching Linear Array
3.5.1 Linear Search
3.5.2 Binary Search
3.6 Multidimensional array.
3.7 2-D Arrays
3.7 Representation of 2-D array in memory
3.1 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.
3.1 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 n 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
Operations of Arrays
1. Traversing : Pass through / Visiting
2. Searching : Finding
3. Insertion : Adding
4. Deletion : Removing
5. Sorting : Arranging
6. Merging : Combining
Types of Arrays
• Arrays are of different types:
1. Single-dimensional arrays, consist of finite
homogenous(same type) elements.
2. Multi-dimensional arrays
1. Two-dimensional arrays, consist of elements, each of
which is itself an array.
Single-Dimensional
Arrays
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 ] = {‘D’ , ‘A’ , ‘B’ , ‘A’ , ‘C’ };
or
• int marks[ ]={50,25,72,45,30};
• float price[ ] = {30.50, 250.5, 50.50, 175.50, 90.50};
• char grade[ ] = {‘D’ , ‘A’ , ‘B’ , ‘A’ , ‘C’ };
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.
Traversing Linear Array

The alternate algorithm for traversing (using for loop) is :

Inserting into LA
• Inserting an element at the end of a LA can be easily done .
• Inserting an element at the middle or beginning of LA , first
we move downwards remaining elements.
Deleting from LA
• Deleting an element from the end of a LA can be easily
done .
• Deleting an element from the middle or beginning of LA ,
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
Bubble Sort:
• The technique we use is called “Bubble Sort”
• Because the bigger value gradually bubbles their way up to
the top of array like air bubble rising in water,
• While the small values sink to the bottom of array.
• This technique is to make several passes through the
array.
• On each pass, successive pairs of elements are compared.
• If a pair is in increasing order (or the values are identical),
we leave the values as they are.
• If a pair is in decreasing order, their values are swapped in the
array.
Convert this algorithm into C++/C language program.
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.
• 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.
Computational Complexity of Linear Search

• Note that the Computational Complexity of the Linear

Search is the maximum number of comparisons you need
to search the array.
• As you are visiting all the array elements in the worst
case, then, the number of comparisons required is:
• n (n is the size of the array)
Example:
• If a given an array of 1024 elements, then the
maximum number of comparisons required is:
• n-1 = 1023 (As many as 1023 comparisons may be required)
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.
Binary Search:
• If the search key is less than the middle element of
array, the first half of the array is searched.

• If the search key is not the middle element of in

the specified sub array, the algorithm is
repeated on one quarter of the original array.
Binary Search
Binary Search
Computational Complexity of Binary Search
• The Computational Complexity of the Binary Search algorithm
is measured by the maximum (worst case) number of
Comparisons it performs for searching operations.
• The searched array is divided by 2 for each comparison/iteration.
• Therefore, the maximum number of comparisons is measured
by: log2(n) where n is the size of the array
Example:
• If a given sorted array 1024 elements, then the maximum
number of comparisons required is:
• log2(1024) = 10 (only 10 comparisons are enough)
Program 1 : WAP for Array Initialization
#include<iostream.h>
OUTPUT :
#include<conio.h> Marks of 5 students are :
void main( ) { 50 60 70 80 90
// Array declaration and initialization
int marks[ ]={50,60,70,80,90} ;
clrscr( );
// Array output
Cout<<"\n Marks of 5 students are : \n”;
for( int i=0; i < 5; i++ )
cout<<marks[i];
getch( );
}
Program 2 : WAP for array input from user
#include<stdio.h>
#include<conio.h>
void main( ) {
int marks[5]; // array declaration
clrscr( );
OUTPUT :
cout<<"enter marks of 5 students : \n”; // array input
Enter marks of 5 students :
50 60 70 80 90
for( int i=0; i<5; i++)
cin>>marks[i];

cout<<"\n marks of 5 students are : \n"; // array output

for ( int i=0; i<5; i++)
cout<<marks[i];
getch( );
}
Program 3:
• WAP & Algo: to display the largest and smallest
element of an array

OUTPUT :
Enter 5 elements of an array :
39518
Largest element in array : 9
Smallest element in array : 1
Program 4 :
• WAP & Algo: to display the sum and average of
elements of an array
OUTPUT :
Enter 5 elements of an array :
2 4 6 8 10
Sum : 30.00
Average : 6.00
Program 5 :
• WAP & Algo: to insert a number in an array
OUTPUT :
Enter size of array (max. 10) : 5
Enter 5 elements of array :
2 4 8 10 12
Original array is :
2 4 8 10 12
Enter the element to be inserted : 6
Enter the position of insertion : 3
New array after insertion :
2 4 6 8 10 12
Program 6 :
• WAP & Algo: to delete a number from an array
• Output:
Enter the size of array (max. 10) : 5
Enter 5 elements of an array :
2 4 6 8 10
Original array is :
2 4 6 8 10
Enter the element to delete : 6
New Array after deletion :
2 4 8 10
Multi-Dimensional
Arrays
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
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 :
Double 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.
Double 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}};
Array input from user :
Row major form Column major form

for(r=0;r<4;r++) { for(c=0;c<3;c++) {
for(c=0;c<3;c++) { for(r=0;r<4;r++) {
cin>>a[r][c]; cin>>a[r][c];
} }
} }
Assignments
• Program 1 : Matrix Initialization & Output
OUTPUT :
• Given 4 * 3 matrix is :
1 2 3
4 5 6
7 8 9
10 11 12
Program 2 : Matrix Input & Output

OUTPUT :
• Enter elements of a 4 * 3 matrix :
1 2 3
4 5 6
7 8 9
10 11 12
• Given 4 * 3 matrix is :
1 2 3
4 5 6
7 8 9
10 11 12
Program 3 : Addition of Two 3 * 3 Matrices
• Enter elements of first 3 * 3 matrix :
1 2 3
4 5 6
7 8 9
• Enter elements of second 3 * 3 matrix :
2 3 4
5 6 7
8 9 10
• Addition of first two matrices :
3 5 7
9 11 13
15 17 19
Program 4 : Transpose of a 3 *3 matrix
• Enter elements of a 3 * 3 matrix :
1 2 3
4 5 6
7 8 9
• Original matrix is :
1 2 3
4 5 6
7 8 9
• Transpose of given matrix is :
1 4 7
2 5 8
3 6 9
Program 5 : Multiply two 3 * 3 matrices
• OUTPUT :
• Enter elements of first 3 * 3 matrix :
1 2 3
4 5 6
7 8 9
• Enter elements of second 3 * 3 matrix :
1 2 3
4 5 6
7 8 9
• Product of first two 3 * 3 matrices :
30 36 42
66 81 96
102 126 150