UNIT-

I
I
ntroducti
onAl
gori
thm Speci
ficat
ion,Perf
ormanceanal
ysis,Per
formanceMeasurement.Arr
ays:
Arrays,
Dynami
cal
lyAll
ocatedAr r
ays.Str
uctur
esandUnions.Sort
ing:Mot
ivat
ion,
Quicksort
,how
fastcanwesor
t,Mergesort,
Heapsor t

Whati
sdat
ast
ruct
ure?

Adatastruct
urei
sadat aorgani
zati
on,managementandstoragefor
matt hatenabl
e
ef
fi
cientaccessandmodi f
icat
ion.adatastr
uctur
eisacol
lect
ionofdatavalues,t
herelat
ionshi
ps
amongt hem,andthefuncti
onsoroperati
onsthatcanbeappl
iedtothedata.

Int
roduct i
on
Dat aStruct
urecanbedef inedast hegroupofdat aelementswhichpr ovi
desanef f
ici
entway
ofstoringandor ganizi
ngdataint hecomput ersothatitcanbeusedef fici
entl
y.Someexampl esof
DataSt ructur
esarear r
ays,Li
nkedLi st,St
ack,Queue,etc.DataStruct
uresarewi del
yusedinalmost
everyaspectofComput erSci
encei .e.operat
ingSystem, Compil
erDesign,Arti
fi
ciali
ntel
l
igence,
Graphicsandmanymor e.
Dat aStruct
uresarethemai npar tofmanycomput ersci
encealgorit
hmsast heyenablethe
programmer stohandlethedatainanef f
ici
entway.Itplaysavit
al r
oleinenhancingthe
performanceofsof twareorapr ogram ast hemainfunct i
onofthesoftwareistostoreandretri
eve
theuser '
sdat aasfastaspossible

BasicTerminol
ogy
Datastr
uctur
esarethebui
ldi
ngbl
ocksofanyprogram orthesof
tware.Choosi
ngthe
appropri
atedatastr
uct
ureforaprogr
am i
sthemostdiff
icul
ttaskforaprogrammer.Fol
l
owing
ter
mi nol
ogyisusedasfarasdatastr
uct
uresar
econcerned

Dat
a:Datacanbedefi
nedasanelement
aryval
ueort
hecol
l
ecti
onofvalue.
Forexampl
e,st
udent
'snameandit
sidaret
hedat
aaboutthest
udent.

Gr
oupI
tems:Datait
emswhichhavesubordi
nat
edat ai
temsar
ecall
edGroupi
tem.
Forexample,
nameofastudentcanhavefi
rstnameandthel
astname.

Recor
d:Recordcanbedefi
nedasthecoll
ect
ionofvari
ousdatai
tems.
Forexample,i
fwetal
kaboutt
hestudentent
it
y,theni
tsname,addr
ess,
cour
seandmar
ks
canbegroupedtoget
hert
oformtherecordf
orthestudent
.

Fil
e:AFileisacol
l
ecti
onofv ari
ousr
ecordsofonetypeofenti
ty,
Forexampl
e,i
fthereare60employeesi
ntheclass,
thentherewi
ll
be20r
ecor
dsi
nthe
rel
atedfil
ewhereeachrecor
dcontai
nsthedataabouteachempl oy
ee.

Att
ri
but
eandEntit
y:Anent
it
yrepr
esentst
hecl
assofcert
ainobject
s.i
tcont
ainsv
ari
ousat
tr
ibut
es.
Eachat
tri
but
erepr
esent
sthepart
icul
arpr
oper
tyoft
hatenti
ty.

Fi
eld:
Fiel
disasi
ngl
eel
ement
aryuni
tofi
nfor
mat
ionr
epr
esent
ingt
heat
tr
ibut
eofanent
it
y.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717931
NeedofDataStructures
Asappl
icationsar eget
ti
ngcompl
exandamountofdat
aisi
ncr
easi
ngdaybyday
,ther
emay
ar
iset
hefol
lowingpr oblems:

Processorspeed:Tohandl
ever
ylar
geamountofdat
a,highspeedprocessi
ngi
srequi
red,
butas
thedataisgrowingdaybydayt
othebi
ll
i
onsoffi
lesperenti
ty,
processormayf
ail
todealwit
hthat
muchamountofdat a.

DataSearch:Consi
deraninvent
orysi
zeof106it
emsi
nastor
e,Ifourappl
i
cat
ionneedstosear
ch
foraparti
cul
arit
em, i
tneedstotr
aver
se106it
emsever
yti
me,resul
tsinsl
owi
ngdownt hesear
ch
process.

Multiplerequests:
Ifthousandsofuser saresearchi
ngthedatasimultaneouslyonawebser v
er,
thent herearethechancesthatav erylargeser
vercanbefail
eddur i
ngt hatprocess.I
nor derto
solvet heaboveproblems,datastructuresareused.Dat
aisorganizedtof or
m adat astructurei
n
suchawayt hatalli
temsar enotrequiredtobesearchedandrequireddat acanbesear ched
i
nstant ly
.

Adv
ant
agesofDat
aSt
ruct
ures

Eff
iciency:Eff
iciencyofapr ogram dependsupont hechoi
ceofdatastructures.
Forexampl e:suppose,wehav esomedat aandweneedt operformt hesearchf ora
part
icularrecord.Inthatcase,ifweor ganizeourdatainanarr
ay,wewi l
lhav etosearch
sequential
lyelementbyel ement.Hence, usi
ngarraymaynotbev eryeffi
cienthere.Thereare
bett
erdat astructureswhi chcanmaket hesearchprocessef
fi
cientli
keorder edarray
,binar
y
searchtreeorhasht ables.

Reusabi
li
ty:
Datastructuresarereusabl
e,i
.e.oncewehavei
mplementedapar
ti
culardat
astructur
e,
wecanusei tatanyotherplace.Implementat
ionofdat
astr
uct
urescanbecompil
edintol
ibr
aries
whichcanbeusedbydi f
ferentcl
ient
s.

Abstr
act
ion:Datast
ructur
eisspeci
fi
edbytheADTwhichprovi
desalev
elofabst
racti
on.Thecl
ient
progr
am usesthedatastr
uctur
ethr
oughint
erf
aceonl
y,wi
thoutget
ti
ngint
otheimplementat
ion
detai
l
s.

Dat
aSt
ruct
ureCl
assi
fi
cat
ion

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717932
LinearDataStructur
es:Adat
astr
uctureiscal
ledl
ineari
fal
lofitsel
ementsarearrangedi
nthe
l
inearorder.I
nlineardat
astr
uct
ures,t
heelementsarestor
edinnon-hi
erarchi
cal
waywher eeach
elementhasthesuccessorsandpredecessor
sexceptthefi
rstandl
astelement.

Ty
pesofLi
nearDat
aSt
ruct
ures:

Arr
ays:Anarr
ayi
sacoll
ect
ionofsi
mil
artypeofdat
aitemsandeachdat
aitem i
scal
ledan
el
ementofthear
ray
.Thedatat
ypeoftheelementmaybeanyval
iddat
atypeli
kechar,
int
,fl
oator
doubl
e.

Theelementsofar
rayshar
ethesamevari
abl
enamebuteachonecarr
iesadif
fer
enti
ndex
numberknownassubscri
pt.Thearr
aycanbeonedi
mensi
onal
,twodi
mensionalor
mult
idi
mensional
.

Thei
ndi
vi
dual
element
soft
hear
rayagear
e:

age[
0],
age[
1],
age[
2],
age[
3],
.
..
..
..
..age[
98]
,age[
99]
.

LinkedList:Linkedli
stisali
neardatastr
uctur
ewhichisusedtomai
ntai
nal i
stinthememor y
.It
canbeseenast hecoll
ect
ionofnodesstoredatnon-
cont
iguousmemorylocat
ions.Eachnodeof
thelistcontai
nsapoi nt
ertoit
sadjacentnode.

St
ack:Stackisalinearl
istinwhichinser
ti
onanddel eti
onsareall
owedonlyatoneend,cal
l
edtop.
Ast ackisanabstractdatatype(ADT),
canbei mplementedinmostoftheprogr
ammi ng
l
anguages.Itisnamedasst ackbecauseitbehaveslikeareal
-worl
dstack.
Forexampl e:-pi
l
esofpl atesordeckofcardsetc.

Queue:Queueisal
inearl
isti
nwhichelement
scanbei
nser
tedonl
yatoneendcal
l
edr
earand
del
etedonlyatt
heotherendcal
l
edf r
ont.

I
tisanabst
ractdat
ast
ruct
ure,
simi
l
art
ost
ack.Queuei
sopenedatbot
hendt
her
efor
eitf
oll
ows

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717933
Fi
rst
-I
n-Fi
rst
-Out(
FIFO)met
hodol
ogyf
orst
ori
ngt
hedat
ait
ems.

NonLi
nearDataStr
uctur
es:Thisdat
astructur
edoesnotf
orm asequencei.
e.eachit
em or
el
ementi
sconnectedwitht
woormor eotheri
temsi
nanon-l
inearar
rangement.Thedat
aelement
s
ar
enotarr
angedinsequent
ialstr
uct
ure.

Ty
pesofNonLi
nearDat
aSt
ruct
ures:

Trees:
Treesar
emulti
leveldat
astr
uct
ureswithahi er
archi
calrel
at i
onshi
pamongitsel
ement
s
knownasnodes.Thebottommostnodesinthehierarchyar
ecalledleafnodewhil
ethet
opmost
nodeiscall
edr
ootnode.Eachnodecontai
nspointerstopointadjacentnodes.

Treedatastructur
eisbasedont heparent
-chi
ldrelat
ionshi
pamongt henodes.Eachnodei
nthe
tr
eecanhav emor ethanonechildexcepttheleafnodeswhereaseachnodecanhav eatmostone
parentexcepttherootnode.Tr
eescanbecl assif
iedintomanycat
egories.

Graphs:Graphscanbedef
inedast hepi
ctor
ialr
epr
esent
ati
onoft
hesetofelement
s(repr
esent
ed
byverti
ces)connect
edbyt
helinksknownasedges.Agraphisdi
ff
erentf
rom t
reei
nthesensethat
agraphcanhav ecycl
ewhi
lethetreecannothavet
heone.

Oper
ati
onsondat
ast
ruct
ure

1)Tr aver sing: Everydat astructur econt ainst hesetofdat aelement s.Tr av ersingt hedat astructure
meansv isitingeachel ementoft hedat ast ruct urei nordert oper f
orm somespeci ficoper ati
onl i
ke
searchi ngorsor t
ing.
Exampl e:I
fweneedt ocal cul at
et heav erageoft hemar ksobt ainedbyast udenti n6
diff
erentsubj ect,weneedt ot r
av erset hecompl etear rayofmar ksandcal cul atethet otalsum,
thenwewi lldivi
det hatsum byt henumberofsubj ectsi.e.6,inor dertof indt heav erage.
2)Inser tion: Inserti
oncanbedef inedast hepr ocessofaddi ngt heel ement st ot hedat ast r
uctureat
anylocat ion.
Ifthesi zeofdat ast r
uctur eisnt henwecanonl yinsertn- 1dat ael ement sintoi t
.
3)Del etion: Thepr ocessofr emov inganel ementf rom thedat ast ructurei scal l
edDel eti
on.Wecan
deleteanel ementf r
om t hedatast ructureatanyr andom l ocat i
on.
Ifwet r
ytodel eteanel ementf r
om anempt ydat astructur ethenunder flowoccur s.
4)Sear chi ng: Thepr ocessoff i
ndi ngt hel ocationofanel ementwi t
hint hedat ast ructureiscalled
Searchi ng.Ther ear etwoal gorithmst oper form sear ching,LinearSear chandBi narySear ch.
5)Sor ting: Theprocessofar rangi ngt hedat ast r
uct ureinaspeci f
icorderi sknownasSor ti
ng.
Therear emanyal gor i
thmst hatcanbeusedt oper form sor t
ing, forexampl e,inserti
onsor t
,
selectionsor t
,bubbl esor t
,etc.
6)Mer ging: Whent wol istsListAandLi stBofsi zeM andNr espect i
vely, ofsi mi l
artypeof
element s, clubbedorj oinedt opr oducet het hirdlist,ListCofsi ze( M+N) , thent hi
spr ocessi s
call
edmer ging

Charact
eri
sti
csofaDataStr
ucture
 Co r
rect
ness−Datast
ructur
eimpl
ement
ati
onshoul
dimpl
ementi
tsi
nter
facecor
rect
ly.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717934
  Ti
meCompl exi
ty−Runni
ngt
imeortheexecut
iont
imeofoperati
onsofdat
ast
ruct
uremust
beassmal l
aspossibl
e.
 SpaceCompl exi
ty−Memoryusageofadat astruct
ureoperat
ionshoul
dbeasl i
tt
leas
possi
ble.

Algorit
hm
Analgori
thm i
saprocedurehavingwelldefinedst
epsf orsolv
ingaparti
cularpr
oblem.
Algorit
hm isfinit
esetofl
ogicorinst
ructions,
writt
eninorderforaccomplisht
hecer t
ainpredef
ined
task.Itisnotthecomplet
epr ogr
am orcode, i
tisjustasolut
ion(logi
c)ofaproblem,whichcanbe
representedeitherasani
nformaldescripti
onusingaFlowchar torPseudocode.

Themajorcat egor i
esofal gorithmsar egivenbelow:
 Sor t
: Algor it
hm dev elopedf orsor t
ingtheitemsincertainorder
.
 Sear ch: Algor i
