332
Chapter7 Sorting
makedecisionsbasedonorderinginformationonly.Naturally,ifthereisextrainformation
available,weshouldexpecttofindamoreefficientalgorithm,sinceotherwisetheextra
informationwouldbewasted.
Althoughbucketsortseemslikemuchtootrivialanalgorithmtobeuseful,itturnsout
thattherearemanycaseswheretheinputisonlysmallintegers,sothatusingamethod
likequicksortisreallyoverkill.Onesuchexampleisradixsort.
Radixsortissometimesknownascardsortbecauseitwasuseduntiltheadventof
moderncomputerstosortold-stylepunchcards.Supposewehave10numbersinthe
range0to999thatwewouldliketosort.IngeneralthisisNnumbersintherange0to
b
p
−1forsomeconstantp.Obviouslywecannotusebucketsort;therewouldbetoomany
buckets.Thetrickistouseseveralpassesofbucketsort.Thenaturalalgorithmwouldbe
tobucketsortbythemostsignificant“digit”(digitistaken tobaseb),thennextmost
significant,andsoon.Butasimplerideaistoperformbucketsortsinthereverseorder,
starting with theleastsignificant“digit”first.Ofcourse,morethanonenumbercould
fallintothesamebucket,andunliketheoriginalbucketsort,thesenumberscouldbe
different,sowekeeptheminalist.Eachpassisstable:Itemsthatagreeinthecurrentdigit
retaintheorderingdeterminedinpriorpasses.ThetraceinFigure7.24showstheresult
ofsorting64,8,216,512,27,729,0,1,343,125,whichisthefirsttencubesarranged
randomly(weuse0stomakeclearthetensandhundredsdigits).Afterthefirstpass,the
itemsaresortedontheleastsignificantdigit,andingeneral,afterthekthpass,theitems
aresortedonthekleastsignificantdigits.Soattheend,theitemsarecompletelysorted.
Toseethatthealgorithmworks,noticethattheonlypossiblefailurewouldoccuriftwo
numberscameoutofthesamebucketinthewrongorder.Butthepreviouspassesensure
thatwhenseveralnumbersenterabucket,theyenterinsortedorderaccordingtothek-1
leastsignificantdigits.TherunningtimeisO(p(N+b))wherepisthenumberofpasses,
Nisthenumberofelementstosort,andbisthenumberofbuckets.
Oneapplicationofradixsortissortingstrings.Ifallthestringshavethesamelength
L,thenby using bucketsforeach character,wecanimplementaradix sortinO(NL)
time.ThemoststraightforwardwayofdoingthisisshowninFigure7.25.Inourcode,
weassumethatallcharactersareASCII,residinginthefirst256positionsoftheUnicode
characterset.Ineachpass,weaddanitemtotheappropriatebucket,andthenafterallthe
bucketsarepopulated,westepthroughthebucketsdumpingeverythingbacktothearray.
Noticethatwhenabucketispopulatedandemptiedinthenextpass,theorderfromthe
currentpassispreserved.
Countingradixsortisanalternativeimplementationofradixsortthatavoidsusing
vector
storepresentbuckets.Instead,wemaintainacountofhowmanyitemswouldgo
ineachbucket;thisinformationcangointoanarray
count
,sothat
count[k]
isthenumber
ofitemsthatarein bucket
k
.Thenwecanuseanotherarray
offset
,sothat
offset[k]
INITIALITEMS:
064,008,216,512,027,729,000,001,343,125
SORTEDBY1’sdigit:
000,001,512,343,064,125,216,027,008,729
SORTEDBY10’sdigit:
000,001,008,512,216,125,027,729,343,064
SORTEDBY100’sdigit:
000,001,008,027,064,125,216,343,512,729
Figure7.24 Radixsorttrace
Convert pdf to editable ppt - 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
pdf to ppt converter; converting pdf to ppt online
Convert pdf to editable ppt - 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 convert pdf to ppt for; convert pdf file to ppt online
7.11 Linear-TimeSorts:BucketSortandRadixSort
333
1
/*
2
* Radix x sort t an n array of Strings
3
* Assume e all l are e all l ASCII
4
* Assume e all l have same e length
5
*/
6
void radixSortA( vector<string> & arr, int stringLen )
7
{
8
const int t BUCKETS = = 256;
9
vector<vector<string>> buckets( ( BUCKETS S );
10
11
for( int pos = = stringLen n - 1; pos s >= 0; --pos s )
12
{
13
for( string & & s s : arr r )
14
buckets[ s[ pos ] ] ].push_back( ( std::move( s ) );
15
16
int idx = 0;
17
for( auto & thisBucket : : buckets )
18
{
19
for( string & s : : thisBucket )
20
arr[ idx++ + ] ] = std::move( s s );
21
22
thisBucket.clear( );
23
}
24
}
25
}
Figure7.25 Simple implementation n of f radix sort t for r strings, using g an ArrayList
ofbuckets
representsthenumberofitemswhosevalueisstrictlysmallerthan
k
.Thenwhenwesee
avalue
k
forthefirsttimeinthefinalscan,
offset[k]
tellsusavalidarrayspotwhereit
canbewrittento(butwehavetouseatemporaryarrayforthewrite),andafterthatis
done,
offset[k]
canbeincremented.Countingradixsortthusavoidstheneedtokeep
lists.Asafurtheroptimization,wecanavoidusing
offset
byreusingthe
count
array.The
modificationisthatweinitiallyhave
count[k+1]
representthenumberofitemsthatarein
bucket
k
.Thenafterthatinformationiscomputed,wecanscanthe
count
arrayfromthe
smallesttolargestindexandincrement
count[k]
by
count[k-1]
.Itiseasytoverifythatafter
thisscan,thecountarraystoresexactlythesameinformationthatwouldhavebeenstored
in
offset
.
Figure7.26showsanimplementationofcountingradixsort.Lines18to27implement
thelogicabove,assumingthattheitemsarestoredinarray
in
andtheresultofasinglepass
isplacedinarray
out
.Initially,
in
represents
arr
and
out
representsthetemporaryarray,
buffer
.Aftereachpass,weswitchtherolesof
in
and
out
.Ifthereareanevennumberof
passes,thenattheend,
out
isreferencing
arr
,sothesortiscomplete.Otherwise,wehave
tomovefromthe
buffer
backinto
arr
.
Online Convert PDF to Text file. Best free online PDF txt
RasterEdge PDF document conversion SDK provides reliable and effective .NET solution for Visual C# developers to convert PDF document to editable & searchable
convert pdf slides to powerpoint; create powerpoint from pdf
334
Chapter7 Sorting
1
/*
2
* Counting radix sort an array y of Strings
3
* Assume e all l are all ASCII
4
* Assume e all l have same e length
5
*/
6
void countingRadixSort( vectro<string> > & arr, , int t stringLen )
7
{
8
const int t BUCKETS = = 256;
9
10
int N N = = arr.size( );
11
vector<string> buffer( ( N N );
12
13
vector<string> *in n = = &arr;
14
vector<string> *out t = = &buffer;
15
16
for( int t pos s = stringLen n - - 1; pos >= 0; --pos )
17
{
18
vector<int> count( ( BUCKETS + + 1 );
19
20
for( int t i = = 0; i i < N; ++i i )
21
++count[ (*in)[ [ i ] ] [ [ pos ] ] + + 1 ];
22
23
for( int t b = = 1; b b <= BUCKETS; ++b )
24
count[ b b ] ] += count[ b b - - 1 ];
25
26
for( int t i = = 0; i i < N; ++i i )
27
(*out)[ count[ [ (*in)[ [ i ] [ [ pos s ] ] ]++ + ] = = std::move( (*in)[ [ i ] ] );
28
29
// swap p in n and d out roles
30
std::swap( in, out t );
31
}
32
33
// if odd number of passes, in n is buffer, out t is arr; so move back
34
if( stringLen % 2 == 1 1 )
35
for( int t i = = 0; i i < arr.size( ); ++i )
36
(*out)[ i ] ] = = std::move( (*in)[ i i ] ] );
37
}
Figure7.26 Countingradixsortforfixed-lengthstrings
Generally,countingradixsortisprefereabletousing
vector
stostorebuckets,butit
cansufferfrompoorlocality(
out
isfilledinnon-sequentially)andthus,surprisingly,itis
notalwaysfasterthanusinga
vector
of
vector
s.
Wecanextendeitherversionofradixsorttoworkwithvariable-lengthstrings.The
basicalgorithmistofirstsortthestringsbytheirlength.Insteadoflookingatallthestrings,
7.11 Linear-TimeSorts:BucketSortandRadixSort
335
1
/*
2
* Radix x sort t an n array of Strings
3
* Assume e all l are e all l ASCII
4
* Assume e all l have length h bounded by maxLen
5
*/
6
void radixSort( ( vector<string> > & & arr, int t maxLen n )
7
{
8
const int t BUCKETS = = 256;
9
10
vector<vector<string>> wordsByLength( ( maxLen n + + 1 );
11
vector<vector<string>> buckets( ( BUCKETS S );
12
13
for( string g & & s : : arr r )
14
wordsByLength[ s.length( ( ) ) ].push_back( std::move( s ) ) );
15
16
int idx x = = 0;
17
for( auto o & & wordList : : wordsByLength )
18
for( string & & s s : wordList )
19
arr[ idx++ ] = = std::move( s s );
20
21
int startingIndex = = arr.size( );
22
for( int pos = = maxLen n - 1; pos >= = 0; --pos s )
23
{
24
startingIndex -= = wordsByLength[ pos s + + 1 ].size( );
25
26
for( int i i = = startingIndex; i i < < arr.size( ); ++i i )
27
buckets[ arr[ i ][ pos ] ].push_back( std::move( arr[ i i ] ] ) );
28
29
idx = = startingIndex;
30
for( auto & thisBucket : : buckets )
31
{
32
for( string & s : : thisBucket )
33
arr[ idx++ + ] ] = std::move( s s );
34
35
thisBucket.clear( );
36
}
37
}
38
}
Figure7.27 Radixsortforvariable-lengthstrings
wecanthenlookonlyatstringsthatweknowarelongenough.Sincethestringlengths
aresmallnumbers,theinitialsortbylengthcanbedoneby—bucketsort!Figure7.27
showsthisimplementationofradixsort,with
vector
stostorebuckets.Here,thewordsare
groupedintobucketsbylengthatlines13and14andthenplacedbackintothearrayat
lines16to19.Lines26and27lookatonlythosestringsthathaveacharacteratposition
336
Chapter7 Sorting
pos
,bymakinguseofthevariable
startingIndex
,whichismaintainedatlines21and24.
Exceptforthat,lines21to37inFigure7.27arethesameaslines11to24inFigure7.25.
The running g time e of this version n of radix sort is linear in the e total number r of
characters in all the strings (each h character r appears exactly onceat line 27,and the
statement at line33 executes precisely as many timesas the line27). Radix sort for
strings willperform especially wellwhen the characters in the string aredrawn from
a reasonably small l alphabet t and when the strings either r are relatively y short or are
verysimilar.BecausetheO(NlogN)comparison-basedsortingalgorithmswillgenerally
look only y at t a small numberof characters in each string comparison, once theaver-
agestringlength startsgetting large,radix sort’sadvantageisminimizedorevaporates
completely.
7.12 ExternalSorting
Sofar,allthealgorithmswehaveexaminedrequirethattheinputfitintomainmemory.
Thereare,however,applicationswheretheinputismuchtoolargetofitintomemory.This
sectionwilldiscussexternalsortingalgorithms,whicharedesignedtohandleverylarge
inputs.
7.12.1 WhyWeNeedNewAlgorithms
Mostoftheinternalsortingalgorithmstakeadvantageofthefactthatmemoryisdirectly
addressable.Shellsortcompareselements
a[i]
and
a[i-h
k
]
in onetimeunit.Heapsort
compareselements
a[i]
and
a[i
*
2+1]
inonetimeunit.Quicksort,withmedian-of-three
partitioning,requirescomparing
a[left]
,
a[center]
,and
a[right]
inaconstantnumber
oftimeunits.Iftheinputisonatape,thenalltheseoperationslosetheirefficiency,since
elementsonatapecanonlybeaccessedsequentially.Evenifthedataareonadisk,there
isstillapracticallossofefficiencybecauseofthedelayrequiredtospinthediskandmove
thediskhead.
Toseehowslowexternalaccessesreallyare,createarandomfilethatislarge,butnot
toobigtofitinmainmemory.Readthefileinandsortitusinganefficientalgorithm.The
timeittakestoreadtheinputiscertaintobesignificantcomparedtothetimetosortthe
input,eventhoughsortingisanO(NlogN)operationandreadingtheinputisonlyO(N).
7.12.2 ModelforExternalSorting
Thewidevarietyofmassstoragedevicesmakesexternalsortingmuchmoredevicedepen-
dentthan internalsorting.Thealgorithmsthatwewillconsiderworkon tapes,which
areprobablythemostrestrictivestoragemedium.Sinceaccesstoanelementontapeis
donebywindingthetapetothecorrectlocation,tapescanbeefficientlyaccessedonlyin
sequentialorder(ineitherdirection).
Wewillassumethatwehaveatleastthreetapedrivestoperformthesorting.Weneed
twodrivestodoanefficientsort;thethirddrivesimplifiesmatters.Ifonlyonetapedrive
ispresent,thenweareintrouble:Anyalgorithmwillrequire(N
2
)tapeaccesses.
7.12 ExternalSorting
337
7.12.3 TheSimpleAlgorithm
Thebasicexternalsortingalgorithmusesthemergingalgorithmfrommergesort.Suppose
we have four tapes, T
a1
T
a2
T
b1
T
b2
, which are two input t and two o output t tapes.
Dependingonthepointinthealgorithm,theaandbtapesareeitherinputtapesoroutput
tapes.SupposethedataareinitiallyonT
a1
.Supposefurtherthattheinternalmemorycan
hold(andsort)Mrecordsatatime.AnaturalfirststepistoreadMrecordsatatimefrom
theinputtape,sorttherecordsinternally,andthenwritethesortedrecordsalternatelyto
T
b1
andT
b2
.Wewillcalleachsetofsortedrecordsarun.Whenthisisdone,werewind
allthetapes.SupposewehavethesameinputasourexampleforShellsort.
T
a1
81
94
11
96
12
35
17
99
28
58
41
75
15
T
a2
T
b1
T
b2
IfM=3,thenaftertherunsareconstructed,thetapeswillcontainthedataindicatedin
thefollowingfigure.
T
a1
T
a2
T
b1
11
81
94
17
28
99
15
T
b2
12
35
96
41
58
75
NowT
b1
andT
b2
containagroupofruns.Wetakethefirstrunfromeachtapeand
mergethem,writingtheresult,whichisaruntwiceaslong,ontoT
a1
.Recallthatmerging
twosortedlistsissimple;weneedalmostnomemory,sincethemergeisperformedasT
b1
andT
b2
advance.Thenwetakethenextrunfromeachtape,mergethese,andwritethe
resulttoT
a2
.Wecontinuethisprocess,alternatingbetweenT
a1
andT
a2
,untileitherT
b1
or
T
b2
isempty.Atthispointeitherbothareemptyorthereisonerunleft.Inthelattercase,
wecopythisruntotheappropriatetape.Werewindallfourtapesandrepeatthesame
steps,thistimeusingtheatapesasinputandthebtapesasoutput.Thiswillgiverunsof
4M.WecontinuetheprocessuntilwegetonerunoflengthN.
Thisalgorithmwillrequirelog(N/M)passes,plustheinitialrun-constructingpass.
Forinstance,ifwehave10millionrecords of128byteseach,and fourmegabytesof
internalmemory,thenthefirstpasswillcreate320runs.Wewouldthenneedninemore
passestocompletethesort.Ourexamplerequireslog13/3=3morepasses,whichare
showninthefollowingfigures:
T
a1
11
12
35
81
94
96
15
T
a2
17
28
41
58
75
99
T
b1
T
b2
338
Chapter7 Sorting
T
a1
T
a2
T
b1
11
12
17
28
35
41
58
75
81
94
96
99
T
b2
15
T
a1
11
12
15
17
28
35
41
58
75
81
94
96
99
T
a2
T
b1
T
b2
7.12.4 MultiwayMerge
Ifwehaveextratapes,thenwecanexpecttoreducethenumberofpassesrequiredtosort
ourinput.Wedothisbyextendingthebasic(two-way)mergetoak-waymerge.
Mergingtworunsisdonebywindingeachinputtapetothebeginningofeachrun.
Thenthesmallerelementisfound,placedonanoutputtape,andtheappropriateinput
tapeisadvanced.Iftherearekinputtapes,thisstrategyworksthesameway,theonly
differencebeingthatitisslightlymorecomplicatedtofindthesmallestofthekelements.
Wecanfindthesmallestoftheseelementsbyusingapriorityqueue.Toobtainthenext
elementtowriteontheoutputtape,weperforma
deleteMin
operation.Theappropriate
inputtapeisadvanced,andiftherunontheinputtapeisnotyetcompleted,we
insert
thenewelementintothepriorityqueue.Usingthesameexampleasbefore,wedistribute
theinputontothethreetapes.
T
a1
T
a2
T
a3
T
b1
11
81
94
41
58
75
T
b2
12
35
96
15
T
b3
17
28
99
Wethenneedtwomorepassesofthree-waymergingtocompletethesort.
T
a1
11
12
17
28
35
81
94
96
99
T
a2
15
41
58
75
T
a3
T
b1
T
b2
T
b3
7.12 ExternalSorting
339
T
a1
T
a2
T
a3
T
b1
11
12
15
17
28
35
41
58
75
81
94
96
99
T
b2
T
b3
Aftertheinitialrunconstructionphase,thenumberofpassesrequiredusingk-way
mergingislog
k
(N/M),becausetherunsgetktimesaslargeineachpass.Fortheexample
above,theformulaisverified,sincelog
3
(13/3)= 2.Ifwehave10tapes,thenk=5,
andourlargeexamplefromtheprevioussectionwouldrequirelog
5
320=4passes.
7.12.5 PolyphaseMerge
Thek-waymergingstrategydevelopedin thelastsectionrequirestheuseof2tapes.
Thiscouldbeprohibitiveforsomeapplications.Itispossibletogetbywithonlyk+1
tapes.Asanexample,wewillshowhowtoperformtwo-waymergingusingonlythree
tapes.
Supposewehavethreetapes,T
1
,T
2
,andT
3
,andaninputfileonT
1
thatwillproduce
34runs.Oneoptionistoput17runsoneachofT
2
andT
3
.Wecouldthenmergethis
resultontoT
1
,obtainingonetapewith17runs.Theproblemisthatsincealltherunsare
ononetape,wemustnowputsomeoftheserunsonT
2
toperformanothermerge.The
logicalwaytodothisistocopythefirsteightrunsfromT
1
ontoT
2
andthenperformthe
merge.Thishastheeffectofaddinganextrahalfpassforeverypasswedo.
Analternativemethodistosplittheoriginal34runsunevenly.Supposeweput21runs
onT
2
and13runsonT
3
.Wewouldthenmerge13runsontoT
1
beforeT
3
wasempty.At
thispoint,wecouldrewindT
1
andT
3
,andmergeT
1
,with13runs,andT
2
,whichhas
8runs,ontoT
3
.Wecouldthenmerge8runsuntilT
2
wasempty,whichwouldleave5runs
leftonT
1
and8runsonT
3
.WecouldthenmergeT
1
andT
3
,andsoon.Thefollowing
tableshowsthenumberofrunsoneachtapeaftereachpass:
Run
After
After
After
After
After
After
After
Const. T
3
+T
2
T
1
+T
2
T
1
+T
3
T
2
+T
3
T
1
+T
2
T
1
+T
3
T
2
+T
3
T
1
0
13
5
0
3
1
0
1
T
2
21
8
0
5
2
0
1
0
T
3
13
0
8
3
0
2
1
0
Theoriginaldistributionofrunsmakesagreatdealofdifference.Forinstance,if22
runsareplacedonT
2
,with12onT
1
,thenafterthefirstmerge,weobtain12runsonT
3
and10runsonT
2
.Afteranothermerge,thereare10runsonT
1
and2runsonT
3
.At
thispointthegoinggetsslow,becausewecanonlymergetwosetsofrunsbeforeT
3
is
exhausted.ThenT
1
has8runsandT
2
has2runs.Again,wecanonlymergetwosetsof
runs,obtainingT
1
with6runsandT
3
with2runs.Afterthreemorepasses,T
2
hastwo
340
Chapter7 Sorting
runsandtheothertapesareempty.Wemustcopyoneruntoanothertape,andthenwe
canfinishthemerge.
Itturnsoutthatthefirstdistributionwegaveisoptimal.Ifthenumberofrunsis
aFibonaccinumberF
N
,thenthebestwaytodistributethemistosplitthemintotwo
FibonaccinumbersF
N−1
andF
N−2
.Otherwise,itisnecessarytopadthetapewithdummy
runsinordertogetthenumberofrunsuptoaFibonaccinumber.Weleavethedetailsof
howtoplacetheinitialsetofrunsonthetapesasanexercise.
Wecanextendthistoak-waymerge,inwhichcaseweneedkth orderFibonacci
numbersforthedistribution,wherethekthorderFibonaccinumberisdefinedasF
(k)
(N)=
F
(k)
(N−1)+F
(k)
(N−2)+···+F
(k)
(Nk),with theappropriateinitialconditions
F
(k)
(N)=0,0≤Nk−2,F
(k)
(k−1)=1.
7.12.6 ReplacementSelection
Thelastitemwewillconsiderisconstructionoftheruns.Thestrategywehaveusedsofar
isthesimplestpossible:Wereadasmanyrecordsaspossibleandsortthem,writingthe
resulttosometape.Thisseemslikethebestapproachpossible,untilonerealizesthatas
soonasthefirstrecordiswrittentoanoutputtape,thememoryitusedbecomesavailable
foranotherrecord.Ifthenextrecordontheinputtapeislargerthantherecordwehave
justoutput,thenitcanbeincludedintherun.
Usingthisobservation,wecangiveanalgorithmforproducingruns.Thistechniqueis
commonlyreferredtoasreplacementselection.Initially,Mrecordsarereadintomemory
andplacedin apriorityqueue.Weperforma
deleteMin
,writingthesmallest(valued)
recordtotheoutputtape.Weread thenextrecord fromtheinputtape.Ifitislarger
thantherecordwehavejustwritten,wecanaddittothepriorityqueue.Otherwise,it
cannotgointothecurrentrun.Sincethepriorityqueueissmallerbyoneelement,wecan
storethisnewelementinthedeadspaceofthepriorityqueueuntiltheruniscompleted
andusetheelementforthenextrun.Storinganelementinthedeadspaceissimilar
towhatisdoneinheapsort.Wecontinuedoingthisuntilthesizeofthepriorityqueue
iszero,atwhichpointtherunisover.Westartanewrunbybuildinganewpriority
queue,usingalltheelementsinthedeadspace.Figure7.28showstherunconstruction
forthesmallexamplewehavebeenusing,withM=3.Deadelementsareindicatedbyan
asterisk.
Inthisexample,replacementselectionproducesonlythreeruns,comparedwiththe
fiverunsobtainedby sorting.Becauseof this,athree-way mergefinishesin onepass
insteadoftwo.Iftheinputisrandomlydistributed,replacementselectioncanbeshown
toproducerunsofaveragelength2M.Forourlargeexample,wewouldexpect160runs
insteadof320runs,soafive-waymergewouldrequirefourpasses.Inthiscase,wehave
notsavedapass,althoughwemightifwegetluckyandhave125runsorless.Since
externalsortstakesolong,everypasssavedcanmakeasignificantdifferenceintherunning
time.
Aswehaveseen,itispossibleforreplacementselectiontodonobetterthanthestan-
dardalgorithm.However,theinputisfrequentlysortedornearlysortedtostartwith,in
whichcasereplacementselectionproducesonlyafewverylongruns.Thiskindofinput
iscommonforexternalsortsandmakesreplacementselectionextremelyvaluable.
Exercises
341
3ElementsinHeapArray
Output
NextElementRead
h[1]
h[2]
h[3]
Run1
11
94
81
11
96
81
94
96
81
12*
94
96
12*
94
35*
96
35*
12*
96
17*
17*
35*
12*
EndofRun
RebuildHeap
Run2
12
35
17
12
99
17
35
99
17
28
28
99
35
28
58
35
99
58
35
41
41
99
58
41
15*
58
99
15*
58
EndofTape
99
15*
99
15*
EndofRun
RebuildHeap
Run3
15
15
Figure7.28 Exampleofrunconstruction
Summary
Sortingisoneoftheoldestandmostwell-studiedproblemsincomputing.Formostgeneral
internalsortingapplications,aninsertionsort,Shellsort,mergesort,orquicksortisthe
methodofchoice.Thedecisionregardingwhichtousedependsonthesizeoftheinput
andontheunderlyingenvironment.Insertionsortisappropriateforverysmallamounts
ofinput.Shellsortisagoodchoiceforsortingmoderateamountsofinput.Withaproper
incrementsequence,itgivesexcellentperformanceand usesonly afew linesofcode.
MergesorthasO(NlogN)worst-caseperformancebutrequiresadditionalspace.However,
thenumberofcomparisonsthatareusedisnearlyoptimal,becauseanyalgorithmthat
sortsbyusingonlyelementcomparisonsmustuseatleastlog(N!)comparisonsforsome
inputsequence.Quicksortdoesnotbyitselfprovidethisworst-caseguaranteeandistricky
tocode.However,ithasalmostcertainO(NlogN)performanceandcanbecombinedwith
heapsorttogiveanO(NlogN)worst-caseguarantee.Stringscanbesortedinlineartime
usingradixsort,andthismaybeapracticalalternativetocomparison-basedsortsinsome
instances.
Exercises
7.1
Sortthesequence3,1,4,1,5,9,2,6,5usinginsertionsort.
7.2
Whatistherunningtimeofinsertionsortifallelementsareequal?
Documents you may be interested
Documents you may be interested