03 Linear Arrays Memory Representations .pdf

Dsa

1. Data Structures & Algorithms
By
Dr. Prakash Singh Tanwar
Associate Professor
Lovely Professional University, Punjab
Topic:Linear Arrays Memory
Representations

2. Linear Arrays Memory
Representation
BasicTerminology
LinearArray
MemoryRepresentationofLinearArray
TraversingArray
InsertionandDeletioninArray
Sorting(BubbleSort)
Searching(LinearSearchandBinarySearch)
ReviewQuestions
By:Dr. Prakash Singh Tanwar

3. Basic Terminology
LinearDataStructures:
Adatastructureissaidtobelinearifitselementsforma
sequenceoralinearlist.
LinearArray:
Itisalistofafinitenumbernofhomogeneousdata
elements(sametypeofdataelements)suchthat:
•(a)theelementsofthearrayarereferencedbyanindexset
consistingofnconsecutivenumbers.
•(b)theelementsofthearrayarestoredrespectivelyinsuccessive
memorylocations
By:Dr. Prakash Singh Tanwar

4. Revision
Definition
Arrayisagroupofvariablesofsamedatatype
havingacommonname.
Elementsofanarraycanbeaccessedthrough
itssubscript(0ton-1)wherenisthesizeof
array.
Continousmemoryallocation
By:Dr. Prakash Singh
Tanwar

5. Revision: 1D Array
Asingle-dimensionalor1-Darrayconsistsof
afixednumberofelementsofthesamedata
typeorganizedasasinglelinearsequence.
Arraydeclaration
Syntax
Ex
<data_type> <array_name>[<size>];
inta[5];
char name[20];
floatnum[4];
By:Dr. Prakash Singh Tanwar

6. Revision: 1D Array
Arraydeclaration
a[0]a[1]a[2]a[3]a[4]
20inta[5];
a[0]=9;
a[1]=6;
a[2]=7;
a[3]=5;
a[4]=20;
9 6 75
By:Dr. Prakash Singh Tanwar

7. 1D Array Memory
Representation
Arraydeclaration
a[0]a[1]a[2]a[3]a[4]
20
inta[5];
a[0]=9;
a[1]=6;
a[2]=7;
a[3]=5;
a[4]=20;
9 6 7 5
10011003100510071009
size ofint= 2 bytes
&a[0]= 1001
&a[1]= 1001+2=1003
&a[2]= 1003+2=1005
&a[3]= 1005+2=1007
&a[4]= 1007+2=1009
size ofint= 2 bytes
&a[0]= 1001
&a[1]= 1001+2=1003
&a[2]= 1003+2=1005
&a[3]= 1005+2=1007
&a[4]= 1007+2=1009
Note: size ofintin 32 bit compiler =2 bytesNote: size ofintin 32 bit compiler =2 bytes
By:Dr. Prakash Singh Tanwar

8. 1D Array Memory
Representation
Arraydeclaration
a[0]a[1]a[2]a[3]a[4]
20
inta[5];
a[0]=9;
a[1]=6;
a[2]=7;
a[3]=5;
a[4]=20;
9 6 7 5
10011005100910131017
size ofint= 4 bytes
&a[0]= 1001
&a[1]= 1001+4=1005
&a[2]= 1005+4=1009
&a[3]= 1009+4=1013
&a[4]= 1013+4=1017
size ofint= 4 bytes
&a[0]= 1001
&a[1]= 1001+4=1005
&a[2]= 1005+4=1009
&a[3]= 1009+4=1013
&a[4]= 1013+4=1017
Note: size ofintin 64 bit compiler =4 bytesNote: size ofintin 64 bit compiler =4 bytes
By:Dr. Prakash Singh Tanwar

9. Q/A
Arethesevalidstatements?
inta[10];
a[10]=10;
a[10]=10; is not valid
Because, in array a[10] we have only 10 elements
from a[0] to a[9]
By:Dr. Prakash Singh Tanwar