thm dev elopedf orsear chingthei
temsi nsideadatast r
uct
ure.
 Delet e:Al gori
t hm dev elopedf ordel et
ingtheexi
stingelementfrom thedatast
ructure.
 Insert: Algorithm dev elopedf ori nsert
inganitem i
nsideadat astr
ucture.
 Updat e:Al gorithm dev elopedf orupdat i
ngtheexisti
ngelementinsideadatastructure.

Theper
for
manceofal
gor
it
hm i
smeasur
edont
hebasi
soff
oll
owi
ngpr
oper
ti
es:

Timecompl exity:Itisawayofr epresentingtheamountoft imeneededbyapr ogram toruntothe

completi
on.
Spacecompl exity:Itistheamountofmemor yspacer equi
redbyanalgori
thm,duringacourseof
i
tsexecution.Spacecompl exi
tyisrequiredinsituati
onswhenl i
mitedmemor yisavail
abl
eandfor
themultiusersy stem.
Eachalgorit
hm musthav e:
Speci f
ication:Descripti
onoft hecomput ati
onalprocedur
e.
Pre-conditions: Thecondi t
ion(s)oninput.
Bodyoft heAl gorit
hm: Asequenceofcl earandunambi guousinst
ruct
ions.
Post -
condi ti
ons: Thecondi ti
on(s)onout put.

Exampl
e:Desi
gnanal
gor
it
hm t
omul
ti
plyt
het
wonumber
sxandyanddi
spl
ayt
her
esul
tinz.

St
ep1:
START
St
ep2:
declaret hreeinteger
sx, y&z
St
ep3:
def i
nev aluesofx&y
St
ep4:
mul ti
plyv aluesofx&y
St
ep5:
storestheout putofstep4inz
St
ep6:
printz
St
ep7:
STOP

Al
ter
nat
ivel
ytheal
gor
it
hm canbewr
it
tenas?

St
ep1STARTMULTIPLY
St
ep2getval
uesofx&y
St
ep3z← x*y
L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717935
St
ep4di
spl
ayz
St
ep5STOP

Char
act
erist
icsofanAlgor
it
hm
Anal
gori
thm mustfol
lowthement
ionedbel
owchar
act
eri
sti
cs:

 I
nput: Analgori
thm musthave0orwelldefi
nedinput
s.
 Output:Analgorit
hm musthav e1orwel
ldefi
nedoutputs,andshoul
dmat chwit
hthe
desir
edout put.
 Feasibil
i
ty:Analgori
thm mustbeter
minatedaft
erthefi
nit
enumberofst eps.
 I
ndependent :Analgori
thm musthavest
ep-by-
stepdi
recti
onswhichisi
ndependentofany
programmi ngcode.
 Unambi guous:Analgorit
hm mustbeunambiguousandclear.Eachoft
heirst
epsand
i
nput/outputsmustbecl earandl
eadtoonlyonemeaning.

Al
gor
it
hm:
Al
gor
it
hm i
saf
ini
tesetofi
nst
ruct
ionst
hati
sfol
l
owed,
accompl
i
shesapar
ti
cul
art
ask.
(
OR)
Analgori
thm i
sasequenceofunambi
guousinst
ructi
onsforsol
vi
ngaprobl
em,i
.e.
,forobt
aini
nga
requi
redoutputf
oranylegi
ti
mate(l
awful
,legal
,reasonabl
egenui
ne)i
nputinafi
niteamountof
ti
me.

Ther
eissomethi
ngorsomeonecapabl
eofunder
standi
ngandf
oll
owi
ngt
hei
nst
ruct
ionsgi
ven.We
cal
lthi
sa"comput
er"
.

Al
lal
gor
it
hmsmustsat
isf
ythef
oll
owi
ngcr
it
eri
a:
1.Input:Itmaybezer oormor equantit
iesareexter
nall
ysuppl
ied.Butinputnotnecessar
yfor
allAlgori
thms.
2.Output :
Atleastonequantityisproduced.I
tismustforall
thealgori
thms
3.Definit
eness: Eachinst
ructi
onisclearandunambiguous.
4.Fini
teness:The i nstr
ucti
on (Steps)ofan al gori
thm mustbe f init
e.Means Al gor
it
hm
terminateaft
erfini
tenumberofst eps( I
nst
ruct
ions).

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717936
 5.Ef fect
iveness:Everyinst
ructionmustbev er
ybasicsothatitcanbecar r
iedout,
inpri
nci
ple,
byaper sonusingonlypenci landpaper.Itisnotenoughthateachoper at
ionbedefi
nit
e,it
alsomustbef easi
ble(possibleorr
eali
stic).
Thestudyofalgorithmsincl
udesmanyi mportantandacti
veareasofr esear
ch.Therear
efour
di
sti
nctareasofst udyonecani dentif
y:

1.Howt
odev
iseal
gor
it
hms -

2.Howt
oval
i
dat
eal
gor
it
hms

3.Howt oDesi gnalgori

thms
4.Howt otestingalgori
thms
Exampl eforalgor i
thm:
Wr i
teanal gori
thm t oaddtwonumbersent
eredbyuser.
Step1: Start
.
Step2: Declarev ar
iablesnum1,num2andsum.
Step3: Readv aluesnum1andnum2.
Step4: Addnum1andnum2andassi gntheresul
ttosum.
sum←num1+num2.
Step5: Displaysum.
Step6: Stop.
Algori
thm specification.

PseudocodeConv
ent
ions
 Algorithm canbedescr i
bedi nmanyway sl ikeEngl
ishforspecifyi
ngalgori
thm i
nst epby
stepandFl owchar
tf orgraphicalrepresent
at i
on.
 Butt heset wowayswor kwel lonlyifalgor
ithm issmallorsimple.Forl
argeorbigalgori
thm
wear egoingtousepseudocode.
 Pseudocodei saki ndofst r
ucturedEngl i
shf ordescr
ibi
ngalgorit
hms.
 Ital l
owst hedesignert of ocusont helogi cofthealgorit
hm wi t
houtbeingdistracted
(diverted)bydetai
l
sofl anguagesy ntax.
 Att hesamet i
me,thepseudocodeneedst obecompl ete.Itdescri
bestheenti
rel
ogicoft he
algorithm sothati
mpl ement ati
onbecomesar ot
emechanicaltaskoftransl
ati
ngli
nebyl ine
i
nt osour cecode.

NOTE:
Alt
ernat
ivel
y,wecanexpr
esst
hesameal
gor
it
hm i
napseudocode:

Exampl
eforpseudocode:

ALGORITHM Sum(num1,num2)
I
nput:r
eadnum1,num2
Output
:wri
tesum ofnum1&num2
{
Readnum1,num2;
Sum =num1+num2;
Writ
esum;
}
Pseudocodeconversi
on:

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717937
 1.“//”I susedt opr ov idecommentl ine.
2.Usingofmat chi ngpar enthesis“ {}
”t ofor m blocks.Acompoundst at ement( i
.e.,Coll
ecti
onof
simpl est atement s)canber epr esent edasabl ock.
3.Ani dent ifierbegi nswi thal ett er.Dat at ypesofv ari
abl
esar enotexpl i
cit
lydecl ar
ed.But
typeswi l
l becl earf rom t hecont extwhet herav ari
ableisglobalorlocal toapr ocedure.
Forexampl e:
node=r ecor d
{
dat at ype_ 1dat a_1;
.
.
dat at ype_ ndat a_n;
node* l
ink;
}
4.Assignmentofv aluest ovar i
abl esi sdoneusi ngassi gnmentstatement .
<variable>: =<expr ession>;
5.Therear e
 TwoBool eanv aluest rueandf alse.
 Logi cal oper ator“ and, orandnot ”insteadof“ &,|
|,
!”respectivel
y .
 Rel at i
onoper ator“ <,≤, =, ≠,≥and>” .
6.Element sofmul tidimensi onalar r
ay sar eaccessedusi ng[and] .Forexampl e,ifAisat wo
dimensi onalar ray ,the( i,j)
thel ementoft hear rayi
sdenot edasA[ i,j
].Arrayindices(index
)
startatzer o.
7.Loopi ngst atementar eempl oy ed: whi l
e, repeatuntilandforaslikebel ow
Gener al repr esent ation Pseudocoder epresentation
Whi l
e( condi ti
on) { Whi l
e<condition>do{
Stmt 1; <st mt1>;
Stmtn; <st mtn>;
} }
do{ repeat{
Stmt 1; <st mt1>;
Stmtn; <st mtn>;
} Unt il<condit
ion>
Whi l
e( condi t
ion) ; }
for(initi
al i
zat ion; condi ti
on;expr essio f orv ari
able:=val
ue1t onst epst ep
n) do
{ {
Stmt 1; <st mt1>;
Stmtn; <st mtn>;
} }

8 Aconditi
onalst
atement:
ifandswi
tchhast
hefoll
owingfor
ms:
General
form Pseudocodef
orm
i
f(condit
ion) If<condi
ti
on>then
st
mt 1; <Stmt1>:
el
se else

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717938
 stmt2 <stmt2>;
Switch(condit
ion)
{ case
Caselabel:stmt1; {
break; :
<conditi
on1>:<st
mt1>
. .
defaul
t:stmt; :
<conditi
onn>:
<stmtn>
} :
else:<st
mtn+1>
}

9 Inputandoutputaredoneusi ngtheinstr
uct
ionsr
eadandwr
it
e.Nof
ormati
susedt
o
specif
ythesi
zeofinputorout
putquant
iti
es.

10Ther
eisonl
yonetypeofpr
ocedur
e:Al
gor
it
hm.Anal
gor
it
hm consi
stsofaheadi
nganda
body
.Theheadi
ngt
akest
hefor
m

Al
gor
it
hm Name(
<par
amet
erl
i
st>)

Algorithm forfi
nds&retur
nsthemaxi mum ofngi v ennumber s
Ingener al way(progr
am) I
nalgori
thm ( pseudocode)
A[n]={9,3,
…}; Algor it
hm max( A, n)
Resul t=A[0]
; //Ai sanarrayofsi zen
for(i=1;i
<=n-1;i++){ {
i
fA[ i]>Result; Resul t:=A[
1];
Resul t=A[i]
; fori:=2t ondo{
} i
fA[ i]>Resul t
;thenResul t:=A[i
];
pri
nt f(Result); returnResul t
;
}
Al
gori
thm f
orsel
ect ionsorti
ng
Pr ogram Al gorithm
mai n(){ Algor it
hm SelectionSor t
(a,n)
i
nts, i
,j,t
emp, a[20] ; //sort hear r
ayaofn- element s.
for(i=0;i<s;i
++) { {
for(j
=i+1; j
<s;j++){ fori:=1t ondo{
temp=a[ i]; j
:=i;
a[i
]=a[j]; fork: =i
+1tondo
a[j
]=temp; i
f(a[k]<a[j
]thenj:=k;
} t:
=a[ i]
;
} a[i
];=a[j]
;
} a[j
]:=t;}}
Recur siveAlgor i
thms:
Af unct i
oniscal l
edi tsel
ftheni
tcall
edrecur
sivef uncti
on.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 80192717939
 Voidmain(
)
{
Fun1()
;/
/ mai
n() cal
l
s
Fun1
}
VoidFun1(
)
{
Fun1()
;
}
Forexampl e
//apartofc-pr ogr
am
Voidmai n(){
i
nti=5;
pri
ntf
(fact(i
))
;
}
i
ntfact(i
nti)
{
i
f(i
<=1)
{
ret
urn1;
}
ret
urni*fact(
i-
1);}

Simi
larl
yanalgori
thm i
ssaidtoberecur
siv
eifthesamealgori
thm isi
nvokedinthebody.Ther
ear
e
twotypesofRecursi
vealgor
ithms.
 Directr
ecursi
vealgor
it
hm anal gori
thm t
hatcal
l
sitselfi
sdir
ecti
verecursi
ve.

 Indi
rectrecursi
vealgorit
hm anal gori
thm, i
fitcallsanotheral
gorithm i
sindir
ect
recursi
v e.Meansal gorit
hm Ai ssaidtobei ndi
rectrecursi
veifi
t
calls anot heralgori
thm whichinturncallsA.
Exampleforrecursi
vealgorit
hm:
TowersofHanoi Problem simpler
ul es:
 Onlyonedi skcanbemov edatat i
me.
 Eachmov econsistsoftaki
ngt heupperdi skfrom oneoft hestacksandpl aci
ngi tontopof
anotherstacki.
e.adi skcanonl ybemov edifitistheuppermostdi skonast ack.
 Nodi skmaybepl acedontopofasmal lerdi
sk.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179310
Av
eryel
egant(
Sty
leordesi
gnordr
ess)sol
uti
onf
ort
hist
owerofHanoi
byusi
ngRecur
sion.

Forndi
sks,
tot
al2n–1mov
esar
erequi
red

Al
gor
it
hm f
orsol
vi
ng“
Tower
sofHanoi
”byusi
ngr
ecur
sional
gor
it
hm:

Algori
thm TowersOf Hanoi(n,x,
y,z)
//
Mov et hetopndi sksform TowerxtoTowery
{
i
f(n≥1)then
TowerOf Hanoi(
n-1,x,z,y
);
writ
e(“Mov etopdiskf orm Towerxtotopoftower
y)
;
TowerOf Hanoi(
n-1,
z,y,
x);
}
}

Expl
anation:
Assumet hatthenumberofdi sksinn.Togett hel ar
gestdi skt
othebott
om ofTowery ,wemove
theremainingn-1di
skstotowerz.Andt henmov et helargestdi
skf
ormtowerxt otowerb.
Nowt oweryhasl ar
gestdi
skandt owerxi sempt yandt owerzhasn-1i
ndecreasingorder.
Herewel efttheremai
ningtaskthatismov ingn-1disksf ormtowerZtotowerY.Fort hisweuse
samepr ocedurebyusi
ngtowerxi sint
ermedi at
estorage.

Forexample:
Input: ifnumberofdi
sksn=2
Output:Total
numberofmoves=2n-
1

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179311
 2
2-1=3mov esasshownbel ow
S-
1:Di sk1mov edf
rom At oB
S-
2:Di sk2mov edfrom AtoC
S-
3: Disk1mov edfr
om Bt oC
Si
mi l
arlyfornumberofdisks=3
I
nput: 3
Output:
S-1:
Disk1mov edfrom AtoC
S-2:
Disk2mov edfrom AtoB
S-3:
Disk1mov edfrom CtoB
S-4:
Disk3mov edfrom AtoC
S-5:
Disk1mov edfrom BtoA
S-6:
Disk2mov edfrom BtoC
S-7:
Disk1mov edfrom AtoC

PerformanceAnal ysi
s
I
ntroducti
on:
AnalyzeAlgori
thmsorper formanceanal
ysi
s:
I
fanal gori
thm isexecuted,i
tusedthe
 Comput er ’
sCPU t operf
ormtheoperati
ons.
 Memor y(bothRAM andROM) t oholdtheprogr
am &dat
a.
Analysisofal
gor i
thmsi sthetaskofdet
ermininghowmuchcomputingt
imeandst
oragememor
y
requir
edforanal gori
thm.

Theyar
emanycr i
ter i
auponwhichwecanj udgeanalgor
it
hm t osayitperform well
.
1)Doesi
tdowhatwewanti ttodo?
2)Doesi
tworkcor r
ectl
yaccordi
ngtotheori
ginal
specif
icati
onsoft het ask?
3)I
sther
edocument ati
onthatdescr
ibeshowtouseitandhowi tworks?
4)Arepr
ocedur escreat
edinsuchawayt hatt
heyperfor
ml ogicalsubf uncti
ons?
5)I
sthecoder eadable?

