Rust Algorithm Ranking – Selection Sorting Illustration and Code Implementation

Iheardthatyouarealmostgettingmoldyfrombeingboredathome,sowhydon’tyoutrysomethingfresh?Concentrateandmaketimepassfaster!

Thefollowingisthesortingprocessandanimationdiagramfromthenovicetutorial:

First,findthesmallest(large)elementintheunsortedsequenceandstoreitatthestartingpositionofthesortedsequence.

Thencontinuetofindthesmallest(largest)elementfromtheremainingunsortedelements,andthenputitattheendofthesortedsequence.

Repeatuntilallelementsaresorted.

Let’stakealookatit.Themainlogicofselectionsortingis:

1. Theouterloopfirstspecifiesanumber,usuallythefirstnumber
2. Thenintheinnerloop,comparethenumberspecifiedintheouterloopwiththenumberontherightonebyone,andrecordthesmallestnumberamongthenumbersontheright.
3. Theleftsideisthesortedelements,sothecomparisonintheinnerloopistocontinuouslycomparethenumberspecifiedintheouterloopwiththeelementsontheright.
4. Duringtheinnerloop,everytimeanumbersmallerthanthenumberspecifiedintheouterloopisfound,itwillberecorded.Aftertheloopends,thenumberrecordedwillbethesmallestnumberontheright.
5. Aftertheinnerloopends,exchangethenumberspecifiedbytheouterloopwiththesmallestnumberontherightsideobtainedbytheinnerloop.
6. Andsoonuntiltheouterloopends

Nowwehaveasetofelementsthatneedtobesorted:

[7,21,9,13,109,9,2,50,33,-1,20,11]

Thelogicalouterloopofselectionsortspecifiesthefirstnumber7withindex0.Afterselection,theforloopwillstartloopingfromtheelementwithindex0.Thecodebehavesas:

foriin0..vectors.len(){}

Theforloopstartsfromthefirstnumber7atindex0.Intheinnerloop,comparethenumberspecifiedbytheouterloopwiththenumberontheright[21,9,13,109,9,2,50,33,-1,20,11]onebyone.WhenthenumberspecifiedbytheouterloopislessthantheelementontheleftRecordtheminimumvalue,andvectors[i]andvectors[j]exchangepositionsaftertheinnerloopends.Theminimumnumberinthisroundis-1,sotheelementgroupbecomes:

[-1,21,9,13,109,9,2,50,33,7,20,11]

Atthispoint,enterthenextouterloopandspecifythesecondnumber21withthesubscript1.Intheinnerloop,comparethenumberspecifiedbytheouterloopwiththenumberontheright[9,13,109,9,2,50,33,-1,20,11]onebyone.Whenthenumberspecifiedbytheouterloopislessthantheelementontheleft,recordtheminimumvalue,vectors[i]andvectors[j]exchangepositionsaftertheinnerloopends.Theminimumnumberinthisroundis2,sotheelementgroupbecomes:

[-1,2,21,13,109,9,9,50,33,7,20,11]

Byanalogywiththisrule,thefinalresultofelementsortingis:

[-1,2,7,9,9,11,13,20,21,33,50,109]

Specificcodeimplementation

Firstdefineasetofelementsandprint:

fnmain(){
letmutvectors=vec![7,21,9,13,109,9,2,50,33,-1,20,11];
println!("vectors:{:?}",vectors);
}

Thendefinethesortingmethod:

fninsert_sort(vectors:&mutVec<i32>)->&Vec<i32>{
vectors
}

Theouterloopofthesortmethodisaforloop:

fninsert_sort(vectors:&mutVec<i32>)->&Vec<i32>{
foriin0..vectors.len(){

}
vectors
}

Theindexhererepresentstheindexoftheminimumvalue:

fninsert_sort(vectors:&mutVec<i32>)->&Vec<i32>{
foriin0..vectors.len(){
letmutindex=i;
}
vectors
}

