第15次上机作业题目

《第15次上机作业题目》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、RadixSortandUsageofSTLSortAlgorithmPrerequisites,Goals,andOutcomesPrerequisites:Studentsshouldhavemasteredthefollowingprerequisiteskills.•RadixSort-Knowledgeoftheradixsortalgorithm•C++STL-BasicknowledgeoftheusageofC++STL•C++functionpointer-BasicKnowledgeofC++functionpointerGoals:Thi

2、sassignmentisdesignedtoreinforcethestudentsunderstandingofradixsortwithtimecomplexity0(/?).Andalsoasthefinalassignmentofsortalgorithm,thestudentsshouldmastertheusageofSTLsortalgorithm.Outcomes:Studentssuccessfullycompletingthisassignmentwouldmasterthefollowingoutcomes.•Understandthe

3、lineartimesortalgorithm•MastertheusageofSTLsortalgorithmBackgroundRadixSortRadixsortfollowsthenon-intuitiveorderofsortingontheleastsignificantfeaturefirstandrecombiningallthelistsimmediatelyaftereachcompletedsplitting.Forinstanceifkeyswere5digitnumbers,thesortcouldfirstbeontheVsdigi

4、t,thenthe10'sdigit,…andfinallythemostsignificantdigit,the10,000'sdigit.Theonlyrequirementtohavethisworkisthesplittingandrecombiningoperationsmakekeysthatgointhesamebucketendupinthesamerelativeorderasthestarted(i.e.bestable).Dosmallexample:forsimplicityonly3possiblevaluesineachplaceI

5、nitialdatafirstpasssecondpasslastpasscombined123231111111111222111312113113312121113121121113++123123231222121+222111312222222231333+123231312121123++333113231312333333333STLSortAlgorithmTheheaderdefinesacollectionoffunctionsespeciallydesignedtobeusedonrangesofelements.Ar

6、angeisanysequenceofobjectsthatcanbeaccessedthroughiteratorsorpointers,suchasanarrayoraninstanceofsomeoftheSTLcontainers・Noticethough,thatalgorithmsoperatethroughiteratorsdirectlyonthevalues,notaffectinginanywaythestructureofanypossiblecontainer(itneveraffectsthesizeorstorageallocati

7、onofthecontainer)・TherearefivesortalgorithmsinSTL,andthefunctionprototypesarelistedbelow:sortSortelementsinrange(functiontemplate)stablesortSortelementspreservingorderofequivalents(functiontemplate)partialsortPartiallySortelementsinrange(functiontemplate)partialsortcopyCopyandpartia

8、llysortrange(functi