Per
for
manceev al
uati
onhast womaj orphases
 Pri
oriesti
matesPer f
or manceanalysi
s
 Posteri
ortest
ing Performancemeasur ement
s

SpaceComplexi
ty:
Defi
nit
ion:
Thespacecomplexi
tyofanal
gor
it
hm i
stheamountofmemor
yitneedst
orunt
ocompl
eti
on.

Thespaceneededbyal
gor
it
hm i
sthesum off
oll
owi
ngcomponent
s

 Af i
xed par
tthatisindependentoft hecharact
eri
sti
csofi nputand out
put
.Exampl
e
Number&si ze.Inthi
sincludesinst
ructi
onsspace[spaceforcode]+Spacef orsi
mpl
e
var
iabl
es+Fixed-
sizecomponentvari
ables+Spaceforconst
ant&soon.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179312
  Av ar
iabl
epart
t hatconsi
stsoft
hespaceneededbycomponentv ar
iabl
eswhosesi zeis
dependenton the par
ti
cul
arprobl
em inst
ance bei
ng sol
ved + The space needed by
ref
erencedv
ari
ables+Recursi
onst
ackspace.

Thespacer
equi
rementS(
P)ofanyal
gor
it
hm Pcanbewr
it
tenas

S(
P)=C+SP
CConstant
SP I
nst
ancechar
act
eri
sti
cs.

Find space compl exi

ty of it
erat
ive Fi
ndspacecompl
exi
tyf
orRecur
siv
eal
gor
it
hm:
Algori
thm ofsum of‘n’number
s.
Algori
thm: Al
gor i
thm:
Algori
thm sum(a,n) Al
gor i
thm RSUM(a,
n)
//Hereai sar
rayofSizen //
ai sanarrayofsi
zen
{ {
S:=0; I
f(n≤0)thenret
urn0;
i
f(n≤0))thenret
urn0; El
ser etur
na[n]
+RSUM(a,
n-1)
;
fori:
=1tondo }
s:=s+a[i
];
retur
ns;
}
Spacecompl
exi
tyS(P)
: SpaceCompl exi
ty:
s1wor d Ther ecursi
onst ackspacei ncludesspacef or
i
1wor d thefor malparamet ers,thelocalv ar
iabl
esand
n1wor d S(P)
≥n+3 thereturnaddress.
anwor d Returnaddressr equires1wor dmemor y
Eachcal ltoRSUM r equires atleast3wor ds
Wordis a St
ri
ng of bi
ts st
ored i
n (Iti
ncludesspacef ort hev al
uesofn, theret
urn
comput
ermemory
,it
ssizeisa4t o64 addressandapoi ntertoa[ ]
).
bi
ts. Thedept hrecursionisn+1
Ther ecursi
onstackspaceneededi s≥3(n+1)

Ti
mecompl
exi
tyT(
P):

Def
ini
ti
on:
Ti
mecompl exi
tyofanal
gor
it
hm i
stheamountofcomput
ert
imei
tneedst
orunt
ocompl
eti
on.
Her
eRUNmeansCompi l
e+Execut
ion.
Ti
meCompl exi
ty
T(
P)=t
c+t
p

Butwearenegl
ecti
ngtcBecauset
hecompilet
imedoesnotdependsontheinst
ance
char
act
eri
sti
cs.Thecompil
edprogram wi
l
lberunsev
eral
timeswithoutr
ecompil
ati
on.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179313
So T(P)
=tp
Her
etp i
nst
ancechar
act
eri
sti
cs.

Forexampl e:
Thepr ogram pdosomeoper ati
onslikeADD, SUB,MULet c.
I
fweknewt hecharacterist
icsofthecompi l
ertobeused, wecoul
dprocesstodeter
minethe
numberofaddi t
ions,subtract
ions,multi
pli
cati
ons,di
vi
sions,compar
es,l
oads,st
oresandsoon.
Weobt ai
ntp(n)expressasf oll
ow:
tp(
n)=CaADD( n)+CSSUB( n)+CmMUL( n)+CdDIV(n)
+…..
..
..
..

n Instancecharacter
ist
ics
Ca,CS,Cm,Cd,….
.. t i
meneededf oranadditi
on,Subt r
acti
on,multipli
cati
on,di
v i
sion,
and
et
c.
ADD, SUBB, MUL,DIV Arefuncti
ons,whosev al
uesar ethenumber sofaddit
ions,
subtr
acti
ons,multi
pli
cati
ons,..et
c,thatareperformedwhent he
codeforpisusedonani nstancewithchar act
eri
sti
cs.
PerformanceMeasur ement
Program step:
Program st
episthesyntacti
cal
lyorsemant i
call
ymeani ngfulsegmentofapr ogr
am.
Andi thasanexecutionti
met hati
sindependentoftheinstancecharacteri
stics.

Example:
 Forcomment / /-
-zerosteps
 Forassignmentstatement s(Whichdoesnotinvol
veanycal l
stootheralgor
it
hms)
:=onest ep
 Forit
erati
vestatementssuchas“ for
,whil
eanduntil
-r
epeat”stat
ements,weconsidert
he
stepcountsonlyforcontrolpartofthestat
ement.
Forwhileloop“while(<expr>)do“: thestepcountforcontr
olpartofawhil
estmtis
Numberofst epcountsf orassignablet
o<expr>

Forforl
oopiefori
:
=<expr>to<expr
1>do: Thest
epcountofcont
rol
partof“
for
”
stat
ementi
s Sum ofthecountof<expr
>&<expr1>Nandremaini
ngexecuti
onoft
he“
for
”
stat
ement,
i.
e.,
one.

Wedet erminethenumberofst
epsneededbyapr ogr
am t
osol
veapart
icul
arprobl
em.For
t
hist
herear etwomet hods.
1)Firstmet hodis,i
ntr
oducea newv ar
iabl
e“count
”int
othepr
ogr
am forfi
ndingnumber
ofstepsinprogram.

2)Secondmethodi
s,bui
l
dinga“
tabl
e”i
nwhi
chwel
i
stt
het
otal
numberofst
epscont
ri
but
ed
byeachst
atement
.

Exampl
efor1stmet
hod:

Fi
nd t i
me compl exi
ty of Iter
ati
ve Fi
ndt
imecompl
exi
tyf
orRecur
siv
eal
gor
it
hm:
al
gor
it
hm ofsum of‘
n’number
s.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179314
Algori
thm: Algorit
hm:
Algori
thm sum( a,
n) Algorit
hm RSUM( a,n)
{ {
//countisglobaliti
si ni
ti
all
yzero Count: =count+1;
//f ori
fcondit
ion
S:=0; I
f (
n≤0)t hen
Count:=count+1;//countforassignment {
fori:
=1tondo Count :
=count+1;//forretur
nstmt
{ return0;
Count:=count+1;//for“f
or”loop }
s:=s+a[i
]; Else{
count:=count+1;//f
orassingment Count: =count+1;
} //fortheadditi
on,functi
oninvocat
ion&r
etur
n
Count: =count+1;//forlastt i
meoff or returna[n]+RSUM(a,n-1)
;
l
oop }
Count:=count+1;//forretur
nst mt }
retur
ns;
}
I
fn=0t hent Rsum( 0) =2
I
fn>0t henincr easesby2, i
e.,
2+t
Rsum(
n-1)
Means
t
Rsum(
n)=2+t Rsum( n-1)
Fi
nall
ycountv
aluesi
s=2n+3; =2+2+t Rsum(n-2)
Sototal
numberofst
eps=2n+3 =2+2+2+t Rsum(n-
3)
.
.
=2(n)
+t Rsum( n-n)
=2n+t Rsum( 0) =2n+2

I
ntheabov
eexampl
ether
ecur
siv
eal
gor
it
hm hasl
esst
imecompl
exi
tyt
heni
ter
ati
veal
gor
it
hm.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179315
 nd
Exampl
efor2 met
hod:

Findti
mecompl exi
tyofAl
gor
it
hm ofsum of‘n’
numbers.
Statements s/e Frequency Total
steps
1.Algori
thm sum(a,
n) 0 _ 0
2.{ 0 _ 0
3.S:=0; 1 1 1
4.fori:
=1tondo 1 n+1 n+1
5.s:=s+a[i
]; 1 n n
6.retur
ns; 1 1 1
7.} 0 _ 0

2n+3

Fi
ndti
mecompl exi
tyf
orRecur
siv
ealgori
thm
St
atement s s/e Fr equency Total
n=0n>0 steps
n=0n>0
1.Al gori
thm RSUM(a,
n) 0 _ _ _ _
2.{ 0 _ _ _ _
3.If (
n≤0)then 1 1 1 1 1
4.r etur
n0; 1 1 0 1 0
5.El se 0
6.r etur
n a[ n]
+RSUM(a,
n- 1+x 0 1 0 1+x
1); 0 _ _ 0 0
7.}

2 2+x

Her
ex=t Rsum(n-
1)
Asy mptot
icNot
ati
on:
Aprobl
em mayhav enumerous(many
)al
gor
it
hmi csol
uti
ons.I
nor
dertochooset
hebest
algori
thm f
orapart
iculartask,y
ouneedt
obeabl
etojudgehowlongapar
ti
cul
arsol
uti
onwil
ltake
torun.

Asy
mpt
oti
cnot
ati
onofanal
gor
it
hm i
samat
hemat
ical
repr
esent
ati
onofi
tscompl
exi
ty

Asymptoti
cnot ati
oni sused toj
udgethebestal
gori
thm among numerousalgor
it
hmsf
ora
par
ti
cularproblem.
Asymptoti
ccompl exi
tyisawayofexpr
essi
ngt
hemaincomponentofal
gor
it
hmslike
 Cost
 Ti mecompl exity
 Spacecompl exit
y
SomeAsy mpt oticnotati
onsar
e
1.BigohO

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179316
 2.OmegaΩ
3.Thetaθ
4.Li
ttl
eoho
5.Li
ttl
eOmegaω

1.Bi
g-OhNot
ati
on(
O)

Bi
g-Ohnot
ati
oni
susedt
odef
inet
heupperboundofanal
gor
it
hm i
nter
msofTi
meCompl
exi
ty.

ThatmeansBi g-Ohnotat
ionalway
sindicat
esthemaxi
mum t
imerequi
redbyanalgor
ithm f
oral
l
i
nputvalues.ThatmeansBig-Ohnotat
iondescri
best
hewor
stcaseofanalgor
it
hm ti
me
complexit
y.

Bi
g-OhNot
ati
oncanbedef
inedasf
oll
ows.
..

Thefunct
ionf
(n)=O(
g(n)
)(readas“ fofnisbi
gohofgofn)i
ff(
ifandonl
yif
)ther
eexi
tposi
ti
ve
const
antscandn0suchthatf(
n)<=c*g(n)f
oral
ln,
n>=n0
f
(n)
=O(
g(n)
)

Consi
dert
hefoll
owinggr
aphdrawnf
ort
hev
aluesoff
(n)andCg(
n)f
ori
nput(
n)v
alueonX-
Axi
s
andti
merequi
redisonY-Axi
s

I
nabovegraphaft
eraparti
cul
ari
nputv
aluen0,
alway
sCg(
n)i
sgr
eat
ert
hanf
(n)whi
chi
ndi
cat
es
t
heal
gori
thm'supperbound.

Exampl
e