Intheinnerloop,thenumberspecifiedbytheouterloopiscomparedwiththenumberontherightonebyone.Whenthenumberspecifiedbytheouterloopislessthantheelementontheright,thesubscriptoftheelementontherightisrecorded,otherwiseitdoesnotmove.

Constantlycomparingwiththeelementsontherightisrepresentedbyforjini+1..vectors.len()andvectors[j]

Thesubscriptrecordcanactuallybereplacedbyexchange,sothatwhentheinnerforloopends,theindexmustbethesubscriptofthesmallandmediumelementontheright;

Youcannotexchangepositionslikea,b=b,ainPython.Youcanonlyusec=a,a=b,b=ctoaddathirdnumber.Thecodeisasfollows

fnselection_sort(vectors:&mutVec<i32>)->&Vec<i32>{
foriin0..vectors.len(){
//Findtheminimumvalueamongunsortedelements,thatis,theminimumelementin[i,n)
letmutindex=i;
forjini+1..vectors.len(){
ifvectors[j]<vectors[index]{
index=j;
}
}
letmiddle=vectors[index];
vectors[index]=vectors[i];
vectors[i]=middle;
}
vectors
}

Verificationoftheory

Theabovetheoryseemsreasonableandconvincing,butisitcorrect?

Wecandothisbyprintingtheroundnumber,minimumvalue,andcurrentelementgroupforeachroundduringprogramexecution.Thecodewiththeprintstatementaddedisasfollows:

fnselection_sort(vectors:&mutVec<i32>)->&Vec<i32>{
foriin0..vectors.len(){
//Findtheminimumvalueamongunsortedelements,thatis,theminimumelementin[i,n)
letmutindex=i;
forjini+1..vectors.len(){
ifvectors[j]<vectors[index]{
index=j;
}
}
println!("Thisisthe{}thround,minimumvalue:{},vectors:{:?}",i,vectors[index],vectors);
letmiddle=vectors[index];
vectors[index]=vectors[i];
vectors[i]=middle;
}
vectors
}

Theprintedresultafterrunningthecodeisasfollows:

Nowisround0,minimumvalue:-1,vectors:[7,21,9,13,109,9,2,50,33,-1,20,11]
Nowitisround1,minimumvalue:2,vectors:[-1,21,9,13,109,9,2,50,33,7,20,11]
Nowitisround2,minimumvalue:7,vectors:[-1,2,9,13,109,9,21,50,33,7,20,11]
Nowitisround3,minimumvalue:9,vectors:[-1,2,7,13,109,9,21,50,33,9,20,11]
Nowitisround4,minimumvalue:9,vectors:[-1,2,7,9,109,13,21,50,33,9,20,11]
Nowitisround5,minimumvalue:11,vectors:[-1,2,7,9,9,13,21,50,33,109,20,11]
Nowitisround6,minimumvalue:13,vectors:[-1,2,7,9,9,11,21,50,33,109,20,13]
Nowitisround7,minimumvalue:20,vectors:[-1,2,7,9,9,11,13,50,33,109,20,21]
Nowitisround8,minimumvalue:21,vectors:[-1,2,7,9,9,11,13,20,33,109,50,21]
Nowitisround9,minimumvalue:33,vectors:[-1,2,7,9,9,11,13,20,21,109,50,33]
Nowitisround10,minimumvalue:50,vectors:[-1,2,7,9,9,11,13,20,21,33,50,109]
Nowisthe11thround,minimumvalue:109,vectors:[-1,2,7,9,9,11,13,20,21,33,50,109]

Itcanbeseenthatthedescriptioninthetheoreticalpartiscorrect,thatis,eachroundtheminimumvalueintheright-handelementisexchangedwiththepositionofthecurrentroundelement.

ThecompleteRustselectionsortcodeisasfollows:

Rustalgorithmcoderepositoryaddressgithub.com/asyncins/ac…

Author:HuaweiCloudEnjoymentExpertWeiShidong