Objectives
DESIGN AND ANALYSIS OFALGORITHMS UNITI INTRODUCTION
Explain what theuseofalgorithm is
Describethe fundamentals of algorithmicproblem solving
Understand how to calculatethe complexityof analgorithm
Describetheuseofan divide and conquermethod
Explain the analysis ofvarious sortingtechniques
1. Algorithm
An algorithm is asequenceofunambiguous instructions forsolvingaproblem, i.e., forobtaining a required output for anylegitimateinput in a finite amount oftime.
2. Fundamentalsofalgorithmic problemsolving
1
2.1.Understanding the Problem:
•Clearlyread theproblem
•Ask anydoubtsyou having
•Analysis what is theinput required
2.2.Decisionmaking on
•Capabilitiesofcomputationaldevices:Thealgorithmshouldadapttoyoursystem.Forexample ifyoursystemexecutes theinstruction in parallelthenyou haveto writeparallel
Algorithm or else if you having RAM machine (The system executes the instruction sequentially)thenyouhavetowriteserialalgorithm.Decideexactorapproximateoutputneed: Writeanalgorithmdependsonoutputneed.Forexampletofindthesquareroottheapproximate output is enough but findingshortest waybetweenthe cities, weneed an exact result.
•DecideDataStructure:Inwhichformatgoingtogivetheinput.Exampledatastructuresare
Stack, Queue,List andetc.
•AlgorithmTechniques:Decidewhichtechniqueusedtowriteanalgorithm.Forexampleyou candividethe big problemintonumberofsmallerunitsandsolveeachunit.Thistechnique calledasDivideandConquer method.Sodependingontheproblemyoucanselectanyone techniques.SometechniquesareDecreesand Conquer,BruteForce,DivideandConquerand etc.
2.3.SpecificationofanAlgorithm:
Thewayforspecifying an algorithm. Therearethreeways to represent analgorithm
•NaturalLanguage: You can represent theinstruction in the form ofsentence.
•PseudoCode:Useidentifier,keywordsandsymbolstorepresenttheinstructions.Forexample c=a+b.
•Flowchart:Theanotherwayforrepresentingtheinstructions.Inthisusediagramsandlinkthe sequenceusinglines. Theseparatediagrams areavailablebased on theinstructions.
2.4.Algorithm Verification:
Toverifythealgorithmapply allthepossibleinputandcheckthealgorithmproducetherequired output ornot..
2.5.Analysis ofAlgorithm:
Computethe efficiencyofthe algorithm.. Theefficiencyiis depend on thefollowingfactors
•Time:Theamountoftimetotakeexecutethealgorithm.Ifthealgorithmtakeless amount oftimeto executethen this one will bethebest one.
2
•Space:Theamountofmemory requiredtostorethealgorithmandthe amountofmemory required to storetheinput forthat algorithm.
•Simplicity:Thealgorithmshouldnothavinganycomplexinstructions.Thattypeof instructions aresimplified to numberofsmallerinstructions.
•Generality: The algorithm should be in general. It should be implemented in any language. Thealgorithm is not fit in to aspecificoutput.
2.6.Implementation:
Aftersatisfyingaboveallfactorscodethealgorithminanyoflanguageyouknownandexecute theprogram.
3. Properties of thealgorithm
)Finiteness: - analgorithm terminates aftera finitenumbers ofsteps.
2)Definiteness: -each step in algorithm is unambiguous. This means that theaction specified by thestep cannot beinterpreted (explain themeaningof)in multiple wayscan beperformed without anyconfusion.
3)Input:- an algorithm accepts zero ormoreinputs
4)Output:-it produces atleast oneoutput.
5)Effectiveness:-it consists ofbasicinstructions that arerealizable. This means that the instructions
6)Non Ambiguity: The algorithm should not havinganyconflict meaning..
7)RangeofInput:Beforedesigna algorithm,, decide what typeofiinputgoingto given,, whatsis the required output..
8)Multiplicity: Youcanwritedifferent algorithms to solvethesame problem..
9)Speed : Applysomeideato speed up theexecution time..
4. Analysis ofalgorithm
4.1.Analysis Framework:
Analysis:Tocomputetheefficiencyofanalgorithm.Whencomputetheefficiencyofan algorithm, considerthefollowingtwo factors.
_SpaceComplexity
_TimeComplexity
3
(i)SpaceComplexity:Theamountofmemoryrequiredtostorethealgorithmandtheamount ofmemoryrequired to storetheinputs forthis algorithm.
S(p)=C+Spwhere,
C– Constant (The amount ofmemoryrequired to storethe algorithm)
Sp – The amount ofmemoryrequired to storetheinputs. Each input stored in oneunit.
Example:Writeanalgorithmtofindthesummationofnnumbersandanalysisthespace complexityforthat algorithm..
AlgorithmSummation(X ,,n)
//// Input : n Numberofelements
//// Output : The result forsummation ofn numbers.. sum =0
forI=1 to n
sum=sum+ X[ii]
return sum
TheSpaceComplexityof above algorithm: S(p)=C+Sp
1..Oneunitforeachelementinthearray..Thearrayhavingnnumberofelementssothearray required in unit..
2..Oneunit forthevariablen,, oneunit forthevariableIand oneunit forthevariablesum..
3..Add the aboveall units and find thespace complexity.. S(p)=C+ (n +1+1 +1)
S(p)=C+ (n +3)
(ii)TimeComplexity
Theamountoftimerequiredtorunthealgorithm..Theexecutiontimedependsonthefollowing factors..
•System load
•Numberofotherprograms running
•Speed ofhardware
Howto measurethe running time?
•Findthebasicoperationofthealgorithm.(Theinnermostlooporoperationiscalledbasic operation)
•Computethetime required to executethebasicoperation.
4
•Computehowmanytimesthebasicoperationisexecuted.TheTimecomplexitycalculatedby the followingformula
T(n)=Cop * C(n)Where,
Cop – Constant (The amount oftime required to executethebasicoperation) C(n)– How manytimes thebasicoperation is executed.
Example:TheTime complexityofthe above algorithm
(Summation ofn Numbers)
1.TheBasicoperation is: addition
2.To computehow manytimes theBasicoperation is executed: n
3.So, T(n)Cop * n
4.Removethe constant or assumeCop =1
5.TheTimeComplexityis T(n)=n.
4.2OrderofGrowth
ThePerformanceofanalgorithmrelationwiththeinputsizenofthatalgorithm.Thisiscalled Orderof Growth.For exampletheFunction is 2n In that,, iftheinput n =1then theoutput is 2. Best case, Worst caseandAverage case
In somealgorithm thetime complexitycomes underin threecategories..
•Best case
•Worst case
•Average case
_IntheBestcasethealgorithm(Basicoperation)executeonlylessnumberoftimescompareto other cases..
_IntheWorstcasethealgorithm(Basicoperation)executehighnumberoftimescompareto other cases..
_IntheAveragecasethealgorithm(Basicoperation)executeinbetweenBestcaseandWorst case..
Example:Write analgorithm to search akeyin thegiven set of elements..
AlgorithmSeq_Search( X,, key,, n)
////Input : The arrayofelements and aSearch key..
//// Output : Thesearch keyis present in thelist ornot.. fori =1 to n
if( X[i]==key)
5
return true return false
In theabovealgorithm thebest caseis One. T(n)=1
In theabovealgorithm the worst case comeunderin two situations,,
•Ifthesearch keyis located at the end ofthelist.
•Ifthesearch keyis not present in thelist.
HerethebasicoperationexecutesnNumberoftimes.SotheTimeComplexity ofthisalgorithm is n. i.eT(n)=n
Letassume,
P– Theprobabilityofsuccessful search.
1-P-Theprobabilityofunsuccessful search.
P/n – Theprobabilityofoccurringfirst match fortheIthe element. Cavg(n)=[1 P/n +2P/n +…..nP/n]+n(1-P)
=P/n[1+2+…..+n]+n(1-P)
=P/n(n(n+1)/2)+n(1-P)
=P(n+1)/2 +n(1-P) In theabove,,
ApplyP=0 ifthereis nosuch akeyin thelist
Cavg(n)=0(n+1)//2 +n(1-0)
=n
ApplyP=1 ifthekeyis present in thelist
Cavg(n)=1(n+1)//2 +n(1-1)
=(n+1)//2..
4.3Asymptotic Notations
(i)Big–O
(ii)Big–Omega
(iii) Big–Theta
(i)Big–O (or)O() Notation
Afunctiont(n)issaidtobeinO(g(n)),denotet(n)€O(g(n)),ift(n)isboundedabovebysome constantmultipleofg(n)foralllargen,i.e.,ifthereexistssomepositiveconstantcandsome nonnegativeintegern0such that
t(n)≤ c.g(n)for all n ≥ n0.
6
(ii)Big–Omega (or)Ω() Notation
Afunctiont(n)issaidtobeinΩ(g(n)),denotet(n)€Ω(g(n)),ift(n)isboundedbelowby some constantmultipleofg(n)foralllargen,i.e.,ifthereexistssomepositiveconstantcandsome nonnegativeintegern0 such that
t(n)≥ c.g(n)for all n ≥ n0.
(iii)Big–Theta (or)θ()Notation
A functiont(n)issaidtobeinO(g(n)),denotet(n)€O(g(n)),ift(n)isboundedbothaboveand belowbysomeconstantmultipleofg(n)foralllargen,i.e.,if thereexists somepositiveconstant c1 and c2and somenonnegativeintegern0 such that
C2.g(n)≤ t(n)≥ c1.g(n)for all n ≥ n0.
7
Examples
Herearea few examples that show how thedefinitions should be applied.
Summary
•An algorithm is asequenceofunambiguous instructions forsolvingaproblem, i.e., for obtainingarequired output for anylegitimateinput in a finite amount oftime.
8
•Therearetwokindsofefficiency:timeefficiencyandspaceefficiency.Timeefficiency indicateshow fastthealgorithmruns;spaceefficiencydealswiththeextraspaceit requires.Theefficiencyisdependingonthefactorssuchastime,space,simplicityand generality.
•Analgorithm’stimeefficiencyisprincipallymeasuredasafunctionofitsinputsizeby countingthe numberoftimeitsbasicoperationisexecuted.Abasicoperationisthe operation that contributesmost toward runningtime.
•Natural Language, Pseudo Code and Flowchart are the three ways to represent an algorithm
•TheSpaceComplexityof an algorithm is calculated usingtheformulaS(p)=C+Sp
•TheTimeComplexityofan algorithm is calculated usingthe formulaT(n)=Cop * C(n)
•Big–O, Big–Omega and Big–Theta notations are used to indicate and compare the asymptoticorders ofgrowth of functions expressingalgorithm efficiencies
KeyTermsAlgorithm / OrderofGrowth / time efficiency
Space efficiency
Average case / Best case
Big–O / Worst case
Big–Omega
Big–Theta
KeyTermQuiz
1.A sequenceofunambiguous instructions forsolvingaproblem is called ------
2.------efficiencyindicates how fast the algorithm runs.
3.------efficiencydeals with the extraspaceit requires.
4.Afunctiont(n)issaidtobeing(n),ift(n)isboundedaboveby someconstantmultipleofg(n) foralllargen,i.e.,ifthereexistssomepositiveconstantcandsomenonnegativeintegern0is called ------notation.
5.Afunctiont(n)issaidtobeing(n),ift(n)isboundedbelowbysomeconstantmultipleofg(n)
foralllargen,i.e.,ifthereexistssomepositiveconstantcandsomenonnegativeintegern0is called ------notation.
9
6.Afunctiont(n)issaidtobeing(n),ift(n)isboundedbothaboveandbelowbysomeconstant multipleofg(n)foralllargen,i.e.,ifthereexistssomepositiveconstantc1andc2andsome nonnegativeintegern0 iscalled ------notation.
Multiple Choice Questions
1.Defineanalgorithm?
(a)Algorithm is aprogramminglanguagethat canbeused to writeaprogram
(b)Consists ofsequenceofinstructions that can be executed in anyorder
(c)Sequenceofambiguous instructions that has to be executed onebyone. (d)asequenceofunambiguous instructions forsolvingaproblem
2.Whatis a pseudo code?
(a)Both 2 and 3.
(b)It is amixtureofanatural languageand programminglanguage-like constructs. (c)Is defined as theprocedural language without programming constructs
(d)Is defined as theprogram that can be executed in themachine.
3.Define the efficiencyofalgorithms?
(a)Thealgorithm should occupymorememoryspace with lesser runningtime
(b)Efficiencyis definedas the algorithm should occupyless memoryspaceand should run fast (c)Efficiencycanbe saidasthealgorithmoccupieslessermemoryspaceandmorerunning time
(d)all the above
4.Whatare the three cases ofefficiencies?
(a)Best Case(b)Worst Case(c)AverageCase(d)All the above
5.Whichofthefollowing parameteris usedto measure theefficiencies ofanalgorithm?
(a)Algorithm's output
(b)Theyaremeasuredasthe function of algorithms input size
(c)It is measured based on theprogramminglanguageit is implemented
(d)Noneofthe above
6.Timeefficiency is measured by
(a)Numberoftimes theprocedures executed in thealgorithm
(b)Countingthenumberoftimes the functions executed
(c)Countingthenumberoftimes the algorithm's basicoperation is executed
(d)Countingthenumberoftimes forasingleloopexecution.
10
8.Space efficiency is calculated by
(a)Countingthenumberof extramemoryunits consumed bythealgorithm (b)Countingthenumberofmemoryunits consumed bythe algorithm (c)Both 1 and 2 are correct
(d)Noneofthe above
9.Defineworst case efficiency?
(a)Veryshort timeofinput sizen
(b)Themedium time consumption fortheinput sizen
(c)Thesmallest possibletime forinput n
(d)Thelongest possibletimeit takes to run forthesizeofn inputs
10.Whatis thebest case efficiency?
(a)Fastest runningtimeforaparticularinput amongall theinputs forthe algorithm
(b)Slowest runningtimeforaparticularinput amongall theinputs
(c)Veryslowertime amongall theinputs
(d)All the above
ReviewQuestions
Two mark Questions
1.Define algorithm
2.DefineBig-Oh notation.
3.Mention anyfour classes of algorithm efficiency.
4.Defineorderofan algorithm.
5.How willyou theinput sizeof an algorithm?
6.Comparetheorderofgrowth n! and 2n.
7.What is an algorithm design technique?
8.How is an efficiencyof an algorithm defined?
Big Questions
1.Definetheasymptoticnotationsusedforbestcaseaveragecaseandworstcaseanalysisof algorithms.
2.Explain various criteria for analyzinganalgorithm.
3.Discuss brieflythesequenceofsteps fordesigningandanalyzinganalgorithm.
11
5. Divideand Conquer
Thedivide-and-conquerstrategysolves aproblem by:
1.Breakingit into sub problems that arethemselves smallerinstances ofthesametypeof problem
2.Recursivelysolvingthesesub problems
3.Appropriatelycombiningtheiranswers
6.BinarySearch
Generally,tofindavalueinunsortedarray,weshouldlookthroughelementsofanarrayoneby one,untilsearchedvalueisfound.Incaseofsearchedvalueisabsentfromarray,wegothrough allelements.Inaverage, complexityofsuchanalgorithmisproportionaltothelengthofthe array.
Algorithm
Algorithm is quitesimple.Itcan bedone either recursivelyoriteratively:
1. get themiddleelement;
2. ifthemiddle element equals to thesearched value,the algorithm stops;
3. otherwise, two cases arepossible:
oSearchedvalueisless,thanthemiddleelement.Inthiscase,gotothestep1for thepart ofthearray, beforemiddle element.
oSearchedvalueisgreater,thanthemiddleelement.Inthiscase,gotothestep1 forthepart ofthe array,aftermiddle element.
Nowweshoulddefine,wheniterationsshouldstop.Firstcaseiswhensearchedelementis found. Second one is when subarrayhas no elements. In this case, wecan conclude, that searched valuedoesn't present in the array.
Examples
Example1. Find 6 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
Step 1 (middle element is 19 >6):-1 5 6 18 19 25 46 78 102 114
Step 2 (middle element is 5 <6):-1 5 6 18 19 25 46 78 102 114
12
Step 3 (middle element is 6 ==6):-1 5 6 18 19 25 46 78 102 114
Example2. Find 103 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
Step 1 (middle element is 19 <103): -1 5 6 18 19 25 46 78 102 114
Step 2 (middle element is 78 <103): -1 5 6 18 19 25 46 78 102 114
Step 3 (middle element is 102 <103): -1 5 6 18 19 25 46 78 102 114
Step 4 (middle element is 114 >103): -1 5 6 18 19 25 46 78 102 114
Step 5 (searched valueisabsent):-1 5 6 18 19 25 46 78 102 114 procedure: int binarySearch(int arr[], int value, int left, int right)
while (left = right)do
int middle= (left + right)/ 2;
if (arr[middle]==value)
return middle;
elseif (arr[middle]value)
right =middle-1;
else
left =middle+1;
return -1;
Analysis:
Therecurrencerelation forbinarysearch
C(n)=C(n/2)+1forn1,C(1)=1
Substituten=2k then weget, C(2k)=k+1=log2n+1
C(n)=log2n+1=log2n(n+1) Ifn=2i then
C(n)=log2n+1=log2n2i+1=log22+log2i+1
=1+log2i+1=log2i+2
7. FindingMaximumand Minimumelement
Anaturalapproachistotryadivideandconqueralgorithm.Splitthelistintotwosublistsof equalsize.(Assumethattheinitiallistsizeisapoweroftwo.)Findthemaximaandminimaof thesublists.Twomorecomparisonsthensufficetofindthemaximumandminimumofthelist.
Thesteps are,
13
Dividingthegiven arrayinto two equal halves
Repeat step1 until the arraycontains asingle element
Combiningthetwo arrays and select theminimum and maximum element
Repeat stpe3 until the final solution is found
proceduremaxmin(A[1...n]ofnumbers) - (min,max)
begin
if (n ==1)
return (A[1], A[1])
elseif (n ==2) if( A[1] A[2]) return (A[1], A[2]) else
return (A[2], A[1])
else
(max_left, min_left)=maxmin(A[1...(n/2)]) (max_right, min_right)= maxmin(A[(n/2 +1)...n]) if (max_left <max_right)
max=max_right else
max=max_left
if (min_left <min_right)
max=min_left else
min =min_right return (min, max)
end
14
Hence,ifT(n)isthenumberofcomparisons,thenT(n)=2T(n/2)+2.(The2T(n/2)termcomes fromconquering thetwoproblemsintowhichwedividetheoriginal;the2termcomesfrom combiningthesesolutions.)Also,clearly T(2)=1.ByinductionwefindT(n)=(3n/2)−2,forna powerof2.
8. Analysis of Mergesort
Themergesort algorithm is based on the classical divide-and-conquerparadigm.
DIVIDE: Partitionthen-elementsequencetobesortedintotwosubsequencesofn/2elements each.
CONQUER: Sortthetwosubsequencesrecursivelyusingthemergesort. COMBINE: Mergethetwosortedsortedsubsequencesofsizen/2eachtoproducethesorted sequence consisting of n elements. Notethatrecursion"bottomsout"whenthesequencetobesortedisofunitlength.Sinceevery sequenceoflength1isinsortedorder,nofurtherrecursivecallisnecessary.Thekeyoperation ofthemergesortalgorithmisthemergingofthetwosortedsequencesinthe"combinestep".To
15
performthemerging,weuseanauxilliaryprocedureMerge(A,p,q,r),whereAisanarrayandp,q andrareindices numberingelementsofthearraysuchthatdureassumesthatthesubarrays A[p..q]andA[q+1...r]areinsortedorder.Itmergesthemtoformasinglesortedsubarraythat replaces thecurrent subarrayA[p..r]. Thus finally,weobtain thesortedarrayA[1..n], which is the
solution.
16
Algorithm
voidmergeSort(intnumbers[], inttemp[],intarray_size)
{
m_sort(numbers, temp, 0, array_size-1);
}
voidm_sort(intnumbers[],inttemp[], intleft, intright)
{
intmid;
if(right >left)
{
mid = (right+left)/ 2; m_sort(numbers, temp, left, mid); m_sort(numbers, temp, mid+1, right); merge(numbers, temp,left, mid+1, right);
}
}
voidmerge(intnumbers[], inttemp[],intleft, intmid, intright)
{
inti, left_end, num_elements, tmp_pos;
Designand analysisof algorithms- P.VasanthaKumari17
left_end =mid -1;
tmp_pos =left;
num_elements = right -left +1;
while((left =left_end)(mid = right))
{
if(numbers[left]=numbers[mid])
{
temp[tmp_pos]=numbers[left];
tmp_pos =tmp_pos+1;
left =left +1;
}
else
{
temp[tmp_pos]=numbers[mid];
tmp_pos =tmp_pos+1;
mid =mid +1;
}
}
while(left =left_end)
{
temp[tmp_pos]=numbers[left];
left =left +1;
tmp_pos =tmp_pos +1;
}
while(mid = right)
{
temp[tmp_pos]=numbers[mid];
mid =mid +1;
tmp_pos =tmp_pos +1;
}
for(i=0; i =num_elements; i++)
{
numbers[right]=temp[right];
right =right -1;
}
}
Analysis
Mergesortgoes thru thesamesteps -independentofthedata. Best-case=Worst-case=Average-case.
T(n)= runningtimeon alist on n elements.
T(1)=1
18
T(n)=2 times runningtimeon alist ofn/2 elements +linearmerge
T(n)=2T(n/2)+n Brute forcemethod: T(n)=2T(n/2)+n=2[2T(n/4)+n/2]+n=4T(n/4)+2n T(n)=4[2T(n/8)+n/4]+2n=8T(n/8)+3n
T(n)=2**kT(n/2**k)+k*n
and therearek=logn equations to get to T(1): T(n)=nT(1)+nlogn =nlogn +n
9. Analysis ofQuicksort
Thedivide-and-conquerstrategyis used in quicksort. Below therecursion step is described:
1. Chooseapivotvalue.Wetakethevalueofthemiddleelementaspivotvalue,butitcan be anyvalue,which is in rangeofsorted values, even ifit doesn't present in the array.
2. Partition.Rearrangeelementsinsuchaway,thatallelementswhicharelesserthanthe pivotgototheleftpartofthearray andallelementsgreaterthanthepivot,gototheright partofthearray.Valuesequaltothepivotcanstayinanypartofthearray.Notice,that arraymaybedivided innon-equal parts.
3. Sortboth parts. Applyquicksort algorithm recursivelyto theleftand theright parts.
Partitionalgorithmindetail
Therearetwoindicesiandjandattheverybeginningofthepartitionalgorithmipointstothe firstelementinthearrayandjpointstothelastone.Thenalgorithmmovesiforward,untilan elementwithvaluegreaterorequaltothepivotisfound.Indexjismovedbackward,untilan elementwithvaluelesserorequaltothepivotisfound.Ifi≤jthenthey areswappedandisteps tothenextposition(i+1),jstepstothepreviousone(j-1).Algorithmstops,whenibecomes
greaterthan j.
19
Afterpartition,allvaluesbeforei-thelementarelessorequalthanthepivotandallvaluesafter
j-thelement aregreateror equal to thepivot.
Example. Sort {1, 12, 5,26, 7, 14, 3, 7, 2} usingquicksort.
Algorithm
int partition(int arr[], intleft, int right)
{
int i =left, j= right;
int tmp;
int pivot = arr[(left +right)/ 2];
while (i =j)
{
while (arr[i]pivot)
i++;
while (arr[j]pivot)
j--;
if (i =j)
{
swap(arr[i],arr[j];
i++;
j--;
}
}
return i;
}
void quickSort(int arr[], int left, int right)
{
int i =left, j= right;
int tmp;
int pivot = arr[(left +right)/ 2];
while (i =j)
{
while (arr[i]pivot)
i++;
while (arr[j]pivot)
j--;
if (i =j)
{
tmp = arr[i]; arr[i]= arr[j]; arr[j]=tmp; i++;
j--;
}
}
if (left <j)
20
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
Analysis ofQuickSort
Therecurrencerelation forthebest caseperformanceis: Cbest(n)=2 Cbest(n/2)+n,forn1, Cbest(1)=0
Toderivetherecurrencerelation,
21
Substituten=2k, then weget
Cbest(2k)=2 Cbest(2k-1)+2k
=2[2 Cbest(2k-2)+2k-1]+2k
=22 Cbest(2k-2)+2k +2k
=22 [2 Cbest(2k-3)+2k-2]+2k +2k
=23 Cbest(2k-3)+3. 2k
.
.
.
Fori terms,
Cbest(2k)=2i Cbest(2k-i)+i. 2k Replacei=k thenweget, Cbest (2k)=k. 2k
Substituten=2k,
Cbest(n)=O(nlogn)
Therecurrencerelation forthe worst caseperformanceis: Cworst(n)=(n+1)+n+…+3=(n+1)(n+2)/2-3 € O(n2)
Therecurrencerelation forthe averagecaseperformanceis: Cavg(n)=2nlogn
10. Analysis of Selection sort
SelectionsortisoneoftheO(n2)sortingalgorithms,whichmakesitquiteinefficientforsorting largedata volumes.Selectionsortisnotableforitsprogrammingsimplicityanditcanover perform othersorts in certain situations (see complexityanalysis formoredetails).
Theideaofalgorithmisquitesimple.Arrayisimaginarydividedintotwoparts-sortedoneand unsortedone.Atthebeginning,sortedpartisempty,whileunsortedonecontainswholearray. Ateverystep,algorithmfindsminimalelementintheunsortedpartandaddsittotheendofthe sorted one. When unsorted part becomesempty, algorithm stops.
Whenalgorithmsortsanarray,itswapsfirstelementofunsortedpartwithminimalelementand thenitisincludedtothesortedpart.Thisimplementationofselectionsortinnotstable.Incase
22
oflinkedlistissorted,and,insteadofswaps,minimalelementislinkedtotheunsortedpart, selection sort is stable.
Example. Sort {5, 1, 12, -5, 16, 2, 12, 14} usingselection sort.
procedureSELECTION_SORT(A)
fori ← 1 to n-1 do min j ← i;
min x← A[i]
forj ← i +1 to n do
If A[j]minxthen min j ← j
min x← A[j]
23
A[min j]← A [i] A[i]←min x
Analysis
Selectionsortstops,whenunsortedpartbecomesempty.Asweknow,oneverystepnumberof unsortedelements decreasedbyone.Therefore,selectionsortmakesnsteps(nisnumberof elementsinarray)ofouterloop,beforestop.Everystepofouterlooprequiresfindingminimum inunsortedpart.Summingup,n+(n-1)+(n - 2)+...+1,resultsinO(n2)numberof comparisons.Numberofswapsmayvaryfromzero(incaseofsortedarray)ton-1(incase arraywassortedinreversedorder),whichresultsinO(n)numberofswaps.Overallalgorithm complexityisO(n2).Fact,thatselectionsortrequiresn-1numberofswapsatmost,makesit veryefficientinsituations,whenwriteoperationissignificantlymoreexpensive,thanread operation.
11. Analysis of Heapsort
Theheapdatastructureisanarrayobjectwhichcanbeeasilyvisualizedasacompletebinary tree.Thereisaonetoonecorrespondencebetweenelementsofthearrayandnodesofthetree. Thetreeiscompletelyfilledonalllevelsexceptpossibly thelowest,whichisfilledfromtheleft uptoapoint.Allnodesofheapalsosatisfy therelationthatthekeyvalueateachnodeisatleast as large as the value at its children. StepI:Theuserinputsthesizeoftheheap(withinaspecifiedlimit).Theprogramgeneratesa corresponding binary tree with nodes having randomly generated key Values. StepII:BuildHeapOperation:Letnbethenumberofnodesinthetreeandibethekeyofa tree.Forthis,theprogramusesoperationHeapify.whenHeapifyiscalledboththeleftandright subtreeoftheiareHeaps.The functionofHeapifyistoletisettledowntoaposition(by swappingitselfwiththelargerofitschildren,whenevertheheappropertyisnotsatisfied)tillthe heap property is satisfied in the tree which was rooted at (i).This operation calls StepIII:Removemaximumelement:Theprogramremovesthelargestelementoftheheap(the root) by swapping it with the last element. StepIV:TheprogramexecutesHeapify(newroot)sothattheresultingtreesatisfiestheheap property.
StepV: Goto stepIIItill heap is empty
24
proceduredownheap (v)
Input:semi-heap with root v
Output:heap (byrearrangingthevertexlabels)
Method:whilev does not havetheheap propertydo
choosedirect descendantw with maximumlabel a(w)
exchange a(v) and a(w)
set v :=w
Proceduredownheap can beused to build aheapfrom an arbitrarilylabelled tree.Byproceeding bottom-up, downheap is called forall subtrees rooted at innervertices. Sinceleavesare already heaps theymaybeomitted.
procedurebuildheap
Input:almost completebinarytreeT ofdepth d(T)with vertexlabellinga
Output:heap (byrearrangingthevertexlabels)
Method:fori :=d(T)– 1 downto 0 do
for all innervertices v ofdepth d(v)=i do
downheap (v)
Acall ofbuildheap is the first step ofprocedureheapsort, which can nowbe written down as follows:
procedureheapsort
Input:almost completebinarytree with root rand vertexlabellinga
Output:vertexlabels in descendingorder
Method:buildheap
whileris not aleafdo
outputa(r)
chooseleafb ofmaximum depth writelabel a(b)to r
deleteleafb downheap (r) output a(r)
Analysis
Analmostcompletebinarytreewithnverticeshasadepthofatmostlog(n).Therefore,procedure downheap requires at most log(n) steps. Procedure buildheap calls downheap for each vertex, thereforeitrequiresatmostn·log(n)steps.Heapsortcallsbuildheaponce;thenitcallsdownheapfor each vertex, togetherit requires at most 2·n·log(n)steps.
25
thetimecomplexityofheapsortisT(n)O(n·log(n)).Thealgorithmisoptimal,sincethelower
boundofthesortingproblem is attained.
Analysis
Analmostcompletebinarytreewithnverticeshasadepthofatmostlog(n).Therefore,procedure downheap requires at most log(n) steps. Procedure buildheap calls downheap for each vertex, thereforeitrequiresatmostn·log(n)steps.Heapsortcallsbuildheaponce;thenitcallsdownheapfor
each vertex, togetherit requires at most 2·n·log(n)steps.
26
Thus,thetimecomplexityofheapsortisT(n)O(n·log(n)).Thealgorithmisoptimal,sincethe lowerbound ofthesortingproblem is attained.
Summary
Divide and Conquer is a general algorithm design technique that solves a problem instance by dividing it into several smaller instances of equal size, solving them recursively,and thencombiningtheirsolutions to get asolution to theoriginal instanceof theproblem.
Time efficiencyofdivideand conquersatisfies theequation T(n)=aT(n/b)+f(n).
Mergesortisadivideandconqueralgorithm.Itworksbydividinganinputarrayinto twohalves,sortingthemrecursivelyandthenmergingthetwosortedhalvestogetthe original arraysorted.
Quicksortisadivideandconqueralgorithmthatworksby partitioningitsinputelements accordingto theirvaluesrelativeto somepreselected element.
Binarysearch is a O(logn) algorithm forsearching in sorted arrays.
Key Termsbinarysearch
divide andconquer
Key TermQuiz / quick sort
heap sort / mergesort
selection sort
1.------isageneralalgorithmdesigntechniquethatsolvesaprobleminstanceby dividingit into several smallerinstances of equal size, solvingthem recursively, and then combiningtheirsolutions to get asolution to theoriginal instanceoftheproblem.
2.------algorithm works bydividing an input arrayinto two halves, sorting them recursivelyand then mergingthetwo sorted halves to get theoriginalarraysorted.
3.------isadivideandconqueralgorithmthatworksbypartitioningitsinputelements accordingto theirvaluesrelativeto somepreselected element.
4.The runningtimeofbinarysearch is ------
27
5.Thetreeiscompletelyfilledonalllevelsexceptpossiblythelowest,whichisfilledfromtheleft to the right is called------
Multiple Choice Questions
1.Thealgorithmworksbydividinganinputarrayintotwohalves,sortingthemrecursively andthenmerging thetwo sorted halves to gettheoriginal array sorted.
a)heap sortb)quick sortc)mergesortd)selection sort
2.------is a divideand conqueralgorithmthatworks by partitioning its input elements according to theirvalues relative to somepreselectedelement.
a)heap sortb)quick sortc)mergesortd)selection sort
3.Theselectionofpivotelementis used in------
a)heap sortb)quick sortc)mergesortd)selection sort
4.Whichoneofthefollowingis nota divideandconquer?
a)heap sortb)quick sortc)mergesortd)selection sort
5.The running timeofbinary search is
a) O(logn)b) O(n)c) O(nlogn)d)O(n/2)
6.The time complexityofheapsortis
a) O(logn)b) O(n)c) O(nlogn)d)O(n/2)
7.The running timeofquicksortis
a) O(logn)b) O(n)c) O(nlogn)d)O(n/2)
8.The time complexityofselectionsortis
a) O(logn)b) O(n)c) O(nlogn)d)O(n2)
ReviewQuestions
Two mark Questions
1. What is the averagecasecomplexityoflinearsearch algorithm
2. Writetheprocedure forselection sort.
28
3. Find thenumberofcomparisons madebythesequential search in the worstand best case.
4. Statethetime complexityofmergesortalgorithm.
5. Statethetime complexityofquick sort algorithm.
6. Statethetime complexityofselection sort algorithm.
7. Statethetime complexityofheap sortalgorithm.
8. List out anytwo drawbacks ofbinarysearchalgorithm.
9. What aretheobjectives ofsorting algorithm?
BigQuestions
1.Writeanalgorithmforfindingmaximumelementofanarray,performbest,worstandaverage case complexitywith appropriateordernotations.
2.Explain in detail quick sortingmethod. Providea complete analysis ofquick sort.
3.Explainindetailmergesort.Illustratethealgorithmwithanumericexample.Providecomplete analysis ofthesame.
4.Writeanalgorithmforperformingbinarysearchforanyelementinanarray.Andfindingthe complexityofbinarysearch.
5.Defineheap.Explainthepropertiesofheap.Withasimpleexampleexplaintheconceptofheap algorithm.
6.Writeanalgorithmtosortnnumbersusingselectionsort.Tracethealgorithmforthenumbers
11,21,56,43,87,67,54,2,99
7.Sort the followingset ofelements usingquick sort 11,21,56,43,87,67,54,2,99,5,78,94
Lesson Labs
1.Comparequick sort, mergesort, heap sortand selection sort
2.Comparelinearsearch and binarysearch.
3.WriteanalgorithmforFibonacciseriesusingdivideandconquer.Findingthecomplexityofthe same.
------END OF FIRSTUNIT------
29