Considert
hef
oll
owingf(
n)andg(n)
..
.
f(
n)=3n+2
g(n)=n
I
fwewantt or
epresentf
(n)asO(
g(n))t
heni
tmustsat
isf
yf(
n)<=Cxg(
n)f
oral
lval
uesofC>
0andn0>=1

f
(n)<=Cg(
n)

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179317
⇒3n+2<=Cn

Abovecondi
ti
oni
sal
waysTRUEforal
lval
uesofC=4andn>=2.
ByusingBi
g-Ohnot
ati
onwecanrepr
esentt
heti
mecompl
exi
tyasf
oll
ows.
..
3n+2=O( n)

2.Bi
g-OmegaNot
ati
on(
Ω)

Bi
g-Omeganot
ati
oni
susedt
odef
inet
hel
owerboundofanal
gor
it
hm i
nter
msofTi
me
Compl
exi
ty.

ThatmeansBi g-Omeganotat
ional
way
sindi
catest
hemi ni
mum timerequi
redbyanal
gor
it
hm f
or
al
linputv
alues.ThatmeansBi
g-Omeganotat
iondescr
ibesthebestcaseofanal
gor
it
hm t
ime
complexi
ty.

Bi
g-OmegaNot
ati
oncanbedef
inedasf
oll
ows.
..

Thefuncti
onf
(n)=Ω(
g(n)
)(r
eadas“ fofnisomegaofgofn)if
f(i
fandonl
yif
)ther
eexi
t
positi
veconst
ant
scandn0suchthatf
(n)>=c*
g(n)f
oral
ln,
n>=n0 f
(n)
=Ω( g(
n))

Consi
dert
hefoll
owinggr
aphdrawnf
ort
hev
aluesoff
(n)andCg(
n)f
ori
nput(
n)v
alueonX-
Axi
s
andti
merequi
redisonY-Axi
s

Inabovegraphaft
eraparti
cul
ari
nputv
aluen0,
alway
sCxg(
n)i
slesst
hanf
(n)whi
chi
ndi
cat
est
he
algor
it
hm'slowerbound.

Exampl
e

Consi
dert
hef
oll
owi
ngf
(n)andg(
n).
..
f(
n)=3n+2

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179318
g(
n)=n
I
fwewanttorepr
esentf
(n)asΩ(
g(n)
)theni
tmustsat
isf
yf(
n)>=Cg(
n)f
oral
lval
uesofC>
0andn0>=1

f
(n)>=Cg(
n)
⇒3n+2<=Cn

Abovecondi
ti
oni
sal
waysTRUEforal
lval
uesofC=1andn>=1.
ByusingBi
g-Omeganot
ati
onwecanrepresentt
het
imecompl
exi
tyasf
oll
ows.
..
3n+2=Ω( n)

3.Bi
g-Thet
aNot
ati
on(
Θ)

Bi
g-Thet
anotat
ioni
susedt
odef
inet
heav
erageboundofanal
gor
it
hm i
nter
msofTi
me
Compl
exi
ty.

ThatmeansBi g-Thet
anotat
ional
waysindicat
estheaveraget
imerequi
redbyanalgori
thm f
oral
l
i
nputvalues.ThatmeansBi
g-Thetanot
ationdescri
bestheaver
agecaseofanalgori
thm t
ime
complexit
y.

Bi
g-Thet
aNot
ati
oncanbedef
inedasf
oll
ows.
..

Thefuncti
onf(n)=Θ(g(
n))(
readas“fofni
sthetaofgofn)i
ff(
ifandonl
yif
)ther
eexi
stposi
ti
ve
const
antsc1,
c2andn0suchthat
c1*
g(n)
<=f(
n)<=c2*
g(n)f
oral
ln,
n>=n0
f(
n)=Θ( g(
n))

Consi
dert
hefoll
owinggr
aphdrawnf
ort
hev
aluesoff
(n)andCg(
n)f
ori
nput(
n)v
alueonX-
Axi
s
andti
merequi
redisonY-Axi
s

I
nabovegraphaf
terapart
icul
ari
nputval
uen0,
alway
sC1g(n)i
slesst
hanf
(n)andC2g(
n)i
s
gr
eat
erthanf(
n)whichi
ndicat
estheal
gori
thm'
saver
agebound.

Exampl
e

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179319
Considert
hef
ollowingf(
n)andg(n)
..
.
f(
n)=3n+2
g(n)=n
I
fwewantt orepresentf
(n)asΘ(
g(n))t
heni
tmustsat
isf
yC1g(
n)<=f
(n)>=C2g(
n)f
oral
lval
ues
ofC1,C2>0andn0>=1

C1g(
n)<=f
(n)>=⇒C2g(
n)
C1n<=3n+2>=C2n

Abovecondit
ioni
sal
waysTRUEforal
lvaluesofC1=1,
C2=4andn>=1.
ByusingBi
g-Thetanot
ati
onwecanrepresentt
heti
mecompl
exi
tyasf
oll
ows.
..
3n+2=Θ( n)

1.Lit
tleoh:o
Thefuncti
onf(n)
=o(
g(n)
)(r
eadas“
fofni
sli
tt
leohofgofn”
)if
f
Li
mf (n)
/g(n)
=0 f
oral
ln,n≥0
n~
Example:
3n+2=o(n2)as

Li
m((3n+2)
/n2)
=0
n~

2.Lit
tl
eOmega:
ω
Thef
unct
ionf
(n)
=ω(g(
n))(
readas“
fofni
sli
tt
leohomegaofgofn”
)if
f

Li
m g(n)/
f(n)
=0 f
oral
ln,
n≥0
n~
Example:
3n+2=o(n2)as

Li
m(n2/
(3n+2)=0
n~

Gr
aphf
orv
isual
i
zet
her
elat
ionshi
psbet
weent
hesenot
ati
ons

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179320
 Per
for
manceMeasur
ement

Or
derofGr
owt
h

 Anyal
gor
it
hm expect
edt
odowor
kfastf
oranyi
nputsi
ze

 Forexampl
e:sor
ti
ngofel
ement
s(n=5)whent
hei
nputsi
zei
ssmal
ltheal
gor
it
hm wor
ksf
ine

 Whenweincreasest
hesi
zeofi
nputwecananal
yzehowcanoural
gor
it
hm wor
ksf
or
exampl
e:whenn=5000el
ement
showouralgor
it
hm works

 Orderofgr
owt
hmeanshowy oural
gor
ithm perf
orm accr
odi
ngtotheinputsize.
whent
he
i
nputchanget
henal
gori
thm perf
ormanceisalsochangethecal
culat
ionofthis
perf
ormancei
sanal
ysi
sofalgori
thm.

Forexampl
e:Li
nearSear
ch

Thesimplestandmostobv i
ouswayt osearchatabl
eistouseLinearsear
chi
.e.examine
t
he1st,2nd,3rd,
.
..ent
ri
esunt
ilt
heent r
ywiththerequi
redkeyisfoundort
heendofthetableis
r
eachedwithouttheentr
ybei
ngf ound.Thebodyofthesearchfuncti
oncouldbewri
ttenasfoll
ows
i
fLi
nearsearchisused:

i
ntfound;
i
nti ;
found=FALSE;
i=0;
whi l
e( !
found&&i
<n)
{
if(!
strcmp(wor
d,t
able[i
].
key))/
/strcmpret
urnszer
o
//ifst
ringsaresame
{
found=TRUE;
index=i;
}
elsei++;
}
returnfound;

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179321
  Theef ficiencyofLinearsearchisnowconsider
ed.Inassessi
ngtheeffi
ciencyofan
algorit
hm i tisusualtocountthenumberofoccurrencesofsometypicaloperati
onasa
functionoft hesizeofthepr obl
em.
 Insear chingt hemajoroperati
onisthenumberofcompar i
sonsofthesearched-forkey
againstt het abl
eentri
esandt heprobl
em si
zeistakentobethenumberofent r
iesinthe
table.Hencei nLi
nearsearchofat abl
ewithnentri
eswehav e:

BestCase:

I
sthemi
nimum numberofst
epst
hatcanbeachi
evedf
orgi
venpar
amet
ers.

Fi
ndatf
ir
stpl
ace-onecompar
ison

Wor
stCase

I
sthemaxi
mum numberofst
epst
hatcanbeachi
evedf
orgi
venpar
amet
ers

Fi
ndatnt
hpl
aceornotatal
l-ncompar
isons

Av
erageCase

Av
eragecasei
sthesi
tuat
ioni
nwhi
chi
tisnotei
therbestcaseorwor
stcase

El
ementi
sfoundsomewher
eint
hemi
ddl
eoft
hel
i
st

Pr
obabi
l
ityofsuccessf
ulsear
chi
sp

Pr
obabi
l
ityofunsuccessf
ulsear
chi
s1-
p

Consi
dert
hegi
venel
ementi
sfoundatposi
ti
on‘
i
’thent
hepr
obabi
l
ityoff
indi
ngt
hatel
ement‘
i
’is
p/n

CAv
g(n)=[
1*p/
n+2*
p/n+3*
p/n+….
+n*
p/n]
+n[
1-p]

Successf
ulsear
ch unsuccessf
ulsear
ch

=p/
n[1+2+3+4+……….
+n]
+n[
1-p]

=p/
n[n(
n+1)
/2]
+n[
1-p]

=p(
n+1)
/2+n[
1-p]

CAv
g(n)
=p(
n+1)
/2+n[
1-p]

Forsuccessf
ulsear
chp=1t
heabov
eequat
ioncanbewr
it
tenas

CAv
g(n)
=1(
n+1)
/2+n[
1-1]

=n+1/
2

Forunsuccessf
ulsear
chp=0t
heabov
eequat
ioncanbewr
it
tenas

CAv
g(n)
=0(
n+1)
/2+n[
1-0]

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179322
 =n

HenceLinearSear
chi
sanorder
(n)process-i
.e.i
ttakesati
mepr opor
ti
onalt
othenumberof
ent
ri
es.Forexamplei
fnwasdoubledthen,onaverage,
thesear
chwoul dt
aketwi
ceaslong.

 Performancemeasurementisthepr
ocessofexecut
ingacorrectpr
ogram ondif
ferentdat
a
setstomeasurethet i
meandspacet hati
ttakestocomputet heresul
ts.Complexi
tyofa
program i
sgener
all
ysomef uncti
onoft
heinst
ancecharact
eri
sti
cs

 Theulti
matetesti
sperfor
medt oensur
ethatt
heprogram dev
elopedonthebasisofthe
desi
gned al
gori
thm,runs sat
isf
act
ori
ly
.Testi
ng a pr
ogram invol
ves t
wo phases v
iz.
,
debuggi
ngandprofi
l
ing.

 Debuggingistheprocessofexecut
ingapr
ogr
am wi
thsampl
edat
aset
stodet
ermi
nei
fthe
resul
tsobtai
nedaresatisf
act
ory.

 Howev er
,iti
spoi ntedoutthat“debuggingcanonl yindicatethepr esenceoferrorsbutnot
thei
rabsence”i.e.,aprogram thaty i
eldsunsat i
sfactoryresult
sonasampl edat asetis
defi
nit
elyfaul
ty,buton t heot herhand apr ogram pr oducing thedesirableresul
tson
one/moredataset sneednotbecor rect
.I nordertoact uall
yprovet hataprogram i
sperfect
,
aprocessof“prov i
ng”isnecessarywher einthepr ogram isanalyt
icall
yprovedtobecor r
ect
andinsuchcases, iti
sboundtoy i
eldper fectresul
tsf orall
possiblesetsofdata.

 Ontheotherhand,profi
li
ngorperf
ormancemeasurementist
heprocessofexecutinga
cor
rectpr
ogram ondiffer
entdataset
st omeasur
et heti
meandspacet hati
ttakesto
computet
heresul
ts.Thatsev
eral
dif
fer
entpr
ogr
amsmaydoagi venj
obsatisfact
ori
l
y.

 Thisisthefi
nalstageofal gor i
thm eval
uati
on.Aquest i
ont obeanswer edwhent heprogr
am
i
sr eadyforexecution,(aft
ert healgori
thm hasbeendev ised,madeapr ior
ianalysi
softhat
,
codedi nt
oapr ogram debuggedandcompi l
ed)ishow doweact uall
yev al
uatetheti
me
takenbythepr ogram?Obv iously,t
hetimerequir
edt oreadt heinputdataorgi vetheout
put
shouldnotbet akeni ntoaccount .I
fsomebodyi skey i
ngi nt heinputdat athroughthe
keyboardorifdatai sbeingr eadf r
om aninputdevice,thespeedofoper ati
onisdependent
ont hespeedoft hedev i
ce,butnotont hespeedoft heal gori
thm.So,wehav et oexcl
ude
thatti
mewhi l
eev aluati
ngt hepr ogr
ams

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179323
  Theent ir
eprocedureexpl
ainedaboveiscal l
ed“
prof
ili
ng”
.Howev er,
unfortunately
,theti
mes
prov i
ded bythe system clock ar
e notal way
s dependable.Mostof ten,t heyare only
i
ndi cati
veinnatur
eandshoul dnotbet akenasanaccuratemeasur ement.Especiall
ywhen
thet imedurati
onsinvolv
edar eoft heorderof1-2mi l
l
iseconds,thefi
gur estendt ovary
oftenbet weenoner unandt heother,evenwiththesamepr ogr
am andal lsamei nput
values.

CommonAsy
mpt
oti
cNot
ati
ons

const
ant − Ο(
1)
l
ogar
it
hmi
c − Ο(
logn)
l
i
near − Ο(
n)
nl
ogn − Ο(
nlogn)
quadr
ati
c − n2)
Ο(
cubi
c − n3)
Ο(
pol
ynomi
al − nΟ(1)
ex
ponent
ial − 2Ο(n)

ARRAYS

OneDi
mensi
onal
arr
ay

Arrayisacontainerwhichcanhol dafixnumberofit
emsandtheseitemsshoul dbeoft
hesame
t
ype.Mostoft hedatastructuresmakeuseofarray
st oi
mplementtheiral
gor
ithms.Fol
l
owingare
t
heimpor tantt
ermst ounderstandtheconceptofAr
ray.
 E l
ement−eachi tem stor
edi nanarrayi
scall
edanelement
.
 I ndex−eachl ocati
onofanel ementinanarr
ayhasanumer i
calindex,
whichisusedtoident
if
y
theelement.

Arr
ayRepresent
ati
on
Arr
ayscanbedecl ar
edi
nvar
iousway
sindi
ff
erentl
anguages.Fori
l
lust
rat
ion,l
et'
stakeCar
ray
decl
arat
ion.

Aspertheabovei
ll
ust
rat
ion,f
oll
owi
ngaretheimpor
tantpoint
stobeconsi
der
ed.
 Indexstar
tswi
th0.
 E achel
ementcanbeaccessedv
iai
tsindex
.Forexample,wecanfet
chanelementati
ndex6as
9.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179324
BasicOper ations
 Trav er se−pri
ntallt
hear r
ayelementsonebyone.
 Inser ti
on−Addsanel ementatthegivenindex.
 De letion−Deletesanelementatt hegiv
enindex.
 Se arch−Sear chesanel ementusingthegiveni
ndexorbyt
hev
alue.
 Me rging--twoarrays
 So rtinganarrayinascendingorderordescendi
ngorder

I
nC,whenanarr
ayi
sini
ti
ali
zedwi
thsi
ze,t
heni
tassi
gnsdef
aul
tsv
aluest
oit
sel
ement
sin
f
oll
owi
ngor
der
.

Dat
aTy
pe Def
aul
tVal
ue

bool f
alse

char 0

i
nt 0

f
loat 0.
0

doubl
e 0.
0f

v
oid

wchar
_t 0

TraverseOper ati
on
Tr
av ersi
ngLi nearSt
ructur
es. Tr av
ersi
nga l i
nearstr
uct
uremeans mov ing through it
sequential
ly,nodebynode.Pr ocessi
ngthedataelementofanodemaybecompl ex,butthe
generalpatter
ni sasfoll
ows:..
.Repeatunt
ilt
her
earenomor enodes.Pr
ocesst
hecur
rentnode.

Al
gor
it
hm f
orar
rayTr
aver
sal

St
ep1.Start
St
ep2.[I
NITIALIZATION]SetIl
owerbound
St
ep3.Repeatst eps3t
o4whi l
eI<=upperbound
St
ep4.ApplyprocesstoA[ I
]
St
ep5.SetI=I+1
[
Endl oop]
St
ep6:Exit

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179325
Exampl ePr ogr am t oreadanddi
spl
aynnumber
susinganar
ray
#incl ude<st dio. h>
#incl ude<coni o.h>
i
ntmai n()
{
i
nti,n,arr[20];
clr
scr ();
printf(“\nent ert henumberofelement
sint
hearr
ay:
”);
scanf (“
%d” ,&n) ;
for(i=0; i
<n; i++)
{
Printf( “
\nar r[%d] =“ ,i
);
Scanf (“
%d” ,&ar r[i]
);
}
Printf( “
\nt hear rayelementsar
e”)
;
For (
i=0; i<n; i
++)
Printf( “
\t%d” ,
ar r[i
])
;
return0;
}

Out
put
Ent
erthenumberofel
ementsi
nthear
ray
:5
Arr[
0]=1
Arr[
1]=2
Arr[
2]=3
Arr[
3]=4
Arr[
4]=5
Theelementsi
nthearr
ayare12345

I
nser
ti
onOperat
ion
I
nser
toperati
on i
st oinser
toneormor edata elementsint
o an ar
ray
.Based on t
he
r
equi
rement,
anewel ementcanbeaddedatt
hebegi
nni
ng,end,oranygi
veni
ndexofar
ray
.

Al
gor
it
hm f
ori
nser
ti
ngael
ementt
oanexi
sti
ngar
ray

Step1.Star
t
Step2.Setupper_bound=upper_
bound+1
Step3.SetA[upper_bound]=v
al
Step4.Stop
Example

Dat
a[]
={12,
23,
34,
45,
56,
67,
78,
89,
90,
100}
;

a)Cal
cul
atet
hel
engt
hoft
hear
ray

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179326
 b)Fi
