程序设计与算法基础ppt课件.ppt

《程序设计与算法基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计与算法基础(5)潘爱民2006/10/23OutlineExternalsortingHuffmancodingtreeThefamilyofB-TreeTrieExternalsortingInternalsortingQuicksortbestaverageruntimeMergesortbestworst-caseruntimeInsertionsortingInternalmergesortPhase1CreateinitialsortedsegmentsPhase2Mergepairsofsortedsegments,inmer

2、gepasses,untilonly1segmentremainsExternalmergesortExternalMergesortSpacerequirementsandconstraintsSort10,000records.Enoughmemoryfor500records.Blocksizeis100records.TimetIO=timetoinput/output1block(includesseek,latency,andtransmissiontimes)tIS=timetointernallysort1memoryloadtI

3、M=timetointernallymerge1blockloadExternalMergeSortTwophasesRungenerationArunisasortedsequenceofrecordsRunmergingRunGenerationInput5blocks.Sort.Outputasarun.Do20times.5tIOtIS5tIO200tIO+20tISMemoryDISK500records10,000records5blocks100blocksComplexityisO(n)RunMergingMergePassPai

4、rwisemergethe20runsinto10.Inamergepassallruns(exceptpossiblyone)arepairwisemerged.Perform4moremergepasses,reducingthenumberofrunsto1Merge20RunsR1R2R3R4R5R6R7R8R9R10R11R12R13R14R15R16R17R18R19R20S1S2S3S4S5S6S7S8S9S10T1T2T3T4T5U1U2U3V1V2W1MergeR1andR2FillI0(Input0)fromR1andI1fr

5、omR2.MergefromI0andI1tooutputbuffer.Writewheneveroutputbufferfull.Readwheneverinputbufferempty.MemoryDISKInput0Input1OutputTimeToMergeR1andR2Eachis5blockslong.Inputtime=10tIO.Write/outputtime=10tIO.Mergetime=10tIM.Totaltime=20tIO+10tIM.TimeForPass1(RS)Timetomergeonepairofruns

6、20tIO+10tIM.Timetomergeall10pairsofruns=200tIO+100tIM.TimeToMergeS1andS2Eachis10blockslong.Inputtime=20tIO.Write/outputtime=20tIO.Mergetime=20tIM.Totaltime=40tIO+20tIM.TimeForPass2(ST)Timetomergeonepairofruns=40tIO+20tIM.Timetomergeall5pairsofruns=200tIO+100tIM.TimeForEachMer

7、gePassTimetoinputallblocks=100tIO.Timetooutputallblocks=100tIO.Timetomergeallblocks=100tIM.Totaltimeforamergepass=200tIO+100tIM.TotalRun-MergingTime(timeforonemergepass)*(numberofpasses)=(timeforonemergepass)*log2(numberofinitialruns)=(200tIO+100tIM)*log2(20)=(200tIO+100t

8、IM)*5ComplexityisO(nlogn)FactorsInOverallRunTimeRungeneration.200tIO