﻿

# generate pdf using itextsharp in mvc : How to convert pdf slides to powerpoint application Library tool html .net windows online DataStructures36-part1794

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-sortedﬁleisthenh-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 DoeitherofthefollowingmodiﬁcationstotheShellsortroutinecodedinFigure7.6
affecttheworst-caserunningtime?
a. Beforeline8,subtractonefrom
gap
ifitiseven.
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
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. theﬁrstelement
b.thelargeroftheﬁrsttwodistinctelements
c. arandomelement
d.theaverageofallelementsintheset
7.22 a. Forthequicksortimplementationinthischapter,whatistherunningtimewhen
allkeysareequal?
b.Supposewechangethepartitioningstrategysothatneither
i
nor
j
stopswhen
inthecodetoguaranteethatquicksortworks,andwhatistherunningtime
whenallkeysareequal?
c. Supposewechangethepartitioningstrategysothat
i
stopsatanelementwith
thesamekeyasthepivot,but
j
doesnotstopinasimilarcase.Whatﬁxesneed
equal,whatistherunningtimeofquicksort?
7.23 Supposewechoosetheelementinthemiddlepositionofthearrayaspivot.Does
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. Performatestsothatthesmallersubarrayisprocessedbytheﬁrstrecursivecall,
whilethelargersubarrayisprocessedbythesecondrecursivecall.
b.Removethetailrecursionbywritinga
while
loopandaltering
left
or
right
,as
necessary.
c. Provethatthenumberofrecursivecallsislogarithmicintheworstcase.
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
Comparable
swaps,aboveandbeyond
thetwo-waypartitioningalgorithm.(Hint:As
i
and
j
movetowardeachother,
maintainﬁvegroupsofelementsasshownbelow):
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 ProvethatanyalgorithmthatﬁndsanelementinasortedlistofNelements
requires(logN)comparisons.
7.34 UsingStirling’sformula,N!≈(N/e)
N
N,giveapreciseestimateforlog(N!).
7.35
a. InhowmanywayscantwosortedarraysofNelementsbemerged?
b.Giveanontriviallowerboundonthenumberofcomparisonsrequiredtomerge
7.36 ProvethatmergingtwosortedarraysofNitemsrequiresatleast2N−1compar-
isons.Youmustshowthatiftwoelementsinthemergedlistareconsecutiveand
fromdifferentlists,thentheymustbecompared.
7.37 Considerthefollowingalgorithmforsortingsixnumbers:
SorttheﬁrstthreenumbersusingAlgorithmA.
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.
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-conqueralgorithmisproposedforﬁndingthesimul-
taneousmaximumandminimum:Ifthereisoneitem,itis themaximumand
minimum,andiftherearetwoitems,thencomparethem,andinonecompari-
sonyoucanﬁndthemaximumandminimum.Otherwise,splittheinputintotwo
halves,dividedasevenlyaspossibly(ifNisodd,oneofthetwohalveswillhave
onemoreelementthantheother).Recursivelyﬁndthemaximumandminimum
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)algorithmtoﬁndthemedianofAB.
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 WriteanefﬁcientversionofShellsortandcompareperformancewhenthefollowing
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:ﬁrstelement,middleelement,randomelement,medianofthree,median
ofﬁve
b.cutoffvaluesfrom0to20
7.50 Writea routinethat reads in twoalphabetizedﬁles andmergesthemtogether,
formingathird,alphabetized,ﬁle.
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
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,
Dothefollowing:
a. GiveanO(N
2
)algorithmtosolvethisproblem.
b.GiveanO(NlogN)algorithmtosolvethisproblem.(Hint:Sorttheitemsﬁrst.
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;toﬁxtheheaporder,
percolatethenewcellupinthenormalmanner.Writearoutinetoincludethis
idea,andcomparetherunningtimewithastandardimplementationofheapsort.
7.57 Proposeanalgorithmtosortalargeﬁleusingonlytwotapes.
7.58 a. ShowthatalowerboundofN!/2
2N
onthenumberofheapsisimpliedbythe
factthat
buildHeap
usesatmost2Ncomparisons.
b.UseStirling’sformulatoexpandthisbound.
7.59 MisanN-by-Nmatrixinwhichtheentriesineachrowsareinincreasingorder
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.Thevaluegwillbespeciﬁedat
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
icalstudywasthesubjectofSedgewick’sdissertation[27].Manyoftheimportantresults
appearinthethreepapers[24],[25],and [26]. . [1]provides adetailed d Cimplemen-
ofthe
UNIX
from[18].
DecisiontreesandsortingoptimalityarediscussedinFordandJohnson[5].Thispaper
alsoprovides an algorithmthatalmost meets thelowerboundintermsofnumberof
comparisons(butnototheroperations).Thisalgorithmwaseventuallyshowntobeslightly
suboptimalbyManacher[17].
TheselectionlowerboundsobtainedinTheorem7.9arefrom[6].Thelowerbound
forﬁndingthemaximumandminimumsimultaneouslyisfromPohl[21].Thecurrent
bestlowerboundforﬁndingthemedianisslightlyabove2NcomparisonsduetoDorand
Zwick[3];theyalsohavethebestupperbound,whichisroughly2.95Ncomparisons[2].
Externalsortingiscoveredindetailin[16].Stablesorting,describedinExercise7.31,
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.,
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.,
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.