ndt
hel
owerandupper
-bound

c)Showt
hememor
yrepr
esent
ati
onoft
hear
ray

d)I
fthenewdat
ael
ementwi
tht
hev
alue75hast
obei
nser
tedf
indi
tsposi
ti
on

e)I
nser
tthe75andshowt
hememor
yrepr
esent
ati
on

Sol
uti
on:

Lengt
hofthearr
ay=numberoft
heel
ement
s
Lowerbound=0upperbound=9

I
ndex Data[
0] Data[
1] Data[
2] Data[
3] Data[
4] Data[
5] Data[
6] Data[
7] Data[
8] Dat
a[9]
Data
12 23 34 45 56 67 78 89 90 100
val
ue

Af
teri
nser
ti
ngt
he75v
alue

I
ndex Dat
a[0] Dat
a[1] Dat
a[2] Dat
a[3] Dat
a[4] Dat
a[5] Dat
a[6] Dat
a[7] Dat
a[8] Dat
a[9] Dat
a[10]
Data
12 23 34 45 56 67 75 78 89 90 100
val
ue

Al
gor
it
hm f
ori
nser
tanel
ementi
nmi
ddl
eoft
hear
ray

St
ep1.St
art
St
ep2.[
INI
TIALI
ZATI
ON]setI=N
St
ep3.RepeatSt
eps4and5Whi
l
eI>=pos
St
ep4.SetA[I
+1]=A[I]
St
ep5.SetI=I–1
[
Endoft
hel
oop]
St
ep6.SetN=N+1
St
ep7.SetA[
pos]=v
alue
St
ep8.St
op

Exampl
e

I
nit
ial
dat
aar
ray

Data[
0] Data[
1] Data[
2] Data[
3] Data[
4] Data[
5]
45 23 34 12 56 20

Cal
l
ingI
nser
t(Dat
a,3,
100)wi
l
lleadt
othef
oll
owi
ngi
nthear
ray

Dat
a[0] Dat
a[1] Dat
a[2] Dat
a[3] Dat
a[4] Dat
a[5] Dat
a[6]

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179327
 45 23 34 12 56 20 20

Data[
0] Data[
1] Data[
2] Data[
3] Data[
4] Data[
5] Data[
6]
45 23 34 12 56 56 20

Data[
0] Data[
1] Data[
2] Data[
3] Data[
4] Data[
5] Data[
6]
45 23 34 12 12 56 20

Data[
0] Data[1] Data[
2] Dat
a[3] Data[
4] Data[
5] Data[
6]
45 23 34 100 12 56 20
Exampleprogram