10. 1D Array Memory
Representation
Arraydeclaration
Sizeofchar
•1byte
Ex
•ArraySize
4characters
•Subscript
0to3
n[0]n[1]n[2]n[3]
char n[4];
5001500250035004
size of array
By:Dr. Prakash Singh Tanwar

11. Basic Terminology
Size/LengthofArray
IndexofArray
UpperboundandLowerboundofArray
By:Dr. Prakash Singh Tanwar
a[0]a[1]a[2]a[3]a[4]
Size / Length ofArray=5
Index of array : 0 to 4
Lower Bound Upper Bound

12. Traversing Linear Array
Supposewehavetocountthenumberofelementinan
arrayorprintalltheelementsofarray.
By:Dr. Prakash Singh Tanwar
Algorithm1: (Using While Loop)
1.[Initialize Counter.] Set K = LB.
2.RepeatStep 3 and 4 while K<= UB.
3. [Visit Element.] Apply PROCESS to A[K].
4. [Increase Counter.] Set K = K+1.
[End of Step 2 Loop.]
5.Exit.
a[0]a[1]a[2]a[3]a[4]
209 6 7 5
K
LB UB

13. Traversing Linear Array
Algorithm2:(Usingforloop)
By:Dr. Prakash Singh Tanwar
1.Repeat for K = LB to UB
Apply PROCESS to A[K].
[ End of Loop.]
2.Exit.
a[0]a[1]a[2]a[3]a[4]
209 6 7 5
K
LB UB

14. Q/A
Question.1:FindtheNumberofelementsinanarray
whicharegreaterthan25
Question2:Findoutthesumofallthetwodigit
numbersinanarray.
By:Dr. Prakash Singh Tanwar
a[0]a[1]a[2]a[3]a[4]
2025 6 27 5
K
LB UB

15. Insertionin an Array
Twotypesofinsertionare
possible:
Insertionattheendofarray
Insertioninthemiddleofthearray
By:Dr. Prakash Singh Tanwar

16. Insert an element in an
Array
Writeaprogramtoinsertanelementin
anarray?
Wheretoinsert?
Whatarethecurrentelementsinthearray?
Whatvalueyouwanttoinsert?
Howmanyelementsarethereinthisarray?
a[0]a[1]a[2]a[3]a[4]
10 20 30
By:Dr. Prakash Singh Tanwar

17. Insertionin an Array
Algorithm:(InsertionofanelementITEMintoKthpositioninaLinear
ArrayAwithNelements)
By:Dr. Prakash Singh Tanwar
Input:
A: Array A ; N: Array A have N elements in it
ITEM :item to insert ;Pos:insert itematpositionPos
Output:
ArrayA with item inserted atposition index ‘Pos’
Algorithm
1. [InitializeCounter.] SetI= N.
2.Repeat Steps3 and4 whileI>=Pos.
3.[MoveIthelement downward] SetA[I+1] =A[I].
4.[Decrease Counter.] SetI=I-1.
[End of Step 2 loop]
5. [Insert element.] SetA[Pos]= ITEM.
6. [Reset N] N = N+1.
7. Exit

18. Insert an element in an
Array
Insert15atposindex=1,Size=3
a[0]a[1]a[2]a[3]a[4]
10 20 30
a[0]a[1]a[2]a[3]a[4]
10 20 30 30
a[0]a[1]a[2]a[3]a[4]
10 20 20 30
a[0]a[1]a[2]a[3]a[4]
10 15 20 30
A[I+1]=A[I]
A[I+1]=A[I]
Algorithm(for index starting from1)
1. [InitializeCounter.] SetI= N.
2.Repeat Steps3 and4 whileI>=Pos.
3.[MoveIthelement downward] SetA[I+1] =A[I].
4.[Decrease Counter.] SetI=I-1.
[End of Step 2 loop]
5. [Insert element.] SetA[Pos]= ITEM.
6. [Reset N] N = N+1.
7. Exit
I
A[Pos]=ITEM
Algorithm (for index starting from 0 andposis also in the
form of index)
1. [InitializeCounter.] SetI=N-1.
2.Repeat Steps3 and4 whileI >=Pos.
3.[MoveIthelement downward] SetA[I+1] =A[I].
4.[Decrease Counter.] SetI=I-1.
[End of Step 2 loop]
5. [Insert element.] SetA[Pos]= ITEM.
6. [Reset N] N = N+1.
7. Exit
By:Dr. Prakash Singh Tanwar

