342
Chapter7 Sorting
7.3
Supposeweexchangeelements
a[i]
and
a[i+k]
,whichwereoriginallyoutoforder.
Provethatatleast1andatmost2k−1inversionsareremoved.
7.4
ShowtheresultofrunningShellsortontheinput9,8,7,6,5,4,3,2,1usingthe
increments{1,3,7}.
7.5
a. WhatistherunningtimeofShellsortusingthetwo-incrementsequence{1,2}?
b.ShowthatforanyN,thereexistsathree-incrementsequencesuchthatShellsort
runsinO(N
5/3
)time.
c. ShowthatforanyN,thereexistsasix-incrementsequencesuchthatShellsort
runsinO(N
3/2
)time.
7.6
a. ProvethattherunningtimeofShellsortis(N
2
)usingincrementsoftheform
1,c,c
2
,...,c
i
foranyintegerc.

b.Provethatfortheseincrements,theaveragerunningtimeis(N
3/2
).
7.7
Provethatifak-sortedfileisthenh-sorted,itremainsk-sorted.
7.8
ProvethattherunningtimeofShellsort,usingtheincrementsequencesuggested
byHibbard,is(N
3/2
)intheworstcase.(Hint:Youcanprovetheboundbycon-
sideringthespecialcaseofwhatShellsortdoeswhenallelementsareeither0or1.)
Seta[i]=1ifiisexpressibleasalinearcombinationofh
t
,h
t−1
,...,h
t/2+1
and0
otherwise.
7.9
DeterminetherunningtimeofShellsortfor
a. sortedinput
b.reverse-orderedinput
7.10 DoeitherofthefollowingmodificationstotheShellsortroutinecodedinFigure7.6
affecttheworst-caserunningtime?
a. Beforeline8,subtractonefrom
gap
ifitiseven.
b.Beforeline8,addoneto
gap
ifitiseven.
7.11 Showhowheapsortprocessestheinput142,543,123,65,453,879,572,434,
111,242,811,102.
7.12 Whatistherunningtimeofheapsortforpresortedinput?
7.13 Showthatthereareinputsthatforceevery
percolateDown
inheapsorttogoallthe
waytoaleaf.(Hint:Workbackward.)
7.14 Rewriteheapsortsothatitsortsonlyitemsthatareintherange
low
to
high
,which
arepassedasadditionalparameters.
7.15 Sort3,1,4,1,5,9,2,6usingmergesort.
7.16 Howwouldyouimplementmergesortwithoutusingrecursion?
7.17 Determinetherunningtimeofmergesortfor
a. sortedinput
b.reverse-orderedinput
c. randominput
7.18 In the analysis of mergesort, , constants have been disregarded.Prove that the
number of comparisons used in the worst case by mergesort is NlogN −
2
logN
+ 1.
How to convert pdf slides to powerpoint - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf to editable powerpoint online; add pdf to powerpoint
How to convert pdf slides to powerpoint - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf file to powerpoint; change pdf to powerpoint on
Exercises
343
7.19 Sort3,1,4,1,5,9,2,6,5,3,5 using quicksortwith median-of-threepartitioning
andacutoffof3.
7.20 Usingthequicksortimplementationinthischapter,determinetherunningtimeof
quicksortfor
a. sortedinput
b.reverse-orderedinput
c. randominput
7.21 RepeatExercise7.20whenthepivotischosenas
a. thefirstelement
b.thelargerofthefirsttwodistinctelements
c. arandomelement
d.theaverageofallelementsintheset
7.22 a. Forthequicksortimplementationinthischapter,whatistherunningtimewhen
allkeysareequal?
b.Supposewechangethepartitioningstrategysothatneither
i
nor
j
stopswhen
anelementwiththesamekeyasthepivotisfound.Whatfixesneedtobemade
inthecodetoguaranteethatquicksortworks,andwhatistherunningtime
whenallkeysareequal?
c. Supposewechangethepartitioningstrategysothat
i
stopsatanelementwith
thesamekeyasthepivot,but
j
doesnotstopinasimilarcase.Whatfixesneed
tobemadeinthecodetoguaranteethatquicksortworks,andwhenallkeysare
equal,whatistherunningtimeofquicksort?
7.23 Supposewechoosetheelementinthemiddlepositionofthearrayaspivot.Does
thismakeitunlikelythatquicksortwillrequirequadratictime?
7.24 Constructapermutationof20elementsthatisasbadaspossibleforquicksort
usingmedian-of-threepartitioningandacutoffof3.
7.25 Thequicksort in the textuses tworecursive calls.Removeoneofthe calls as
follows:
a. Rewritethecodesothatthesecondrecursivecallisunconditionally y thelast
lineinquicksort.Dothisbyreversingthe
if
/
else
andreturningafterthecallto
insertionSort
.
b.Removethetailrecursionbywritinga
while
loopandaltering
left
.
7.26 ContinuingfromExercise7.25,afterpart(a),
a. Performatestsothatthesmallersubarrayisprocessedbythefirstrecursivecall,
whilethelargersubarrayisprocessedbythesecondrecursivecall.
b.Removethetailrecursionbywritinga
while
loopandaltering
left
or
right
,as
necessary.
c. Provethatthenumberofrecursivecallsislogarithmicintheworstcase.
7.27 Supposetherecursivequicksortreceivesan
int
parameter,
depth
,fromthedriver
thatisinitiallyapproximately2logN.
a. Modifytherecursivequicksorttocall
heapsort
onitscurrentsubarrayifthelevel
ofrecursionhasreached
depth
.(Hint:Decrement
depth
asyoumakerecursive
calls;whenitis0,switchtoheapsort.)
C# PowerPoint - How to Process PowerPoint
slides sorting library can help you a lot. Extract Slides from PowerPoint in C#.NET. Use C# sample code to extract single or several
how to convert pdf to powerpoint; how to change pdf to powerpoint on
VB.NET PowerPoint: Read, Edit and Process PPTX File
split PowerPoint file, change the order of PPTX sildes and extract one or more slides from PowerPoint How to convert PowerPoint to PDF, render PowerPoint to
how to convert pdf to ppt online; convert pdf to ppt online without email
344
Chapter7 Sorting
b.Provethattheworst-caserunningtimeofthisalgorithmisO(NlogN).
c. Conductexperimentstodeterminehowoften
heapsort
getscalled.
d.Implement this technique e in n conjunction with tail-recursion removal in
Exercise7.25.
e. ExplainwhythetechniqueinExercise7.26wouldnolongerbeneeded.
7.28 When implementing quicksort, , if the array y contains lots of duplicates,it may
be better to perform a three-way partition (into elements less than, equal to,
andgreaterthan thepivot)tomake smaller recursivecalls. . Assume three-way
comparisons.
a. Giveanalgorithmthatperformsathree-wayin-placepartitionofanN-element
subarrayusingonlyN−1three-waycomparisons.Ifthereareditemsequal
tothepivot,youmay useadditional
Comparable
swaps,aboveandbeyond
thetwo-waypartitioningalgorithm.(Hint:As
i
and
j
movetowardeachother,
maintainfivegroupsofelementsasshownbelow):
EQUAL SMALL UNKNOWN LARGE EQUAL
i
j
b.Provethatusingthealgorithmabove,sortinganN-elementarraythatcontains
onlyddifferentvalues,takesO(dN)time.
7.29 Writeaprogramtoimplementtheselectionalgorithm.
7.30 Solvethefollowingrecurrence:T(N)=(1/N)[
N−1
i=0
T(i)]+cN,T(0)=0.
7.31 Asortingalgorithmisstableifelementswithequalelementsareleftinthesame
orderastheyoccurintheinput.Whichofthesortingalgorithmsinthischapter
arestableandwhicharenot?Why?
7.32 Supposeyou are given asorted list ofelements followedby f(N)randomly
orderedelements.Howwouldyousorttheentirelistif
a. f(N)=O(1)?
b.f(N)=O(logN)?
c. f(N)=O(
N)?
d.Howlargecanf(N)befortheentireliststilltobesortableinO(N)time?
7.33 ProvethatanyalgorithmthatfindsanelementinasortedlistofNelements
requires(logN)comparisons.
7.34 UsingStirling’sformula,N!≈(N/e)
N
N,giveapreciseestimateforlog(N!).
7.35
a. InhowmanywayscantwosortedarraysofNelementsbemerged?
b.Giveanontriviallowerboundonthenumberofcomparisonsrequiredtomerge
twosortedlistsofNelementsbytakingthelogarithmofyouranswerinpart(a).
7.36 ProvethatmergingtwosortedarraysofNitemsrequiresatleast2N−1compar-
isons.Youmustshowthatiftwoelementsinthemergedlistareconsecutiveand
fromdifferentlists,thentheymustbecompared.
7.37 Considerthefollowingalgorithmforsortingsixnumbers:
SortthefirstthreenumbersusingAlgorithmA.
SortthesecondthreenumbersusingAlgorithmB.
MergethetwosortedgroupsusingAlgorithmC.
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
add image to slide, extract slides and merge library SDK, this VB.NET PowerPoint processing control powerful & profession imaging controls, PDF document, image
how to convert pdf file to powerpoint presentation; add pdf to powerpoint slide
VB.NET PowerPoint: Sort and Reorder PowerPoint Slides by Using VB.
clip art or screenshot to PowerPoint document slide large amount of robust PPT slides/pages editing powerful & profession imaging controls, PDF document, image
how to convert pdf to powerpoint on; how to convert pdf to ppt using
Exercises
345
Showthatthisalgorithmissuboptimal,regardlessofthechoicesforAlgorithmsA,
B,andC.
7.38 Writeaprogramthatreadspointsinaplaneandoutputsanygroup offour
ormorecolinearpoints(i.e.,pointsonthesameline).Theobviousbrute-force
algorithmrequiresO(N
4
)time.However,thereisabetteralgorithmthatmakesuse
ofsortingandrunsinO(N
2
logN)time.
7.39 ShowthatthetwosmallestelementsamongNcanbefoundinN+logN−2
comparisons.
7.40 Thefollowing divide-and-conqueralgorithmisproposedforfindingthesimul-
taneousmaximumandminimum:Ifthereisoneitem,itis themaximumand
minimum,andiftherearetwoitems,thencomparethem,andinonecompari-
sonyoucanfindthemaximumandminimum.Otherwise,splittheinputintotwo
halves,dividedasevenlyaspossibly(ifNisodd,oneofthetwohalveswillhave
onemoreelementthantheother).Recursivelyfindthemaximumandminimum
ofeachhalf,andthenintwoadditionalcomparisonsproducethemaximumand
minimumfortheentireproblem.
a. SupposeNisapowerof2.Whatistheexactnumberofcomparisonsusedby
thisalgorithm?
b.SupposeNisoftheform3·2
k
.Whatistheexactnumberofcomparisonsused
bythisalgorithm?
c. Modifythealgorithmasfollows:WhenNiseven,butnotdivisiblebyfour,split
theinputintosizesofN/2−1andN/2+1.Whatistheexactnumberof
comparisonsusedbythisalgorithm?
7.41 SupposewewanttopartitionNitemsintoGequal-sizedgroupsofsizeN/G,such
thatthesmallestN/Gitemsareingroup1,thenextsmallestN/Gitemsarein
group2,andsoon.Thegroupsthemselvesdonothavetobesorted.Forsimplicity,
youmayassumethatNandGarepowersoftwo.
a. GiveanO(NlogG)algorithmtosolvethisproblem.
b.Provean(NlogG)lowerboundtosolvethisproblemusingcomparison-based
algorithms.
7.42 Givealinear-timealgorithmtosortNfractions,eachofwhosenumeratorsand
denominatorsareintegersbetween1andN.
7.43 SupposearraysAandBareboth sorted and bothcontainelements.Givean
O(logN)algorithmtofindthemedianofAB.
7.44 SupposeyouhaveanarrayofNelementscontainingonlytwodistinctkeys,
true
and
false
.GiveanO(N)algorithmtorearrangethelistsothatall
false
elements
precedethe
true
elements.Youmayuseonlyconstantextraspace.
7.45 SupposeyouhaveanarrayofNelements,containingthreedistinctkeys,
true
,
false
,and
maybe
.GiveanO(N)algorithmtorearrangethelistsothatall
false
elementsprecede
maybe
elements,whichinturnprecede
true
elements.Youmay
useonlyconstantextraspace.
7.46 a. Prove e that any comparison-based algorithm m to o sort 4 elements requires s 5
comparisons.
b.Giveanalgorithmtosort4elementsin5comparisons.
VB.NET PowerPoint: Use PowerPoint SDK to Create, Load and Save PPT
Besides, users also can get the precise PowerPoint slides count as soon as the PowerPoint document has been loaded by using the page number getting method.
conversion of pdf into ppt; export pdf to powerpoint
VB.NET PowerPoint: Extract & Collect PPT Slide(s) Using VB Sample
want to combine these extracted slides into a please read this VB.NET PowerPoint slide processing powerful & profession imaging controls, PDF document, image
how to convert pdf into powerpoint on; convert pdf to editable ppt online
346
Chapter7 Sorting
7.47 a. Provethat7comparisonsarerequiredtosort5elementsusinganycomparison-
basedalgorithm.
b.Giveanalgorithmtosort5elementswith7comparisons.
7.48 WriteanefficientversionofShellsortandcompareperformancewhenthefollowing
incrementsequencesareused:
a. Shell’soriginalsequence
b.Hibbard’sincrements
c. Knuth’sincrements:h
i
=
1
2
(3
i
+1)
d.Gonnet’sincrements:h
t
=
N
2.2
andh
k
=
h
k+1
2.2
(withh
1
=1ifh
2
=2)
e. Sedgewick’sincrements
7.49 Implementanoptimizedversionofquicksortandexperimentwithcombinations
ofthefollowing:
a. pivot:firstelement,middleelement,randomelement,medianofthree,median
offive
b.cutoffvaluesfrom0to20
7.50 Writea routinethat reads in twoalphabetizedfiles andmergesthemtogether,
formingathird,alphabetized,file.
7.51 Supposeweimplementthemedian-of-threeroutineasfollows:Findthemedianof
a[left]
,
a[center]
,
a[right]
,andswapitwith
a[right]
.Proceedwiththenormal
partitioningstepstarting
i
at
left
and
j
at
right-1
(insteadof
left+1
and
right-2
).
a. Supposetheinputis2,3,4,...,N−1,N,1.Forthisinput,whatistherunning
timeofthisversionofquicksort?
b.Supposetheinputisinreverseorder.Forthisinput,whatistherunningtime
ofthisversionofquicksort?
7.52 Provethatanycomparison-basedsortingalgorithmrequires(NlogN)compar-
isonsonaverage.
7.53 WearegivenanarraythatcontainsNnumbers.Wewanttodetermineifthereare
twonumberswhosesumequalsagivennumberK.Forinstance,iftheinputis8,
4,1,6,andKis10,thentheanswerisyes(4and6).Anumbermaybeusedtwice.
Dothefollowing:
a. GiveanO(N
2
)algorithmtosolvethisproblem.
b.GiveanO(NlogN)algorithmtosolvethisproblem.(Hint:Sorttheitemsfirst.
Afterthatisdone,youcansolvetheprobleminlineartime.)
c. Codebothsolutionsandcomparetherunningtimesofyouralgorithms.
7.54 RepeatExercise7.53forfournumbers.TrytodesignanO(N
2
logN)algorithm.
(Hint:Computeallpossiblesumsoftwoelements.Sortthesepossiblesums.Then
proceedasinExercise7.53.)
7.55 RepeatExercise7.53forthreenumbers.TrytodesignanO(N
2
)algorithm.
7.56 Considerthefollowingstrategyfor
percolateDown
:WehaveaholeatnodeX.The
normalroutineistocompareX’schildrenandthenmovethechilduptoXifitis
larger(inthecaseofa(max)heap)thantheelementwearetryingtoplace,thereby
pushingtheholedown;westopwhenitissafetoplacethenewelementinthe
hole.Thealternativestrategyistomoveelementsupandtheholedownasfaras
VB.NET PowerPoint: Merge and Split PowerPoint Document(s) with PPT
of the split PPT document will contain slides/pages 1-4 code in VB.NET to finish PowerPoint document splitting If you want to see more PDF processing functions
changing pdf to powerpoint file; pdf to powerpoint converter
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
It contains PowerPoint documentation features and all PPT slides. Control to render and convert target PowerPoint or document formats, such as PDF, BMP, TIFF
how to convert pdf slides to powerpoint presentation; create powerpoint from pdf
References
347
possible,withouttestingwhetherthenewcellcanbeinserted.Thiswouldplace
thenewcellinaleafandprobablyviolatetheheaporder;tofixtheheaporder,
percolatethenewcellupinthenormalmanner.Writearoutinetoincludethis
idea,andcomparetherunningtimewithastandardimplementationofheapsort.
7.57 Proposeanalgorithmtosortalargefileusingonlytwotapes.
7.58 a. ShowthatalowerboundofN!/2
2N
onthenumberofheapsisimpliedbythe
factthat
buildHeap
usesatmost2Ncomparisons.
b.UseStirling’sformulatoexpandthisbound.
7.59 MisanN-by-Nmatrixinwhichtheentriesineachrowsareinincreasingorder
andtheentriesineachcolumnareinincreasingorder(readingtoptobottom).
ConsidertheproblemofdeterminingifisinMusingthree-waycomparisons
(i.e.,onecomparisonofxwithM[i][j]tellsyoueitherthatxislessthan,equalto,
orgreaterthanM[i][j]).
a. Giveanalgorithmthatusesatmost2N−1comparisons.
b.Provethatanyalgorithmmustuseatleast2N−1comparisons.
7.60 Thereisaprizehiddeninabox;thevalueoftheprizeisapositiveintegerbetween
1andN,andyouaregivenN.Towintheprize,youhavetoguessitsvalue.Your
goalistodoitinasfewguessesaspossible;however,amongthoseguesses,you
mayonlymakeatmostgguessesthataretoohigh.Thevaluegwillbespecifiedat
thestartofthegame,andifyoumakemorethangguessesthataretoohigh,you
lose.So,forexample,ifg=0,youthencanwininNguessesbysimplyguessing
thesequence1,2,3,...
a. Supposeg=logN.Whatstrategyminimizesthenumberofguesses?
b.Supposeg=1.ShowthatyoucanalwayswininO(N1/2)guesses.
c. Supposeg=1.Showthatanyalgorithmthatwinstheprizemustuse(N1/2)
guesses.
d.Giveanalgorithmandmatchinglowerboundforanyconstantg.
References
Knuth’sbook[16]isacomprehensivereferenceforsorting.GonnetandBaeza-Yates[5]
hassomemoreresults,aswellasahugebibliography.
TheoriginalpaperdetailingShellsortis[29].ThepaperbyHibbard[9]suggestedthe
useoftheincrements2
k
−1andtightenedthecodebyavoidingswaps.Theorem7.4
is from[19].Pratt’s lowerbound,which uses amorecomplex methodthan that sug-
gestedinthetext,canbefoundin[22].Improvedincrementsequencesandupperbounds
appearin[13],[28],and[31];matchinglowerboundshavebeenshownin[32].Ithas
beenshownthatnoincrementsequencegivesanO(NlogN)worst-caserunningtime[20].
Theaverage-caserunningtimeforShellsortisstillunresolved.Yao[34]hasperformedan
extremelycomplexanalysisforthethree-incrementcase.Theresulthasyettobeextended
tomoreincrements,buthasbeenslightlyimproved[14].ThepaperbyJiang,Li,and
Vityani[15]hasshownan(pN
1+1/p
)lowerboundontheaverage-caserunningtimeof
p-passShellsort.Experimentswithvariousincrementsequencesappearin[30].
VB.NET PowerPoint: Convert & Render PPT into PDF Document
Using this VB.NET PowerPoint to PDF converting demo code below, you can easily convert all slides of source PowerPoint document into a multi-page PDF file.
conversion of pdf to ppt online; convert pdf to powerpoint
VB.NET PowerPoint: Add Image to PowerPoint Document Slide/Page
insert or delete any certain PowerPoint slide without methods to reorder current PPT slides in both powerful & profession imaging controls, PDF document, tiff
convert pdf to powerpoint presentation; convert pdf slides to powerpoint online
348
Chapter7 Sorting
HeapsortwasinventedbyWilliams[33];Floyd[4]providedthelinear-timealgorithm
forheapconstruction.Theorem7.5isfrom[23].
Anexactaverage-caseanalysisofmergesorthasbeendescribedin[7].Analgorithmto
performmerginginlineartimewithoutextraspaceisdescribedin[12].
QuicksortisfromHoare[10].Thispaperanalyzesthebasicalgorithm,describesmost
oftheimprovements,andincludestheselectionalgorithm.Adetailedanalysisandempir-
icalstudywasthesubjectofSedgewick’sdissertation[27].Manyoftheimportantresults
appearinthethreepapers[24],[25],and [26]. . [1]provides adetailed d Cimplemen-
tation withsomeadditionalimprovements,andpointsoutthatolderimplementations
ofthe
UNIX
qsortlibraryroutineareeasilydriventoquadraticbehavior.Exercise7.27is
from[18].
DecisiontreesandsortingoptimalityarediscussedinFordandJohnson[5].Thispaper
alsoprovides an algorithmthatalmost meets thelowerboundintermsofnumberof
comparisons(butnototheroperations).Thisalgorithmwaseventuallyshowntobeslightly
suboptimalbyManacher[17].
TheselectionlowerboundsobtainedinTheorem7.9arefrom[6].Thelowerbound
forfindingthemaximumandminimumsimultaneouslyisfromPohl[21].Thecurrent
bestlowerboundforfindingthemedianisslightlyabove2NcomparisonsduetoDorand
Zwick[3];theyalsohavethebestupperbound,whichisroughly2.95Ncomparisons[2].
Externalsortingiscoveredindetailin[16].Stablesorting,describedinExercise7.31,
hasbeenaddressedbyHorvath[11].
1.J. L. BentleyandM.D. McElroy,“EngineeringaSortFunction,”Software—Practiceand
Experience,23(1993),1249–1265.
2.D.DorandU.Zwick,“SelectingtheMedian,”SIAMJournalonComputing,28(1999),1722–
1758.
3.D.DorandU.Zwick,“MedianSelectionRequires(2+ε)nComparisons,”SIAMJournalon
DiscreteMath,14(2001),312–325.
4.R.W.Floyd,“Algorithm245:Treesort3,”CommunicationsoftheACM,7(1964),701.
5.L.R.FordandS.M.Johnson,“ATournamentProblem,”AmericanMathematicsMonthly,66
(1959),387–389.
6.F. Fussenegger and H. Gabow, , “A Counting g Approach to Lower r Bounds for r Selection
Problems,”JournaloftheACM,26(1979),227–238.
7.M. GolinandR. Sedgewick, “ExactAnalysis of Mergesort,” FourthSIAMConference on
DiscreteMathematics,1988.
8.G. H. Gonnetand R. Baeza-Yates,Handbook of Algorithms andDataStructures,2ded.,
Addison-Wesley,Reading,Mass.,1991.
9.T.H.Hibbard, “AnEmpiricalStudyof MinimalStorageSorting,”Communicationsofthe
ACM,6(1963),206–213.
10.C.A.R.Hoare,“Quicksort,”ComputerJournal,5(1962),10–15.
11.E.C.Horvath,“StableSortinginAsymptoticallyOptimalTimeandExtraSpace,”Journalof
theACM,25(1978),177–199.
12.B.HuangandM.Langston,“PracticalIn-placeMerging,”CommunicationsoftheACM,31
(1988),348–352.
13.J.IncerpiandR.Sedgewick,“ImprovedUpperBoundsonShellsort,”JournalofComputer
andSystemSciences,31(1985),210–224.
References
349
14.S. Jansonand d D. . E. . Knuth, “Shellsort t withThree e Increments,” RandomStructuresand
Algorithms,10(1997),125–142.
15.T. Jiang, , M. Li, and P. Vitanyi, “A A Lower Boundon the Average-Case e Complexity y of
Shellsort,”JournaloftheACM,47(2000),905–911.
16.D.E. Knuth,TheArt ofComputer Programming.Volume3:SortingandSearching,2ded.,
Addison-Wesley,Reading,Mass.,1998.
17.G.K.Manacher,“TheFord-JohnsonSortingAlgorithmIsNotOptimal,”JournaloftheACM,
26(1979),441–456.
18.D. R. . Musser, , “Introspective e Sorting and SelectionAlgorithms,” Software—Practiceand
Experience,27(1997),983–993.
19.A. A. Papernov and G. V. . Stasevich, , “A A Method of Information Sorting in Computer
Memories,”ProblemsofInformationTransmission,1(1965),63–75.
20.C.G.Plaxton,B.Poonen,andT.Suel,“ImprovedLowerBoundsforShellsort,”Proceedings
oftheThirty-thirdAnnualSymposiumontheFoundationsofComputerScience(1992),226–235.
21.I.Pohl,“ASortingProblemandItsComplexity,”CommunicationsoftheACM,15(1972),
462–464.
22.V.R.Pratt,ShellsortandSortingNetworks,GarlandPublishing,NewYork,1979.(Originally
presentedastheauthor’sPh.D.thesis,StanfordUniversity,1971.)
23.R.SchafferandR.Sedgewick,“TheAnalysisofHeapsort,”JournalofAlgorithms,14(1993),
76–100.
24.R. Sedgewick, “Quicksort t with Equal Keys,” ” SIAM Journal l on Computing, 6 (1977),
240–267.
25.R.Sedgewick,“TheAnalysisofQuicksortPrograms,”ActaInformatica,7(1977),327–355.
26.R.Sedgewick,“ImplementingQuicksortPrograms,”CommunicationsoftheACM,21(1978),
847–857.
27.R.Sedgewick,Quicksort,GarlandPublishing,NewYork,1978.(Originallypresentedasthe
author’sPh.D.thesis,StanfordUniversity,1975.)
28.R. Sedgewick, “A New w Upper Bound for Shellsort,” ” Journal of Algorithms, 7 (1986),
159–173.
29.D. L. Shell, “A A High-Speed Sorting Procedure,” ” Communicationsof theACM,2 (1959),
30–32.
30.M.A.Weiss,“EmpiricalResultsontheRunningTimeofShellsort,”ComputerJournal,34
(1991),88–91.
31.M. A. Weiss s andR. . Sedgewick, “More on ShellsortIncrement t Sequences,” ” Information
ProcessingLetters,34(1990),267–270.
32.M.A.WeissandR.Sedgewick,“TightLowerBoundsforShellsort,”JournalofAlgorithms,11
(1990),242–251.
33.J. W. . J. . Williams, “Algorithm m 232: Heapsort,” ” Communications of the ACM, 7 (1964),
347–348.
34.A.C.Yao,“AnAnalysisof(h,k,1)Shellsort,”JournalofAlgorithms,1(1980),14–50.
This page intentionally left blank 
C H A P P T E R
8
TheDisjointSetsClass
Inthischapter,wedescribeanefficientdatastructuretosolvetheequivalenceproblem.
Thedatastructureissimpletoimplement.Eachroutinerequiresonlyafewlinesofcode,
and asimple array can be used.The implementation is alsoextremely fast,requiring
constantaveragetimeperoperation.Thisdatastructureisalsoveryinterestingfroma
theoreticalpointofview,becauseitsanalysisisextremelydifficult;thefunctionalformof
theworstcaseisunlikeanywehaveyetseen.Forthedisjointsetsdatastructure,wewill...
Showhowitcanbeimplementedwithminimalcodingeffort.
Greatlyincreaseitsspeed,usingjusttwosimpleobservations.
Analyzetherunningtimeofafastimplementation.
Seeasimpleapplication.
8.1 EquivalenceRelations
ArelationRisdefinedonasetSifforeverypairofelements(a,b),a,bS,aRbiseither
trueorfalse.IfaRbistrue,thenwesaythataisrelatedtob.
AnequivalencerelationisarelationRthatsatisfiesthreeproperties:
1. (Reflexive)aRa,forallaS.
2. (Symmetric)aRbifandonlyifbRa.
3. (Transitive)aRbandbRcimpliesthataRc.
Wewillconsiderseveralexamples.
The≤relationshipisnotanequivalencerelationship.Althoughitisreflexive,since
aa,andtransitive,sinceabandbcimpliesac,itisnotsymmetric,sinceab
doesnotimplyba.
Electricalconnectivity,whereallconnectionsarebymetalwires,isanequivalence
relation.Therelationisclearlyreflexive,asanycomponentisconnectedtoitself.Ifais
electricallyconnectedtob,thenbmustbeelectricallyconnectedtoa,sotherelationis
symmetric.Finally,ifaisconnectedtobandbisconnectedtoc,thenaisconnectedtoc.
Thuselectricalconnectivityisanequivalencerelation.
Twocitiesarerelatediftheyareinthesamecountry.Itiseasilyverifiedthatthisisan
equivalencerelation.Supposetownaisrelatedtobifitispossibletotravelfromatobby
takingroads.Thisrelationisanequivalencerelationifalltheroadsaretwo-way.
351
Documents you may be interested
Documents you may be interested