312
Chapter7 Sorting
13
81
0
92
43
65
31
57
75
26
13
81
0
92
43
65
31 57
75
26
select pivot
partition
quicksort large
65
65
13
0
26
43
57
31
75
81
92
quicksort small
0 13 3 26
31 43
57
0 13 3 26
31
43
57 65 5 75 5 81
92
75 81
92
Figure7.14 Thestepsofquicksortillustratedbyexample
AWrongWay
Thepopular,uninformedchoiceistousethefirstelementasthepivot.Thisisacceptable
iftheinputisrandom,butiftheinputispresortedorinreverseorder,thenthepivot
providesapoorpartition,becauseeitheralltheelementsgointoS
1
ortheygointoS
2
.
Worse,thishappensconsistentlythroughouttherecursivecalls.Thepracticaleffectisthat
ifthefirstelementisusedasthepivotandtheinputispresorted,thenquicksortwill
takequadratictimetodoessentiallynothingatall,whichisquiteembarrassing.Moreover,
presortedinput(orinputwithalargepresortedsection)isquitefrequent,sousingthe
firstelementaspivotisanabsolutelyhorribleideaandshouldbediscardedimmediately.An
alternativeischoosingthelargerofthefirsttwodistinctelementsaspivot,butthishas
Convert pdf into ppt online - 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 ppt; convert pdf into powerpoint online
Convert pdf into ppt online - 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
how to add pdf to powerpoint presentation; how to convert pdf into powerpoint slides
7.7 Quicksort
313
thesamebadpropertiesasmerelychoosingthefirstelement.Donotusethatpivoting
strategy,either.
ASafeManeuver
Asafecourseismerelytochoosethepivotrandomly.Thisstrategyisgenerallyperfectly
safe,unlesstherandomnumbergeneratorhasaflaw(whichisnotasuncommonasyou
mightthink),sinceitisveryunlikelythatarandompivotwouldconsistentlyprovidea
poorpartition.Ontheotherhand,randomnumbergenerationisgenerallyanexpensive
commodityanddoesnotreducetheaveragerunningtimeoftherestofthealgorithmatall.
Median-of-ThreePartitioning
ThemedianofagroupofnumbersistheN/2th largestnumber.Thebestchoice
ofpivotwould bethemedianofthearray.Unfortunately,thisishardtocalculateand
wouldslowdown quicksortconsiderably.Agood estimatecanbeobtainedbypicking
threeelementsrandomlyandusingthemedianofthesethreeaspivot.Therandomness
turnsoutnottohelpmuch,sothecommoncourseistouseaspivotthemedianofthe
left,right,andcenterelements.Forinstance,withinput8,1,4,9,6,3,5,2,7,0asbefore,
theleftelementis8,therightelementis0,andthecenter(inposition(left+right)/2)
elementis6.Thus,thepivotwouldbev=6.Usingmedian-of-threepartitioningclearly
eliminatesthebadcaseforsortedinput(thepartitionsbecomeequalin thiscase)and
actuallyreducesthenumberofcomparisonsby14%.
7.7.2 PartitioningStrategy
Thereareseveralpartitioning strategiesusedinpractice,buttheonedescribedhereis
knowntogivegoodresults.Itisveryeasy,asweshallsee,todothiswrongorinefficiently,
butit issafetouseaknownmethod.Thefirststepistogetthepivotelementoutof
thewaybyswappingitwiththelastelement.
i
startsatthefirstelementand
j
startsat
thenext-to-lastelement.Iftheoriginalinputwasthesameasbefore,thefollowingfigure
showsthecurrentsituation:
8
1
4
9
0
3
5
2
7
6
i
j
Fornow,wewillassumethatalltheelementsaredistinct.Lateron,wewillworryabout
whattodointhepresenceofduplicates.Asalimitingcase,ouralgorithmmustdothe
properthingifalloftheelementsareidentical.Itissurprisinghoweasyitistodothe
wrongthing.
Whatourpartitioningstagewantstodoistomoveallthesmallelementstotheleft
partofthearrayandallthelargeelementstotherightpart.“Small”and“large”are,of
course,relativetothepivot.
While
i
istotheleftof
j
,wemove
i
right,skippingoverelementsthataresmallerthan
thepivot.Wemove
j
left,skippingoverelementsthatarelargerthanthepivot.When
i
and
j
havestopped,
i
ispointingatalargeelementand
j
ispointingatasmallelement.If
Online Convert PowerPoint to PDF file. Best free online export
Convert a PPTX/PPT File to PDF. Just upload your file by clicking on the blue button or drag-and-drop your pptx or ppt file into the drop area.
image from pdf to ppt; converting pdf to powerpoint slides
How to C#: Convert PDF, Excel, PPT to Word
How to C#: Convert PDF, Excel, PPT to Word. PDF, MS-Excel, MS-PPT to Word Conversion Overview. By integrating XDoc.Word SDK into your C#.NET project, PDF, MS
how to convert pdf slides to powerpoint presentation; converting pdf to ppt
314
Chapter7 Sorting
i
istotheleftof
j
,thoseelementsareswapped.Theeffectistopushalargeelementtothe
rightandasmallelementtotheleft.Intheexampleabove,
i
wouldnotmoveand
j
would
slideoveroneplace.Thesituationisasfollows:
8
1
4
9
0
3
5
2
7
6
i
j
Wethenswaptheelementspointedtoby
i
and
j
andrepeattheprocessuntil
i
and
j
cross:
AfterFirstSwap
2
1
4
9
0
3
5
8
7
6
i
j
BeforeSecondSwap
2
1
4
9
0
3
5
8
7
6
i
j
AfterSecondSwap
2
1
4
5
0
3
9
8
7
6
i
j
BeforeThirdSwap
2
1
4
5
0
3
9
8
7
6
j
i
At this stage,
i
and
j
have crossed, so no swap is s performed. . The final part of the
partitioningistoswapthepivotelementwiththeelementpointedtoby
i
:
AfterSwapwithPivot
2
1
4
5
0
3
6
8
7
9
i
pivot
Whenthepivotisswappedwith
i
inthelaststep,weknowthateveryelementina
positionp<
i
mustbesmall.Thisisbecauseeitherpositionpcontainedasmallelement
How to C#: Convert Word, Excel and PPT to PDF
How to C#: Convert Word, Excel and PPT to PDF. MS Office to PDF Conversion Overview. By integrating XDoc.PDF SDK into your C#.NET project, Microsoft Office
convert pdf to powerpoint online for; convert pdf into ppt online
VB.NET PowerPoint: Convert & Render PPT into PDF Document
directly encode converted image source into PDF document file converted image source to PDF format, RasterEdge VB other encoding APIs to convert rendered image
table from pdf to powerpoint; pdf into powerpoint
7.7 Quicksort
315
tostartwith,orthelargeelementoriginallyinpositionpwasreplacedduringaswap.A
similarargumentshowsthatelementsinpositionsp>
i
mustbelarge.
Oneimportantdetailwemustconsiderishowtohandleelementsthatareequalto
thepivot.Thequestionsarewhetherornot
i
shouldstopwhenitseesanelementequal
tothepivotandwhetherornot
j
shouldstopwhenitseesanelementequaltothepivot.
Intuitively,
i
and
j
oughttodothesamething,sinceotherwisethepartitioningstepis
biased.Forinstance,if
i
stopsand
j
doesnot,thenallelementsthatareequaltothepivot
willwindupinS
2
.
Togetanideaofwhatmightbegood,weconsiderthecasewherealltheelementsin
thearrayareidentical.Ifboth
i
and
j
stop,therewillbemanyswapsbetweenidentical
elements.Althoughthisseemsuseless,thepositiveeffectisthat
i
and
j
willcrossinthe
middle,sowhenthepivotisreplaced,thepartitioncreatestwonearlyequalsubarrays.The
mergesortanalysistellsusthatthetotalrunningtimewouldthenbeO(NlogN).
Ifneither
i
nor
j
stops,andcodeispresenttopreventthemfromrunningofftheendof
thearray,noswapswillbeperformed.Althoughthisseemsgood,acorrectimplementation
wouldthenswapthepivotintothelastspotthat
i
touched,whichwouldbethenext-to-
lastposition (orlast,depending on theexactimplementation).Thiswouldcreatevery
unevensubarrays.Ifalltheelementsareidentical,therunningtimeisO(N
2
).Theeffectis
thesameasusingthefirstelementasapivotforpresortedinput.Ittakesquadratictimeto
donothing!
Thus,wefindthatitisbettertodotheunnecessaryswapsandcreateevensubarrays
thantoriskwildlyunevensubarrays.Therefore,wewillhaveboth
i
and
j
stopifthey
encounteranelementequaltothepivot.Thisturnsouttobetheonlyoneofthefour
possibilitiesthatdoesnottakequadratictimeforthisinput.
Atfirstglanceitmayseemthatworryingaboutanarrayofidenticalelementsissilly.
Afterall,whywouldanyonewanttosort 500,000 identicalelements?However,recall
thatquicksortisrecursive.Supposethereare10,000,000elements,ofwhich500,000are
identical(or,morelikely,complex elementswhosesortkeysareidentical).Eventually,
quicksortwillmaketherecursivecallononlythese500,000elements.Thenitreallywill
beimportanttomakesurethat500,000identicalelementscanbesortedefficiently.
7.7.3 SmallArrays
Forvery smallarrays(≤ ≤ 20),quicksortdoesnotperformas s wellasinsertion sort.
Furthermore,becausequicksortisrecursive,thesecaseswilloccurfrequently.Acommon
solutionisnottousequicksortrecursivelyforsmallarrays,butinsteaduseasortingalgo-
rithmthatisefficientforsmallarrays,suchasinsertionsort.Usingthisstrategycanactually
saveabout15percentintherunningtime(overdoingnocutoffatall).Agoodcutoffrange
isN=10,althoughanycutoffbetween5and20islikelytoproducesimilarresults.This
alsosavesnastydegeneratecases,suchastakingthemedianofthreeelementswhenthere
areonlyoneortwo.
7.7.4 ActualQuicksortRoutines
ThedriverforquicksortisshowninFigure7.15.
C# TIFF: Learn to Convert MS Word, Excel, and PPT to TIFF Image
C# TIFF - Conversion from Word, Excel, PPT to TIFF. In order to convert Microsoft Word, Excel, and PowerPoint to quiet easy to integrate this SDK into your C#
change pdf to powerpoint online; convert pdf to powerpoint presentation
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
to split one PPT (.pptx) document file into smaller sub control add-on can do PPT creating, loading powerful & profession imaging controls, PDF document, image
pdf to ppt; how to change pdf to powerpoint
316
Chapter7 Sorting
1
/**
2
* Quicksort algorithm m (driver).
3
*/
4
template <typename Comparable>
5
void quicksort( vector<Comparable> & & a a )
6
{
7
quicksort( a, 0, , a.size( ( ) ) - 1 );
8
}
Figure7.15 Driverforquicksort
Thegeneralformoftheroutineswillbetopassthearrayandtherangeofthearray
(
left
and
right
)tobesorted.Thefirstroutinetodealwithispivotselection.Theeasi-
estwaytodothisistosort
a[left]
,
a[right]
,and
a[center]
inplace.Thishastheextra
advantagethatthesmallestofthethreewindsupin
a[left]
,whichiswherethepartition-
ingstepwouldputitanyway.Thelargestwindsupin
a[right]
,whichisalsothecorrect
place,sinceitislargerthanthepivot.Therefore,wecanplacethepivotin
a[right - - 1]
andinitialize
i
and
j
to
left + + 1
and
right - 2
inthepartitionphase.Yetanotherben-
efitisthatbecause
a[left]
issmallerthanthepivot,itwillactasasentinelfor
j
.Thus,
wedonotneedtoworryabout
j
runningpasttheend.Since
i
willstoponelements
equaltothepivot,storingthepivotin
a[right-1]
providesasentinelfor
i
.Thecodein
1
/**
2
* Return median of left, , center, and d right.
3
* Order these e and d hide the pivot.
4
*/
5
template <typename Comparable>
6
const Comparable & median3( vector<Comparable> & a, int t left, , int right t )
7
{
8
int center r = = ( left + + right t ) ) / / 2;
9
10
if( a[ center r ] ] < a[ left ] )
11
std::swap( a[ left ], a[ center ] ] );
12
if( a[ right ] < a[ left t ] ] )
13
std::swap( a[ left ], a[ right ] );
14
if( a[ right ] < a[ center ] )
15
std::swap( a[ center r ], , a[ right ] );
16
17
// Place pivot t at position n right - 1
18
std::swap( a[ center r ], a[ right t - - 1 ] );
19
return a[ right - 1 ];
20
}
Figure7.16 Codetoperformmedian-of-threepartitioning
VB.NET PowerPoint: Read & Scan Barcode Image from PPT Slide
VB.NET PPT PDF-417 barcode scanning SDK to detect PDF-417 barcode Allow VB.NET developers to output PPT ISSN barcode scanning result into data string.
how to convert pdf to ppt; convert pdf to powerpoint online no email
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document
VB.NET Read: PDF Text Extract; VB.NET Read: PDF Image Extract; VB.NET Write: Insert text into PDF; C# PDF Convert: How to Convert MS PPT to Adobe PDF Document.
convert pdf into powerpoint; converting pdf to powerpoint online
7.7 Quicksort
317
Figure7.16doesthemedian-of-threepartitioningwithallthesideeffectsdescribed.Itmay
seemthatitisonlyslightlyinefficienttocomputethepivotbyamethodthatdoesnotactu-
allysort
a[left]
,
a[center]
,and
a[right]
,but,surprisingly,thisproducesbadresults(see
Exercise7.51).
Therealheartofthequicksort routineisin Figure7.17.Itincludesthepartition-
ingand recursivecalls.There areseveralthings worthnotingin this implementation.
Line16initializes
i
and
j
to1pasttheircorrectvalues,sothattherearenospecialcases
toconsider.Thisinitializationdependsonthefactthatmedian-of-threepartitioninghas
1
/**
2
* Internal l quicksort t method d that makes recursive calls.
3
* Uses median-of-three e partitioning and d a a cutoff of 10.
4
* a a is s an array y of Comparable items.
5
* left is the e left-most index of the e subarray.
6
* right t is the right-most t index of f the subarray.
7
*/
8
template <typename e Comparable>
9
void quicksort( ( vector<Comparable> & & a, int t left, , int right t )
10
{
11
if( left t + 10 <= right t )
12
{
13
const Comparable e & & pivot = = median3( ( a, , left, right );
14
15
// Begin partitioning
16
int i i = = left, , j j = right - 1;
17
for( ; ; )
18
{
19
while( a[ ++i i ] < < pivot t ) ) { { }
20
while( pivot t < < a[ --j j ] ) ) { { }
21
if( i < j j )
22
std::swap( a[ i i ], a[ [ j j ] );
23
else
24
break;
25
}
26
27
std::swap( a[ i i ], , a[ right t - - 1 1 ] ); ; // / Restore pivot
28
29
quicksort( a, left, , i i - - 1 );
// Sort small l elements
30
quicksort( a, i i + 1, right );
// Sort large e elements
31
}
32
else // / Do an n insertion n sort on the e subarray
33
insertionSort( a, left, right t );
34
}
Figure7.17 Mainquicksortroutine
318
Chapter7 Sorting
16
int i i = left + + 1, j j = right - 2;
17
for( ; ; ; ; )
18
{
19
while( a[ i ] ] < < pivot t ) ) i++;
20
while( pivot < a[ j ] ] ) ) j--;
21
if( i i < < j )
22
std::swap( a[ i ], a[ j ] ] );
23
else
24
break;
25
}
Figure7.18 Asmallchangetoquicksort,whichbreaksthealgorithm
somesideeffects;thisprogramwillnotworkifyoutrytouseitwithoutchangewitha
simplepivotingstrategy,because
i
and
j
startinthewrongplaceandthereisnolongera
sentinelfor
j
.
Theswappingactionatline22issometimeswrittenexplicitly,forspeedpurposes.For
thealgorithmtobefast,itisnecessarytoforcethecompilertocompilethiscodeinline.
Manycompilerswilldothisautomaticallyif
swap
isdeclaredusing
inline
,butforthose
thatdonot,thedifferencecanbesignificant.
Finally,lines19and20showwhyquicksortissofast.Theinnerloopofthealgorithm
consistsofanincrement/decrement(by1,whichisfast),atest,andajump.Thereisno
extrajugglingasthereisinmergesort.Thiscodeisstillsurprisinglytricky.Itistempting
toreplacelines16to25withthestatementsinFigure7.18.Thisdoesnotwork,because
therewouldbeaninfiniteloopif
a[i] = = a[j] ] = pivot
.
7.7.5 AnalysisofQuicksort
Likemergesort,quicksortisrecursive;therefore,itsanalysisrequiressolvingarecurrence
formula.Wewilldotheanalysisforaquicksort,assumingarandompivot(nomedian-
of-threepartitioning)andnocutoffforsmallarrays.WewilltakeT(0)=T(1)=1,asin
mergesort.Therunningtimeofquicksortisequaltotherunningtimeofthetworecursive
callsplusthelineartimespentinthepartition(thepivotselectiontakesonlyconstant
time).Thisgivesthebasicquicksortrelation
T(N)=T(i)+T(Ni−1)+cN
(7.1)
wherei=|S
1
|isthenumberofelementsinS
1
.Wewilllookatthreecases.
Worst-CaseAnalysis
Thepivotisthesmallestelement,allthetime.Then= 0,andifweignoreT(0)= 1,
whichisinsignificant,therecurrenceis
T(N)=T(N−1)+cNN>1
(7.2)
7.7 Quicksort
319
Wetelescope,usingEquation(7.2)repeatedly.Thus,
T(N−1)=T(N−2)+c(N−1)
(7.3)
T(N−2)=T(N−3)+c(N−2)
(7.4)
.
.
.
T(2)=T(1)+c(2)
(7.5)
Addingupalltheseequationsyields
T(N)=T(1)+c
N
i=2
i=(N
2
)
(7.6)
asclaimedearlier.Toseethatthisistheworstpossiblecase,notethatthetotalcostofall
thepartitionsinrecursivecallsatdepthdmustbeatmostN.Sincetherecursiondepthis
atmostN,thisgivesanO(N
2
)worst-caseboundforquicksort.
Best-CaseAnalysis
Inthebestcase,thepivotisinthemiddle.Tosimplifythemath,weassumethatthetwo
subarraysareeach exactlyhalfthesizeoftheoriginal,andalthoughthisgivesaslight
overestimate,thisisacceptablebecauseweareonlyinterestedinaBig-Ohanswer.
T(N)=2T(N/2)+cN
(7.7)
DividebothsidesofEquation(7.7)byN.
T(N)
N
=
T(N/2)
N/2
+c
(7.8)
Wewilltelescopeusingthisequation:
T(N/2)
N/2
=
T(N/4)
N/4
+c
(7.9)
T(N/4)
N/4
=
T(N/8)
N/8
+c
(7.10)
.
.
.
T(2)
2
=
T(1)
1
+c
(7.11)
Weaddalltheequationsfrom(7.8)to(7.11)andnotethattherearelogNofthem:
T(N)
N
=
T(1)
1
+clogN
(7.12)
whichyields
T(N)=cNlogN+N=(NlogN)
(7.13)
Noticethatthisistheexactsameanalysisasmergesort;hence,wegetthesameanswer.
ThatthisisthebestcaseisimpliedbyresultsinSection7.8.
320
Chapter7 Sorting
Average-CaseAnalysis
Thisisthemostdifficultpart.Fortheaveragecase,weassumethateachofthesizesforS
1
isequallylikely,andhencehasprobability1/N.Thisassumptionisactuallyvalidforour
pivotingandpartitioningstrategy,butitisnotvalidforsomeothers.Partitioningstrategies
thatdonotpreservetherandomnessofthesubarrayscannotusethisanalysis.Interestingly,
thesestrategiesseemtoresultinprogramsthattakelongertoruninpractice.
With this s assumption, the average value of T(i), and d hence T(− − − − 1), , is
(1/N)
N−1
j=0
T(j).Equation(7.1)thenbecomes
T(N)=
2
N
N−1
j=0
T(j)
+cN
(7.14)
IfEquation(7.14)ismultipliedbyN,itbecomes
NT(N)=2
N−1
j=0
T(j)
+cN
2
(7.15)
Weneedtoremovethesummationsigntosimplifymatters.Wenotethatwecantelescope
withonemoreequation:
(N−1)T(N−1)=2
N−2
j=0
T(j)
+c(N−1)
2
(7.16)
IfwesubtractEquation(7.16)fromEquation(7.15),weobtain
NT(N)−(N−1)T(N−1)=2T(N−1)+2cNc
(7.17)
Werearrangetermsanddroptheinsignificant−contheright,obtaining
NT(N)=(N+1)T(N−1)+2cN
(7.18)
WenowhaveaformulaforT(N)intermsofT(N−1)only.Againtheideaistotelescope,
butEquation(7.18)isinthewrongform.DivideEquation(7.18)byN(N+1):
T(N)
N+1
=
T(N−1)
N
+
2c
N+1
(7.19)
Nowwecantelescope.
T(N−1)
N
=
T(N−2)
N−1
+
2c
N
(7.20)
T(N−2)
N−1
=
T(N−3)
N−2
+
2c
N−1
(7.21)
.
.
.
T(2)
3
=
T(1)
2
+
2c
3
(7.22)
7.7 Quicksort
321
AddingEquations(7.19)through(7.22)yields
T(N)
N+1
=
T(1)
2
+2c
N+1
i=3
1
i
(7.23)
Thesumisaboutlog
e
(N+1)+γ−
3
2
,whereγ ≈0.577isknownasEuler’sconstant,so
T(N)
N+1
=O(logN)
(7.24)
Andso
T(N)=O(NlogN)
(7.25)
Althoughthisanalysisseemscomplicated,itreallyisnot—thestepsarenaturalonce
youhaveseensomerecurrencerelations.Theanalysiscanactuallybetakenfurther.The
highlyoptimizedversionthatwasdescribedabovehasalsobeenanalyzed,andthisresult
getsextremelydifficult,involvingcomplicatedrecurrencesandadvancedmathematics.The
effectofequalelementshasalsobeenanalyzedindetail,anditturnsoutthatthecode
presenteddoestherightthing.
7.7.6 ALinear-Expected-TimeAlgorithmforSelection
Quicksortcanbemodifiedtosolvetheselectionproblem,whichwehaveseeninChapters1
and6.Recallthatbyusingapriorityqueue,wecanfindthekthlargest(orsmallest)element
in O(N+klogN).Forthespecialcaseoffindingthemedian,thisgivesanO(NlogN)
algorithm.
SincewecansortthearrayinO(NlogN)time,onemightexpecttoobtainabetter
timeboundforselection.Thealgorithmwepresenttofindthekthsmallestelementina
setSisalmostidenticaltoquicksort.Infact,thefirstthreestepsarethesame.Wewill
callthisalgorithmquickselect.Let|S
i
|denotethenumberofelementsinS
i
.Thestepsof
quickselectare
1. If|S|=1,thenk=1andreturntheelementinSastheanswer.Ifacutoffforsmall
arraysisbeingusedand|S|≤
CUTOFF
,thensortSandreturnthekthsmallestelement.
2. Pickapivotelement,vS.
3. PartitionS−{v}intoS
1
andS
2
,aswasdonewithquicksort.
4. If ≤ ≤ |S
1
|, then n the kth h smallest t element t must be e in S
1
. In this s case, , return
quickselect(S
1
,k).If= 1+|S
1
|,thenthepivotis thekthsmallestelementand
wecanreturnitastheanswer.Otherwise,thekthsmallestelementliesinS
2
,andit
isthe(k−|S
1
|−1)stsmallestelementinS
2
.Wemakearecursivecallandreturn
quickselect(S
2
,k−|S
1
|−1).
Incontrasttoquicksort,quickselectmakesonlyonerecursivecallinsteadoftwo.The
worstcaseofquickselectisidenticaltothatofquicksortandisO(N
2
).Intuitively,thisis
becausequicksort’sworstcaseiswhenoneofS
1
andS
2
isempty;thus,quickselectisnot
Documents you may be interested
Documents you may be interested