19. Insert an element in an
Array
intinsert(inta[],intn,intkey,intpos)
{
inti;
//shift the elements to right
for(i=n-1;i>=pos; i--)
{
a[i+1]=a[i];
}
//insert the element
a[pos]=key;
//increase the size
n++;
return n;
}
//display array
printf("\n After insertion in array\n");
for(i=0;i<size;i++)
{
printf("%d\t",a[i]);
}
By:Dr. Prakash Singh Tanwar
cout<<"\n After insertion inarray“<<endl;
cout<<a[i]<<“\t”;
intmain(void)
{
intarr[6] = { 10,20,30 };
intn = 3;
intkey=15;
intpos=1;
//insert element key at givenpos
n=insert(arr,n,key,pos);
//display array
display(arr,n);
return 0;
}

20. Linear Search
Writeaprogramtosearchanelementin
anarray?
Whatarethecurrentelementsinthearray?
Whatvalueyouwanttosearch?
By:Dr. Prakash Singh
Tanwar
a[0]a[1]a[2]a[3]a[4]
10 8 30 5 60

21. Linear Search
(un-ordered data)
Input:
Arraya[]withsizen
Keytosearch
Output:
posindexofkeyelementinthearray.Ifnotfoundthenreturn-1
Algo:
Startsearchingtheelementfromtheleftmostpositiontotheendofanarray.
•Ifkeyelementisfoundthereturnthepositionindex
•Otherwiserepeatthestep1fornextposition
Ifitisnotfoundinallpositionindexofarraythen
•returnnotfound
By:Dr. Prakash Singh
Tanwar

22. Linear Search
(un-ordered data)
Searchkey=15
By:Dr. Prakash Singh
Tanwar
a[0]a[1]a[2]a[3]a[4]
10 8 30 5 60
i=0i=0
a[i]==key
Not
matched
i=1i=1
Not
matched
i=2i=2
Not
matched
i=3i=3
Not
matched
i=4i=4
Not
matched
i=5 (out)i=5 (out)
Key=15

23. Linear Search
(un-ordered data)
Searchkey=30
a[0]a[1]a[2]a[3]a[4]
10 8 30 5 60
i=0i=0
a[i]==key
a[i]==30
Not
matched
i=1i=1
Not
matched
i=2i=2
Matched
30 is found atposi=2
Key=30
By:Dr. Prakash Singh Tanwar

24. Linear Search
(un-ordered data)
// linear search for unordered data
intlinearSearch(inta[],intsize,intkey)
{
inti;
//check each element to search the key
for(i=0; i < size ; i++)
{
//if key is found in array
if( a[i] == key )
{
return i; //then return theposi
}
}
//if not found then return-1
return-1;
}
By:Dr. Prakash Singh Tanwar

25. Linear Search
(Sorted Array)
// linear search for ordered data
intlinearSearch(inta[],intsize,intkey)
{
inti;
//check each element to search the key
for(i=0; i<size&&a[i]<=key;i++)
{
//if key is found in array
if( a[i] == key )
{
return i;//then return theposi
}
}
//if not found then return-1
return-1;
}
By:Dr. Prakash Singh Tanwar

26. Linear Search
(Sorted Array)
LinearSearch(sortedarray)
a[0]a[1]a[2]a[3]a[4]
10 20 30 40 50
i=0i=0
a[i]==key
a[i]==30
Not
matched
i=1i=1
Matched
Key=30 key= 30
Key not
matched
30<10
=false
Key not
matched
30<20
=false
10==3020==30
i=2i=2
Key
matched
30==30
Try next
element
Try next
element
30 found at
posi=2
By:Dr. Prakash Singh Tanwar