#i
nclude<st di
o. h>
#i
nclude<coni o.h>
i
ntmai n()
{
inti, n,num, pos, arr
[10];
clrscr (
) ;
print f(
"\nEnt ert henumberofel ementsi
nthearr
ay:
");
scanf (
"%d" ,&n) ;
for(i
=0; i<n;i
++)
{
printf("\nArr [%d]=: "
,i
);
scanf ("%d",&ar r[i]
);
}
print f(
"\nEnt ert henumbert obei nser
ted:
")
;
scanf (
"%d" ,
&num) ;
print f(
"\nEnt ert hepositi
onatwhi chthenumberhastobeadded:
")
;
scanf (
"%d" ,&pos) ;
for(i
=n; i>=pos; i
--)
{
arr[i+1]=ar r
[i];
}
arr[pos]=num;
n++;
print f(
"\nThear r
ayaf t
erinsert
ion i
s:",
&num);
f
or (
i=0; i
<n;i++)
{
print f("\nAr r[ %d]=%d",i
,
arr[
i]
);
}
getch( );
ret
ur n0;
}
Out
put

Ent
erthenumberofel ementsi
nthear
ray:4
Arr
[0]=1
Arr
[1]=2
Arr
[2]=3
Arr
[3]=4
Ent
erthenumbert obeinser
ted:9
Ent
ertheposit
ionatwhichthenumberhastobeadded:
2
Thearrayaf
terinser
ti
onis

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179328
 Ar
r[
0]=1
Ar
r[
1]=2
Ar
r[
2]=3
Ar
r[
3]=4
Ar
r[
4]=9

Al
gor
it
hm f
orDel
eti
ngal
astEl
ementf
rom anar
ray

1.Star
t
2.Setupper
_bound=upper
_bound-
1
3.Stop

Al
gor
it
hm f
orDel
eti
ngaMi
ddl
eEl
ementf
rom anar
ray

1. [I
NITIALIZATION]setI=pos
2.Repeatst eps3and4whileI<=N–1
3.SetA[I ]=A[I+1]
4.SetI=I+1
[Endoft hel
oop]
5.SetN=N- 1
6.Exit
Example
I
niti
aldataarray
Data[
0] Dat a[1] Data[
2] Data[
3] Data[
4] Data[
5]
45 23 34 12 56 20

Cal
l
ingI
nser
t(Dat
a,2)wi
l
lleadt
othef
oll
owi
ngi
nthear
ray

Dat
a[0] Dat
a[1] Dat
a[2] Dat
a[3] Dat
a[4] Dat
a[5]
45 23 12 12 56 20

Dat
a[0] Dat
a[1] Dat
a[2] Dat
a[3] Dat
a[4] Dat
a[5]
45 23 12 56 56 20

Dat
a[0] Dat
a[1] Dat
a[2] Dat
a[3] Dat
a[4] Dat
a[5]
45 23 12 56 20 20

Dat
a[0] Dat
a[1] Dat
a[2] Dat
a[3] Dat
a[4]
45 23 12 56 20

Exampl
epr
ogr
am t
odel
eteanel
ementf
rom ar
rayatspeci
fi
edposi
ti
on

#i
nclude<st di
o.h>
#def
ineMAX_ SIZE100
i
ntmain()
{
i
ntar
r[MAX_ SIZE];
i
nti,
size,pos;
pr
int
f("Entersi
zeofthear
ray:
");

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179329
scanf
("%d" ,
&size);
pri
ntf
("Enterelementsi
narray:"
);
for
(i
=0; i
<size;i++)
{
scanf
("%d" ,
&arr[i
])
;
}
pri
ntf
("Entertheelementposi
ti
ontodel
ete:
");
scanf
("%d" ,
&pos) ;

i
f(pos<0| |
pos>size)
{
printf(
"I
nv ali
dposit
ion!Pleaseenterposi
ti
onbetween1t
o%d"
,si
ze)
;
}
else
{
for(i
=pos- 1;i
<si
ze-1;i
++)
{
arr[i
]=arr[
i+1];
}
size--;
}
printf(
"\nElementsofarrayafterdel
eteare:"
);
for(i
=0; i
<size;i
++)
{
printf(
"%d\ t
",
arr
[i
])
;
}
return0;
}

Out
put
Entersizeofthearr
ay:5
Enterelementsinarr
ay:1020304050
Entertheelementposit
iontodel
ete:
2
Element sofarr
ayaft
erdelet
eare:10 30 40 50

Mergi
ngoft woarrays
Mergi
ngoft woar r
aysinat hir
dar raymeansf i
rstcopy
ingthecontentsofthef i
rstarr
ay
i
ntothethir
dar r
ayandt hencopy i
ngthecont entsofthesecondarrayint
othet hi
rdarray.Hence
themergedarraycontainsthecontentsoft hef ir
starr
ayf ol
l
owedbyt hecontentsofthesecond
arr
ay.
I
fthearraysareunsor t
ed,thenmer gingthearraysisver
ysimple,asonej ustneedst o
copyt
hecontentsofonear r
ayintoanotherarray .
Butmergingthearray
sisnotat ri
vialt askwhenthetwoarraysaresort
edandt hemer ged
arr
ayalsoneedstobesor t
ed.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179330
 Ar
ray 9 5 8 7 6
1 0 6 9 7 9

Ar
ray 4 8 7 9 1 5 8
2 5 8 6 9 2 8 1

Ar
ray 9 5 8 7 6 4 8 7 9 1 5 8
3 0 6 9 7 9 5 8 6 9 2 8 1
Mer
gingoft
wounsor
tedar
ray
s

I
fwehavetwosort
edarr
aysandt
her
esult
antmergedar
rayandneedst
obeasor
tedone,
t
henthet
askofmer
gingt
hearr
aysbecomeal
i
ttl
edif
fi
cul
t
.
Arr
ay 2 3 4 5 6
1 0 0 0 0 0

Ar
ray 1 2 3 4 5 6 7
2 5 2 1 5 6 2 8

Ar
ray 1 2 2 3 3 4 4 5 5 6 6 7
3 5 0 2 0 1 0 5 0 6 0 2 8
Mer
gingoft
wosor
tedar
ray
s

Themer gedar r
ayisf or
medusi ngt wosor t
edar r
ays.Her ewef i
rstcomparethe1st
elementoft hear ray1withthe1stel
ementoft hearray2,andthenputt hesmal l
erel
ementinthe
mer gedar r
ay.Since20>15, weput15ast hef i
rstel
ementinthemer gedarray.Thencomparethe
2nd elementoft hesecondar r
aywi t
ht he1stel
ementoft he f
irstar
ray,si
nce20< 22,now20i s
storedassecondel ementofthemer gedar r
ayandt heprocesswillconti
nuesunt i
lthemerged
arraywillcomplete.

Passi
ngAr
ray
stoFunct
ions

Passi
ngdat
aval
ues

mai
n() v
oidf
unc(
int
num)

{ {

i
ntar
r[
5]={
1,2,
3,4,
5}; pr
int
f("
%d"
,num)
;

f
unc(
arr
[3]
); }

Passi
ngaddr
esses

mai
n() v
oidf
unc(
int*
num)

{ {

i
ntar
r[
5]={
1,2,
3,4,
5}; pr
int
f("
%d"
,*num)
;

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179331
 f
unc(
&ar
r[
3])
; }

Passi
ngt
heent
ir
ear
ray
main(
) v
oidf
unc(
int
arr
[5]
)

{ {

i
ntar
r[
5]={
1,2,
3,4,
5}; i
nti
;

f
unc(
arr
); f
or(
i=0;
i
<5;
i
++)

} pr
int
f("
%d"
,ar
r[
i]
);

Ti
meCompl
exi
ty
Al
gor
it
hm Av
erageCase Wor
stCase

Access O(
1) O(
1)

Sear
ch O(
n) O(
n)

I
nser
ti
on O(
n) O(
n)

Del
eti
on O(
n) O(
n)

SpaceComplexi
ty
I
narray
,spacecompl
exi
tyf
orwor
stcasei
sO(
n).

Adv
ant
agesofAr ray
 Arrayprovidesthesinglenamef orthegroupofvari
abl
esofthesamet y
petheref
ore,
itis
easytor emembert henameofal l
theelementsofanarray.
 Traver
singanar rayisav erysi
mplepr ocess,
wejustneedtoincrementthebaseaddressof
thearrayinordertov i
siteachel
ementonebyone.
 Anyelementi nthear r
aycanbedi rect
lyaccessedbyusingt
hei ndex.

MemoryAll
ocat
ionoft
hear r
ay
Aswehavementioned,al
lthedat
aelementsofanarr
ayar estoredatconti
guouslocati
ons
i
nthemainmemor y
.Thenameoft hear
rayr
epresent
sthebaseaddr essortheaddressoffi
rst
el
ementint
hemainmemor y.Eachelementoft
hear r
ayisr
epresentedbyapr operi
ndexing.

Thei
ndexi
ngoft
hear
raycanbedef
inedi
nthr
eeway
s.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179332
 0(
zer
o-basedi ndexing):
Thef i
rstelementofthearraywi
llbearr[0]
.
1(
one-basedindexing):Thefi
rstelementofthearraywil
lbearr[1].
n(
n-basedindexing):Thefi
rstelementofthearraycanresideatanyrandom i
ndexnumber
.

wehaveshownthememor yal
locat
ionofanarr
ayar rofsi
ze5.Thear
rayfoll
ows0-basedi
ndexing
appr
oach.Thebaseaddressofthearrayi
s100thbyte.Thi
swill
betheaddressofarr
[0]
.Her
e,the
si
zeofinti
s4bytesther
eforeeachelementwil
ltake4by t
esinthememory.

I
n0basedindexi
ng,i
ft hesi
zeofanarr
ayi
snthenthemaxi
mum i
ndexnumber
,anel
ementcan
hav
eisn-
1.Howev er
,itwil
lbenifweuse1basedi
ndexi
ng.

Accessi
ngElementsofanarray
Toaccessanyrandom elementofanar rayweneedthefol
l
owinginf
ormati
on:
 BaseAddressofthearray.
 Sizeofanelementinbytes.
 Whichtypeofindexi
ng,arrayfol
l
ows?
Addressofanyel
ementofa1Dar r
aycanbecalcul
atedbyusi
ngthefol
lowi
ngfor
mul
a:

Byteaddr
essofel
ementA[
i]=baseaddr
ess+si
ze*(i
-fi
rsti
ndex)
Example:

Inanarray,A[-
10....
.+2] ,
Baseaddr ess(BA)=999, sizeofanelement=2by t
es,
fi
ndthelocat i
onofA[ -
1].
L(A[
-1]
)=999+[ (-
1)-( -
10) ]x2
=999+18
=1017
Memor yAl l
ocati
onPr ocess
Gl obalvar
iables,stati
cv ari
ablesandpr ogram instr
ucti
onsgetthei
rmemor yi
npermanent
stor
agear eawher easlocal vari
ablesarestoredinamemor yareacal
l
edStack.
Thememor yspacebet weent hesetwor egionsisknownasHeapmemor y.Thi
sregioni
s
usedfordy namicmemor yal l
ocati
ondur ingexecut i
onoftheprogram.Thesizeofheapkeeps
changi
ng.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179333
DynamicMemor yAll
ocation
Theprocessofallocat
ingmemoryatrunt
imei sknownasdynamicmemor yal
locati
on.
Li
brar
yrout
inesknownasmemor ymanagementfuncti
onsareusedforal
locati
ngandf r
eeing
memoryduringexecuti
onofapr ogr
am.Thesefuncti
onsaredefi
nedinstdli
b.hheaderfi
le.
Functi
o
Descri
pti
on
n
mall
oc al l
ocatesrequest
edsizeofby
tesandr
eturnsav oi
dpoi
nterpoi
nti
ngtothef
irstby
teof
(
) theall
ocatedspace
all
ocatesspaceforanarr
ayofel
ements,i
nit
ial
i
zethem t
ozeroandthenret
urnsav oi
d
cal
loc()
point
ertothememor y

f
ree(
) r
eleasespr
evi
ousl
yal
l
ocat
edmemor
y

r
eall
oc
modi
fyt
hesi
zeofpr
evi
ousl
yal
l
ocat
edspace
(
)

Let
’sunder
standt
hedi
ff
erencebet
weenst
ati
cmemor
yal
l
ocat
ionanddy
nami
cmemor
yal
l
ocat
ion.

St
ati
cmemor
yal
l
ocat
ion Dy
nami
cmemor
yal
l
ocat
ion

Memor
yisal
l
ocat
edatcompi
l
eti
me. Memor
yisal
l
ocat
edatr
unt
ime.

Memorycan'
tbei
ncr
easedwhi
l
eexecut
ing Memorycanbei
ncr
easedwhi
l
eexecut
ing
pr
ogr
am. pr
ogr
am.

usedi
nar
ray
. usedi
nli
nkedl
i
st.

Mal
l
oc(
)funct
ion
 Themal
l
oc(
)funct
ional
l
ocat
essi
ngl
ebl
ockofr
equest
edmemor
y.
 I
tdoesn'
ti
nit
ial
i
zememor
yatexecut
iont
ime,
soi
thasgar
bagev
aluei
nit
ial
l
y.
 I
tret
urnsNULLi
fmemor
yisnotsuf
fi
cient
.

Thesy
ntaxofmal
l
oc(
)funct
ioni
s:-
pt
r=(
cast
-t
ype*
)mal
l
oc(
byt
e-si
ze)
(
or)

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179334
 v
oid*mal
l
oc(
byt
e-si
ze)
mal
l
oc(
)funct
ioni
susedf
oral
l
ocat
ingbl
ockofmemor
yatr
unt
ime.Thi
sfunct
ionr
eser
vesabl
ock
ofmemor
yoft
hegi
vensi
zeandr
etur
nsapoi
nteroft
ypev
oid.Thi
smeanst
hatwecanassi
gni
tto
anyt
ypeofpoi
nterusi
ngt
ypecast
ing.I
fitf
ail
stoal
l
ocat
eenoughspaceasspeci
fi
ed,
itr
etur
nsa
NULLpoi
nter
.

Exampl
eOfMal
l
oc(
)Funct
ion.

#include<st dio.h>
#include<st dlib.h>
intmai n()
{
intn,i,*ptr,
sum=0;
clrscr ()
;
print f("
Ent ernumberofel ements:");
scanf ("
%d" ,
&n) ;
ptr=( int*)
mal l
oc( n*sizeof(int
));//memor yallocat
edusingmal
l
oc
if(
pt r==NULL)
{
pri
ntf("Sor ry!unabl etoallocatememor y")
;
exit
(0) ;
}
print f("
Ent erel ement sofar r
ay:")
;
for(i=0;i<n;++i )
{
scanf ("
%d" ,
ptr+i)
;
sum+=* (
pt r
+i);
}
print f("
Sum=%d" ,
sum) ;
free( ptr);
get ch( )
;
return0;
}
Output
:
Enterel ement sofar ray:3
Enterel ement sofar ray:10
10
10
Sum=30
cal
l
oc()funct ion
 Thecal l
oc( )f unctional l
ocatesmul t
ipleblockofrequest
edmemor
y.
 I tini ti
all
yi niti
alizeal lbytestozero.
 I tr eturnsNULLi fmemor yi
snotsuf f
icient.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179335
Thesy
ntaxofcal
l
oc(
)funct
ionis:
ptr
=(cast
-t
ype*
)cal
l
oc(
number
,by
te-
size)
(
or)
v
oid*
cal
l
oc(
numberofi
tems,
element
-si
ze)
calloc()isanothermemor yal
locat
ionfunct
iont
hatisusedforall
ocati
ngmemoryatrunt
ime.cal
l
oc
functionisnormal l
yusedforall
ocati
ngmemor ytoderi
veddatatypessuchasarr
aysand
structures.I
fitfai
lstoal
locat
eenoughspaceasspecified,
itr
eturnsaNULLpointer
.

Let
'sseet heexampl eofcal loc()functi
on.
#include<st dio.h>
#include<st dli
b.h>
intmai n(){
i
ntn, i,
*ptr,sum=0;
clrscr (
);
pr i
ntf("Ent ernumberofel ement s:"
);
scanf (
"%d" ,
&n);
pt r=(i
nt* )call
oc(n,sizeof(i
nt)
);//memoryal
l
ocat
edusi
ngcal
l
oc
if(ptr==NULL)
{
printf("Sorry!unabl etoall
ocatememory"
);
exit(
0) ;
}
pr i
ntf("Ent erelement sofar ray
:");
for (i
=0;i<n;++i)
{
scanf ("
%d" ,
ptr+i);
sum+=* (ptr
+i);
}
pr i
ntf("Sum=%d" ,
sum) ;
free(pt r);
get ch();
return0;
}
Output
:
Enterel ement sofar ray :3
Enterel ement sofar ray :10
20
30
Sum=60

r
eal
loc()f
uncti
on
I
fmemor yisnotsuf
fi
cientformall
oc()orcal
l
oc(
),y
oucanreal
l
ocat
ethememor
ybyr
eal
l
oc(
)
f
uncti
on.Inshor
twecansayt hat,
itchangesthememorysize.

Let
'sseet
hesy
ntaxofr
eal
l
oc(
)funct
ion.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179336
 pt
r=r
eal
l
oc(
ptr
,new-
size)
(
or)
v
oid*r
eal
l
oc(
poi
nter
,new-
size)

Examplef or: r
ealloc(
)
i
nt* x;
x=( int*
)mal l
oc(50*sizeof(i
nt))
;
x=( int*
)reall
oc(x,
100);/ /
all
ocatedanewmemor ytovari
abl
ex
free(
)function
Thememor yoccupiedbymal loc()orcal
l
oc()functi
onsmustberel
easedbycal
l
ingf
ree(
)
functi
on.Ot herwise,i
twillconsumememor yuntil
program exi
t.

Sy
ntaxoff
ree(
)funct
ion.
f
ree(
ptr
)

Di
ff
rencebet
weenmal
l
oc(
)andcal
l
oc(
)

Cal
l
oc(
) Mal
l
oc(
)
1.call
oc(
)ini
ti
ali
zest
heal
locat
edmemor
ywi
th 1.Malloc()ini
ti
ali
zest
heal
l
ocat
edmemor
ywi
th
0value. garbagevalues.
2.Numberofargumentsi
s2 2.Numberofar gumenti
s1

Synt
ax:(cast_
type*
)cal
l
oc(
blocks, Sy
ntax:(
cast
_ty
pe*
)mal
l
oc(
Size_
in_
byt
es)
;
si
ze_of
_block)
;

Passi
ngarraytothefuncti
on:
Aswehav ementionedear
li
erthat
, t
henameoft hear
rayr
epr
esent
sthest
art
ingaddressor
theaddr
essoft hefi
rstel
ementofthearray.Al
ltheel
ementsoft
hearr
aycanbetr
aversedbyusing
thebaseaddress.

Exampl
e:
#include<stdio.
h>
i
ntsummat i
on(i
nt [
])
;
voidmai n()
{
intarr[
5]={ 0,
1,2,
3,4};
intsum =summat i
on(arr
);
printf
("%d",
sum) ;
}
i
ntsummat i
on( i
ntarr[
])
{
intsum=0, i
;
for(i=0; i
<5;i++)
{
sum =sum +ar r
[i
];

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179337
 }
r
etur
nsum;
}
Theaboveprogram def
inesafunct
ionnamedassummat
ionwhi
chaccept
sanarr
ayasan
ar
gument
.Thefunct
ioncalcul
atest
hesum ofallt
heel
ement
softhear
rayandr
etur
nsi
t.

TwoDimensi onalAr
rays
2Dar r
aycanbedef i
nedasanar rayofar
ray
s.The2Darrayisorgani
zedasmatri
ceswhich
canberepresentedasthecol
lecti
onofrowsandcolumns.
Howev er,2Darr
aysarecreatedt
oimplementarel
ati
onaldatabasel
ookal
ikedat
astr
ucture.
Itpr
ovi
deseaseofhol di
ngbulkofdataatoncewhichcanbepassedt oanynumberoff
unct
ions
wherev
errequired.

Howtodecl
are2DArray
Thesynt
axofdecl
ari
ngtwodi
mensi
onalar
rayisv
erymuchsimi
lartot
hatofaonedi
mensi
onal
arr
ay.
i
ntarr
[max_r
ows][
max_col
umns];

Thetwodimensionalar
ray,t
heelementsareorgani
zedi
nt hef
orm ofr
owsandcol
umns.
Fir
stel
ementofthefi
rstrowisrepr
esentedbya[0]
[0]wher
ethenumbershowninthef
ir
sti
ndexi
s
thenumberoft
hatrowwhi l
ethenumbershowni nthesecondindexi
sthenumberoft
hecol
umn.

Howdoweaccessdat ai
na2Dar ray
Theelementsof2Dar r
ayscanber andom accessed.Si
mi l
artoonedimensi
onal
arrays,
we
canaccesst
heindivi
dualcel
lsina2Darraybyusingt heindi
cesofthecell
s.Ther
earetwoindi
ces
att
achedtoapart
icul
arcell
,oneisit
srownumberwhi let
heot heri
sitscol
umnnumber.

Howev
er,
wecanst
oret
heval
uest
oredi
nanypar
ti
cul
arcel
lofa2Dar
rayt
osomev
ari
abl
exby
usi
ngt
hefol
l
owi
ngsynt
ax.

i
ntx=a[
i]
[j
];
wher
eiandj
ist
her
owandcol
umnnumberoft
hecel
lrespect
ivel
y.

Exampl
e:
f
or(i
nti
=0;
i<n;
i
++)
{

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179338
 f
or(intj
=0;
j<n;
j++)
{
a[
i]
[j
]=0;
}
}
Weknowt hat,whenwedeclar
eandini
ti
ali
zeonedi
mensi
onalarr
ayi
nCprogr
ammi ng
si
multaneousl
y,wedon'
tneedtospeci
fythesi
zeoft
hear
ray.Howev
erthi
swi
llnotworkwi
th2D
ar
ray
s.Wewi l
lhavet
odefi
neatleastt
heseconddi
mensi
onofthear
ray
.

Thesy
ntaxt
odecl
areandi
nit
ial
i
zet
he2Dar
rayi
s
i
ntar
r[
2][
2]={
0,1,
2,
3};
Thenumberofel
ementst
hatcanbepr
esenti
na2Dar
raywi
l
lal
way
sbeequal
to(
numberofr
ows
*numberofcol
umns)
.

Exampl
e:St
ori
ngUser
'sdat
aint
oa2Dar
rayandpr
int
ingi
t.

#incl ude<st dio.

h>
voidmai n()
{
i
ntar r[
3] [
3],
i,
j;
clr
scr (
);
for( i
=0; i
<3;i
++)
{
for( j
=0; j
<3;j
++)
{
printf("Entera[%d][
%d]:
",i
,
j);
scanf (
"%d" ,
&arr[
i]
[j
])
;
}
}
printf("\nprinti
ngtheel
ement s.
..
.\
n")
;
for(i=0;i<3;
i++)
{
printf("\n")
;
for( j
=0; j
<3;j
++)
{
printf("%d\ t
",
arr[
i]
[j
])
;
get ch();
}
}
}

Mappi
ng2Dar
rayt
o1Dar
ray

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179339
 Wheni tcomest omapa2di mensi onalarr
ay,mostofusmi ghtthi
nkthatwhythismapping
i
sr equi
red.Howev er,2Dar ray sexi stsf r
om theuserpointofv i
ew.2Dar r
aysarecreat
edt o
i
mpl ementar elat
ional databaset abl elookali
kedatastructure, i
ncomputermemor y,t
hest or
age
techni
quef or2Dar rayissi milart ot hatofanonedi mensi onal arr
ay.
Thesizeofat wodi mensi onal arrayisequaltothemul t
ipli
cati
onofnumberofr owsandt he
numberofcol umnspr esenti nt hear r
ay.Wedoneedt omapt wodi mensi
onalarr
aytotheone
dimensionalarrayinor dertost or et hem inthememor y.
A3X3t wodi mensional arrayi sshowni nthefoll
owi ngi mage.However,t
hisarrayneedsto
bemappedt oaonedi mensi onal arrayinor dert
ostoreitintot hememor y.

Ther
ear
etwomai
ntechni
quesofst
ori
ng2Dar
rayel
ement
sint
omemor
y

1.Rowmaj ororder
ing
Inrowmaj oror
deri
ng,
all
t her
owsoft
he2Darrayar
estoredi
ntothememorycont
iguousl
y.
Consideri
ngt hearr
ayshownintheabov
eimage,
itsmemoryal
locat
ionaccor
dingt
orowmajor
orderis.

Fi
rst
,the1str
owofthear
rayi
sstor
edint
othememorycompl
etel
y,t
hent
he2ndr
owoft
he
ar
rayi
sstoredint
othememorycompl
etel
yandsoonti
l
lthel
astr
ow.

2.Col
umnmaj oror
der i
ng
Accor
dingtothecolumnmaj
ororder
ing,
allt
hecol
umnsoft
he2Dar
rayar
est
oredi
ntot
he
memoryconti
guousl
y .Thememor
yall
ocati
onofthear
rayi
s.

Fir
st,
the1stcol
umnofthear
rayi
sstoredintot
hememorycompl
etel
y,andt
henthe2nd
r
owofthearr
ayisstor
edi
ntot
hememor ycompletel
yandsoonti
l
lthel
astcol
umnofthearr
ay.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179340
APPLI
CATIONOFARRAYS
 Arraysar
ewi
del
yusedt
oimpl
ementmat
hemat
ical
vect
ors,
mat
ri
ces,
andot
herki
ndsof
r
ect
angul
art
abl
es.
 Manydat
abasesi
ncl
udeone-
dimensi
onal
arr
ayswhoseel
ement
sar
erecor
ds.
 Ar
ray
sar
eal
sousedt
oimpl
ementot
herdat
ast
ruct
uressuchasst
ri
ngs,
stacks,
queues,
heaps,
andhasht
abl
es.Wewi
l
lreadaboutt
hesedat
ast
ruct
uresi
nthesubsequentchapt
ers.
 Ar
ray
scanbeusedf
orsor
ti
ngel
ement
sinascendi
ngordescendi
ngor
der
.

St
ructure
Astr
uctur
eisacompositedat
aty
pet
hatdefi
nesagroupedl
istofv
ari
abl
esthataret
obe
pl
acedunderonenamei nablockofmemor
y.I
tal
lowsdif
fer
entvar
iabl
estobeaccessedbyusi
ng
asingl
epointert
othest
ruct
ure.

Sy
ntax
st
ructst
ruct
ure_
name
{
dat
a_t
ypemember1;
dat
a_t
ypemember2;
.
.
.
.

data_t
ypememeber ;
};
Let
'sseetheexampl etodef
ineast
ruct
uref
oranent
it
yempl
oyee.
str
uctempl oyee
{
i
ntid;
charname[ 10]
;
fl
oatsalary
;
};

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179341
Her
e,st
ructi
sthekeywor
d;employ
eei
sthenameoft
hest
ruct
ure;
id,
name,
andsal
aryar
ethe
membersorfi
eldsoft
hestr
uct
ure.

Adv
ant
ages
 Itcanhol
dv ari
ablesofdi
ff
erentdat
at y
pes.
 Wecancr eateobject
scontai
ningdi
ffer
enttypesofatt
ri
butes.
 Ital
lowsustor e-
usethedatalay
outacrossprogr
ams.
 Iti
susedtoi mplementot
herdatastr
ucturesli
keli
nkedli
sts,st
acks,
queues,
trees,
graphs
etc.

Exampl eprogr am
#include<stdio.
h>
#include<conio.h>
voidmai n()
{
structempl oyee
{
i
nti d;
fl
oatsal ary;
i
ntmobi le;
};
structempl oyeee1,e2,
e3;
cl
rscr (
);
printf(
"\nEnterids,sal
ary&mobi leno.of3employee\
n")
;
scanf( "
%d%f%d" ,
&e1.i
d,&e1.sal
ary,&e1.
mobi
le);
scanf( "
%d%f%d" ,&e2.
id,&e2.
salary,
&e2.mobi
l
e);
scanf( "
%d%f%d" ,
&e3.i
d,&e3.sal
ary,&e3.
mobi
le);
printf(
"\nEnteredResul t"
);

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179342
 printf("
\n%d%f%d" ,e1.i
d,e1.sal
ary,e1.
mobil
e);
printf("
\n%d%f%d" ,e2.
id,e2.
salar
y,e2.mobil
e);
printf("
\n%d%f%d" ,e3.i
d,e3.sal
ary,e3.
mobil
e);
get ch()
;
}
Union
Likest r
uct ure,
Unioninclanguagei sauser-
defi
neddat
atypethatisusedtostoret
he
diff
erentty peofel ements.
Atonce, onlyonememberoft heunioncanoccupythememor y.I
notherwords,wecansay
thatthesi zeoft heunioninanyinstanceisequaltothesi
zeofi
tslar
gestelement
.

Advant
ageofuni onoverst
ruct
ure
I
toccupieslessmemor ybecausei
toccupi
esthesi
zeoft
helar
gestmemberonl
y.
Di
sadvantageofunionoverstr
uctur
e
Onlythelastent
ereddatacanbestor
edintheuni
on.I
tov
erwri
test
hedat
aprevi
ousl
yst
ored
i
ntheunion.

Uni
onexampl
e

#incl ude<st dio.h>

#incl ude<st ri
ng. h>
unionempl oyee
{i nti d;
charname[ 50] ;
}e1;/ /
decl ari
nge1v ari
ableforuni on
intmai n()
{
//stor efir
stempl oy eeinf
ormat ion
e1.id=101;
strcpy (e1.name, "Superstar")
;//copyingstr
ingi
ntocharar
ray
//pr i
ntingf i
rstempl oyeeinformat i
on
printf("empl oyee1i d: %d\n",e1.id);
printf("empl oyee1name: %s\ n",e1.name);
return0;
}
Out
put
:
empl oyee1i d:1869508435
empl oyee1name: Superstar

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179343
Sor t
ing
Sortingreferstotheoper ati
onort echniqueofar r
angi ngandr earrangingset sofdat ain
somespeci fi
corder.Acol l
ectionofrecordscal ledal i
stwher eeveryrecordhasoneormor ef i
elds.
Thef ieldswhi chcont ai
nauni quev al
uef oreachr ecordi stermedast hekeyf i
eld.
Forexampl e,aphonenumberdi rectorycanbet houghtofasal i
stwher eeachr ecordhas
threef i
elds-'name' oftheper son,'
address' ofthatper son,andt heir'
phonenumber s'
.Beingunique
phonenumbercanwor kasakeyt olocateanyr ecor dinthel ist.
Sortingistheoper ati
onper f
ormedt oar ranget her ecordsofat ableorl i
sti nsomeor der
accor dingt osomespeci ficorderi
ngcr i
teri
on.Sor ti
ngi sper formedaccor dingt osomekeyv alueof
eachr ecor d.
Ther ecordsar eeit
hersor t
edeithernumer i
callyoral phanumer i
cally.Ther ecordsar ethen
arrangedi nascendi ngordescendi ngor derdependi ngont henumer i
calvalueoft hekey .Her eisan
exampl e, wheret hesorti
ngofal i
stsofmar ksobt ainedbyast udentinanypar ticularsubjectofa
class.

Cat
egor
iesofSor
ti
ng

Thet
echni
quesofsor
ti
ngcanbedi
vi
dedi
ntot
wocat
egor
ies.

 I
nter
nalSor
ti
ng
 Ext
ernal
Sort
ing

I
nter
nalSor
ti
ng:Ifal
lthedat
athati
stobesor
tedcanbeadj
ust
edatat
imei
nthemai
nmemor
y,
t
heinter
nal
sort
ingmet hodi
sbeingper
for
med.

Exter
nal Sort
ing:
Whent hedatat
hati
stobesort
edcannotbeaccommodatedinthememoryatthe
samet i
meandsomehast obekepti
nauxi
li
arymemorysuchasharddi
sk,
floppydisk,
magnet
ic
tapesetc,thenexter
nal
sorti
ngmethodsar
eperfor
med.

Thecompl exityoft hesor ti

ngal gori
thms
Thecompl exityofsor t
ingalgorit
hm calcul atesther unni ngt i
meofaf uncti
oni nwhi ch' n'
numberofi temsar etobesor ted.Thechoicef orwhi chsor tingmet hodissuit
ableforapr obl em
dependsonsev eral dependencyconf i
gurati
onsf ordi f
ferentpr obl ems.Themostnot eworthyof
theseconsiderationsar e:
 Thel engthoft imespentbyt heprogrammeri npr ogrammi ngaspeci
fi
csor ti
ngpr ogram
 Amountofmachi netimenecessar yforr unningt hepr ogr am
 Theamountofmemor ynecessar yforrunni ngthepr ogram
TheEf f
ici
encyofSor t
ingTechni ques
Togett heamountoft imer equir
edt osor tanar rayof' n' element
sbyapar t
icularmet hod,
thenormal approachi stoanal yzethemet hodt of i
ndt henumberofcompar i
sons( orexchanges)
requir
edbyi t.Mostoft hesor t
ingtechniquesar edat asensi tive, andsothemet r
icsf orthem
dependsont heor derinwhi cht heyappearinani nputar ray.
Varioussorti
ngt echni quesar eanalyzedinv ar
iouscasesandnamedt hesecasesar e:

 Bestcase

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179344
  Wor
stcase

 Av eragecase
Hence, ther esul tofthesecasesi softenaf or
mul agivi
ngt heav er
agetimer equiredforaparticul
ar
sor tofsize'n. 'Mostoft hesor tmet hodshav eti
mer equirement sthatrangef rom O( nl
ogn)to
2
O(n) .
Ty pesofSor tingTechni ques
 Bubbl eSor t
 Sel ect i
onSor t
 Inser tionSor t
 Mer geSor t
 Qui ckSor t
 HeapSor t
 Radi xSor t
Qui ckSor tAl gorit
hm
Quicksor tisaf astsor tingalgori
thm usedtosor tal i
stofelement s.Quicksor talgor
it
hm is
i
nv entedbyC.A.R.Hoar e.
Thequi cksor talgor it
hm attempt stoseparatethelistofelement sintot wopar t
sandt hen
sor teachpar trecursively .Thatmeansi tusedivideandconquerst rat
egy .Inqui cksort,
the
par ti
ti
onoft helistisper for medbasedont heelementcal ledpivot.Her
epi votel ementisoneoft he
element si nt helist.
Thel i
sti sdi v
idedi ntotwopar ti
ti
onssucht hat"all
el ementstothel eftofpi v
otaresmal ler
thant hepi votandal lelement stotherightofpivotaregreat ert
hanorequal tot hepivot"
.

St
epbyStepPr
ocess/Algor
ithm
I
nQuicksor
tal
gor
ithm,part
it
ioni
ngoft
hel
i
sti
sper
for
medusi
ngf
oll
owi
ngst
eps.
..

St
ep1-Considerthefir
stel ementoft helistaspi vot(i.
e.,
Elementatf
ir
stposi
ti
oni
ntheli
st).
St
ep2-Definetwov ari
ablesi andj.Seti andj tofi
r standlastel
ementsoft
heli
str
espect
ivel
y.
Step3-I
ncrementi unti
lli
st [
i]>pivotthenstop.
St
ep4-Decrementj unti
llist[
j]<pivotthenstop.
St
ep5-Ifi<jthenexchangel ist
[i
]andl i
st[
j]
.
St
ep6-Repeatsteps3,4&5unt ili>j.
St
ep7-Exchanget hepivotelementwi thli
st[
j]element .

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179345
L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179346
Compl
exi
tyoft
heQui
ckSor
tAl
gor
it
hm

Tosortanunsor
tedl
i
stwi t
h'n'
numberofel
ements,
weneedtomake((n-
1)+(n-
2)+(n-
3)+..
..
..
+1)
=(n(n-
1))/
2numberofcomparisonsi
nthewor
stcase.I
fthel
i
sti
sal
readysor
ted,t
heni
trequi
res
'
n'numberofcompar
isons.

WorstCase :O( n2)

BestCase : O(
nlogn)
AverageCase :O(nl
ogn)

Exampl
ePr
ogr
am f
orQui
ckSor
t

#include<st dio.h>
#include<coni o.h>
voidqui ckSor t(int[10],int,
int);
voidmai n()
{
i
ntl ist[20],size,i;
printf("Ent ersi zeoft hel ist:")
;
scanf ("%d" ,
&si ze);
printf("Ent er%di ntegerv alues:"
,si
ze)
;
for(i =0; i<si ze; i++)
scanf ("%d",&list[i]
);
quickSor t(li
st,0,size-1) ;
printf("Listaf tersor tingi s:")
;
for(i =0; i<si ze; i++)
print f(
"%d" ,l
ist[i
]);
get ch();
}
voidqui ckSor t(intlist
[10] ,
intfir
st,
i
ntlast
){
intpi vot ,
i,
j,
temp;
i
f( fi
rst<l ast )
{
pivot=f i
rst ;
i=f ir
st ;
j=l ast;
whi l
e(i <j)
{
whi le(li
st [
i]<=l ist[
pivot]&&i <l
ast)
i
++;
whi le(li
st [
j]>list [
pivot])
j
--;
if(i<j)
{
temp=l i
st[i
];
list[i
]=l ist[
j];

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179347
 l
i
st[
j]=t
emp;
}
}
temp=l ist
[pi
vot];
l
ist[
pivot]=li
st[
j]
;
l
ist[
j]=temp;
quickSort(
li
st,
fi
rst
,j-
1);
quickSort(
li
st,
j
+1,last
);
}
}
OutPut
Ent
ert
hesizeoft heli
st:
8
Ent
ert
he8I ntegerval
ues:53814627
Li
staf
tersort
ingis:12345678

Mer geSor tAlgori

thm
MergeSor tfol
lowst her uleofDivideandConquert osor tagivensetofnumber s/elements,
recursivel
y,henceconsumi ngl esstime.
I
nthel asttwotutorials,welearnedaboutSel ectionSor tandInsertionSort,
bot
hofwhi ch
haveawor st-caserunningt imeofO( n2).Ast hesizeofi nputgrows, i
nsertionandsel
ectionsort
cant akeal ongt i
met orun.
Mergesor t,
ont heot herhand, r
unsi nO( n*l
ogn)t i
meinal lt
hecases.
Divi
deandConquer
I
fwecanbr eakasi ngl ebigproblem intosmallersub-problems, sol
v ethesmal
lersub-
problemsandcombi netheirsol uti
onstof i
ndt hesoluti
onf ortheorigi
nal bigprobl
em,itbecomes
easiertosol vethewhol epr oblem.

InMergeSor t
,thegivenunsor
tedarraywi
thnelementsi
sdivi
dedintonsubarr
ays,eachhav
ing
oneelement,becauseasingleelementi
salwayssor
tedi
nitsel
f.Then,
itr
epeat
edlymergesthese
subarrays,
topr oducenewsortedsubarr
ays,andi
ntheend,onecomplet
esortedarr
ayis
produced.

TheconceptofDi
vi
deandConqueri
nvol
vest
hreest
eps:

 Di
videtheprobl
em int
omul ti
plesmallprobl
ems.
 Conquerthesubprobl
emsbysol v
ingthem.Thei deaist
obreakdownthepr
oblem i
nto
at
omicsubpr obl
ems, wheretheyareactual
lysolved.
 Combinethesolut
ionsofthesubpr obl
emst ofindthesol
uti
onoftheact
ual
probl
em.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179348
HowMer geSortWorks?
Aswehav ealreadydi
scussedthatmergesortuti
li
zesdivi
de-
and-conquerrul
et obr
eakt
he
pr
obl
em intosub-
problems,theprobl
em inthi
scasebeing,sor
ti
ngagi v
enar r
ay .
I
nmer gesort,
webr eakthegiv
enar r
aymi dway
,forexampleift
heor i
ginalar
rayhad6
el
ements,t
henmer gesortwill
breaki
tdowni ntotwosubarray
swi t
h3el ementseach.

Butbreaki
ngt heori
ginal arr
ayinto2smal lersubar raysisnothel pi
ngusinsor
ti
ngthear ray.
Sowewi llbr
eakt hesesubar raysintoev ensmal l
ersubar rays,
unti
lwehavemul t
iplesub
arr
ayswi t
hsingleelementi nthem.Now, theideaher eisthatanar r
aywithasi
ngleelementi s
al
readysorted,sooncewebr eaktheorigi
nal ar
r ayintosubar rayswhichhasonlyasingl
eel ement
,
wehav esuccessful
lybrokendownourpr oblem i ntobasepr oblems.
Andthenwehav et omer geallt
hesesor tedsubar rays,stepbysteptof
orm onesingle
sort
edar r
ay.
Let'
sconsideranarraywi thvalues{14,7,3,12, 9, 11,6,and12}

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179349
I
nmer
gesor
twef
oll
owt
hef
oll
owi
ngst
eps:

 Wet akeav ari

abl epandst orethestart
ingindexofourar r
ayinthi
s.Andwet akeanot her
vari
abl erandst or ethelasti
ndexofar r
ayi nit
.
 Thenwef indt hemi ddleofthearrayusingthef ormul
a(p+r )
/2andmar kthemi ddl
ei ndex
asq, andbr eakt hear r
ayintotwosubar rays,fr
om ptoqandf rom q+1t orindex.
 Thenwedi v i
det hese2subar raysagain,justl
ikewedividedourmainarrayandt hi
s
continues.
 Oncewehav edi vi
dedt hemainarrayintosubar rayswit
hsingl
eelements,thenwest art
mer gingt hesubar rays.
Exampl epr ogr am
#include<st dio.h>
voidmer geSor t(i
nt[]
,i
nt,
int
);

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179350
 v
oi dmer ge( int[]
,i
nt,
int ,
int)
;
v
oi dmai n( )
{
i
nta[ 10] ={ 10, 9,7, 101, 23,44,12,
78,34,23}
;
i
nti ;
clr
scr ();
mer geSor t(a,0,
9);
pri
nt f("printingthesor tedelements")
;
for(i
=0; i<10; i
++)
{
printf("\n%d\ n",a[i
]);
}
getch( );
}
v
oi dmer geSor t(i
nta[ ]
, i
ntbeg, i
ntend)
{
i
ntmi d;
i
f(beg<end)
{
mi d=( beg+end) /2;
mer geSor t(
a,beg, mid);
mer geSor t(
a,mi d+1,end) ;
mer ge( a,beg,mi d,end);
}
}
v
oi dmer ge( inta[],i
ntbeg, intmid,i
ntend)
{
i
nti =beg, j=mi d+1,k,index=beg;
i
ntt emp[ 10] ;
whi l
e( i
<=mi d&&j <=end)
{
if(a[i
]<a[ j]
)
{
temp[ index]=a[ i]
;
i=i +1;
}
else
{
temp[ index]=a[ j]
;
j=j +1;
}
index++;
}
i
f(i
>mi d)
{
whi le(j<=end)

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179351
 {
t
emp[index]=a[
j]
;
i
ndex++;
j
++;
}
}
el
se
{
whi l
e(i<=mi d)
{
temp[ index]=a[
i]
;
index++;
i++;
}
}
k=beg;
whil
e( k<index)
{
a[k]=temp[ k];
k++;
}
}
Output:
Pri
nti
ngthesort
edel ements
7
9
10
12
23
23
34
44
78
101
HeapSortAlgori
thm
Heapsor ti
soneofthesortingalgor
it
hmsusedt oar
rangealistofelementsinor
der.
Heapsor
talgori
thm usesoneofthet r
eeconcept
scall
edHeapTr ee.Inthi
ssorti
ngalgor
it
hm, we
useMaxHeapt oarr
angeli
stofelementsinDescendi
ngorderandMi nHeapt oarr
angeli
st
el
ementsinAscendingorder.

St
epbySt
epPr
ocess/Al
gor
it
hm

St
ep1-ConstructaBinar
yTreewi t
hgivenl
i
stofElements.
St
ep2-Transf
or mtheBinar
yTreeintoMinHeap.
St
ep3-Delet
et herootel
ementfrom MinHeapusingHeapi
fymet
hod.
St
ep4-Putthedeletedel
ementintotheSort
edli
st.

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179352
St
ep5-Repeatt
hesameunti
lMi
nHeapbecomesempt
y.
St
ep6-Displ
ayt
hesort
edl
ist
.

Exampl
ePr
obl
em

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179353
L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179354
Compl
exi
tyoft
heHeapSor
tAl
gor
it
hm

Tosor
tanunsor
tedl
i
stwi
th'
n'numberofel
ement
s,f
oll
owi
ngar
ethecompl
exi
ti
es.
..

WorstCase :O(
nlogn)
BestCase : O(
nlogn)
AverageCase :
O(nlogn)

Exampl
epr ogram
#include<stdio.h>
i
ntt emp;
voidheapi fy(
intarr
[]
, i
ntsi
ze,i
nti)
{
i
ntlar gest=i;
i
ntlef t=2* i+1;
i
ntr i
ght=2* i+2;
i
f( l
ef t<size&&ar r[
left
]>ar
r[
lar
gest]
)
L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179355
 largest=l ef t;
if(right<si ze&&ar r [
ri
ght ]>arr[
largest]
)
largest=r i
ght ;
if(largest! =i )
{
temp=ar r[i
];
ar r[i
]=ar r[largest];
ar r[l
argest ]=t emp;
heapi fy(
ar r
, size, l
argest )
;
}
}
voidheapSor t(
intar r[
],intsize)
{
inti;
for( i=si ze/2-1; i >=0; i--
)
heapi fy(
ar r
, size, i
);
for( i=size-1; i
>=0; i
--)
{
temp=ar r[0];
ar r[0]=ar r[i];
ar r[i
]=t emp;
heapi fy(
ar r
, i,0);
}
}
voidmai n()
{
intar r[]={ 1, 10, 2,3, 4,1, 2,100,
23, 2};
inti;
intsi ze=si zeof (arr)/sizeof(arr
[0])
;
clrscr ();
heapSor t
(ar r,size);
printf (
"printingsor tedel ement s\n");
for( i=0; i
<si ze; ++i)
printf (
"%d\ n" ,arr[
i]
);
get ch( );
}
Out
put
:
Print i
ngsor t edel ement s
1
1
2
2
2
3
4
10
23

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179356
 100

L.
LAKSHMAI
AH l
akshmai
ah.
l@sv
col
l
eges.
edu.
in 801927179357