27. Linear Search
(Sorted Array)
LinearSearch(sortedarray)
a[0]a[1]a[2]a[3]a[4]
10 20 30 40 50
i=0i=0
a[i]==key
a[i]==30
Not
matched
i=1i=1
Matched
Key=30 key= 25
Key not
matched
25<10
=false
Key not
matched
25<20
=false
10==2520==25
i=2i=2
Key not
matched
30==25
Try next
element
Try next
element
25 not found in
sorted array
25<30
=true
Come
out from
loop
Where the control will move
from this break statement?
By:Dr. Prakash Singh Tanwar

28. Q/A
Wherethecontrolwillmovefromthisbreakstatement?
A.Outsideofloop
B.comeoutfromif
C.Comeoutfromelseif
D.movetoincrementsection
By:Dr. Prakash Singh Tanwar

29. Linear Search
(Sorted Array)
// linear search for ordered data
intlinearSearch(inta[],intsize,intkey)
{
inti;
//check each element to search the key
for(i=0; i<size&&a[i]<=key;i++)
{
//if key is found in array
if( a[i] == key )
{
return i;//then return theposi
}
}
//if not found then return-1
return-1;
}
Both program works sameBoth program works same
Opposite
condition
By:Dr. Prakash Singh Tanwar

30. Q/A
Itcansearchsortedandunsortedelementsboth
bestcase:keyisfoundatthefirstelement(index=0):
Ω(1)
worstcase:keyelementisfoundatlastpositionn
(index=n-1):O(n)
By:Dr. Prakash Singh Tanwar

31. Q/A
Whatisthebestcasesearchorderfor
linearsearch?
A.Ω(1)
B.O(n)
C.O(n
2
)
D.Ω(n)
By:Dr. Prakash Singh Tanwar

32. Q/A
Whatisthebestcasesearchorderfor
linearsearch?
A.Ω(1)
B.O(n)
C.O(n
2
)
D.Ω(n)
By:Dr. Prakash Singh Tanwar

33. Q/A
Whatistheworstcasesearchorderfor
linearsearch?
A.Ω(1)
B.O(n)
C.O(n
2
)
D.Ω(n)
By:Dr. Prakash Singh Tanwar

34. Q/A
Whatistheworstcasesearchorderfor
linearsearch?
A.O(1)
B.O(n)
C.O(n
2
)
D.Ω(n)
By:Dr. Prakash Singh Tanwar

35. Q/A
Whichoftheprogramiscorrectforlinearsearchalgorithm?
A B C D
intindex =-1;
inti = 0;
while(size > 0)
{
if(a[i] == key)
{
index = i;
}
if(a[i] > key))
{
index = i;
break;
}
i++;
}
return index;
intindex =-1;
inti = 0;
while(size > 0)
{
if(a[i] == key)
{
index = i;
break;
}
if(a[i] > key))
{
break;
}
i++;
}
return index;
intindex =-1;
inti = 0;
while(size > 0)
{
if(a[i] == key)
{
index=i;
break;
}
if(a[i] > key))
{
index = i;
}
i++;
}
return index;
intindex =-1;
inti = 0;
while(size > 0)
{
if(a[i] == key)
{
break;
}
if(a[i] > key))
{
break;
index = i;
}
i++;
}
return index;
By:Dr. Prakash Singh Tanwar

36. Q/A
Writeaprogramtodeleteanelement
fromanarray?
Whatarethecurrentelementsinthearray?
Whatyouwantstodelete?
Howmanyelementsarethereinthisarray?
a[0]a[1]a[2]a[3]a[4]
10 20 30
By:Dr. Prakash Singh Tanwar

37. Delete Element of an
array
Delete10,Size=3
Search10inthisarrayusingsearchalgo.
a[0]a[1]a[2]a[3]a[4]
10 20 30
a[0]a[1]a[2]a[3]a[4]
20 20 30
a[0]a[1]a[2]a[3]a[4]
20 30 30
a[0]a[1]a[2]a[3]a[4]
20 30
Size--
a[0]=a[1]
a[1]=a[2]
posToDelete=0
By:Dr. Prakash Singh Tanwar

38. Delete Element of an
array
By:Dr. Prakash Singh Tanwar
Input: Pointer to an array a[], size of array, Key to delete
Output: array with deleted item and
size of array
Step1:posToDelete=search the element in the array and get the position
to delete
Step 2: if key not found
display message
Step 3: Otherwise (if key found in array)
replace the elements fromposToDeleteto the size of array
Step 3(a):repeatthe step from last element to theposToDelete
Shift elements to the left hand side a[i]=a[i+1];
Step 3(b):decreasethe size by one
size--;
Step 4 return the size

39. Delete Element of an
array
By:Dr. Prakash Singh Tanwar
cout<<“Element ” <<key<<“ not fount in array”<<endl;
cout<<“Before deletion of an array”<<endl;
cout<<“Which element you want to remove?”<<endl;
cin>> key;
cout<<“After deletion from array”<<endl;

40. Binary Search
a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
10 20 30 40 50 60 70 80 90 100
mid=(9+0)/2=4 Mid=4Mid=4
Key=60
a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
10 20 30 40 50 60 70 80 90 100
Mid=(5+9)/2=7
Mid+1Mid-1Mid-1
Mid=(5+6)/2=5
Left=0Left=0 Right=9Right=9
key not foundkey not found
a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]
10 20 30 40 50 60 70 80 90 100
Mid=7Mid=7 Mid+1Mid+1Mid-1Mid-1
Left
=mid+1
RightRight
key not foundkey not found
Mid=5Mid=5
key found at
pos5
key found at
pos5
Right
=mid-1
By:Dr. Prakash Singh Tanwar

41. Binary Search
Algorithm
Step 1: calculate the mid position
Step 2: If the key to search is found at mid then return themidpos
Step 3: If key <a[mid]value, then it is in left side.
so, recursively find it in left side fromlefttomid-1
Step 4: otherwise , then it is in right side.
so, recursively find it in right side i.e. frommid + 1toright
Step 5: if it is not found in left and right then return-1 (not found)
By:Dr. Prakash Singh Tanwar

42. Binary Search
cout<<“key is not found in array”<<endl;
cout<<“key is found at index ”<<pos<<endl;
By:Dr. Prakash Singh Tanwar

43. Binary Search
cout<<“key is not found in array”<<endl;
cout<<“key is found at index ”<<pos<<endl;
By:Dr. Prakash Singh Tanwar

44. Binary Search-Algo-2
Algorithm
1.BINARY ( DATA, LB, UB, ITEM, LOC )
2.[Initialize Segment Variables]
Set BEG = LB, END = UB and MID = INT ((BEG+END)/2).
3.Repeat Steps 3 and 4 while BEG <= END and DATA [MID] != ITEM.
4. If ITEM < DATA[MID], then:
Set END = MID-1.
Else:
Set BEG = MID + 1.
[End of if Structure.]
5. Set MID = INT ((BEG+END)/2).
[End of Step 2 Loop.]
6.If DATA [MID] = ITEM, then: Set LOC= MID
Else:
Set LOC = NULL.
[End of if structure.]
7.Exit.
By:Dr. Prakash Singh Tanwar

45. Binary Search
Binarysearchorderis
O(logn)
Ifn=1024thenitwilltakemax.
log
2(1024)=log
2(2
10
)=10steps
1024512256128643216
8421
By:Dr. Prakash Singh Tanwar

46. Q/A
Ifthereare1000elementsinanarray.Then
howmanymaximumstepsareneededto
searchanelementinanarrayusingbinary
search?
A.9
B.1000
C.999
D.10
By:Dr. Prakash Singh Tanwar

47. Limitations of
Binary Search
AlthoughthecomplexityofBinarySearchis
O(logn),ithassomelimitations:
Thelistmustbesorted
Onemusthavedirectaccesstothemiddleelementin
anysublist.
By:Dr. Prakash Singh Tanwar