O(n²) time complexity isn’t great performance, but the sorting algorithms in this category are easy to understand and useful in some scenarios. One advantage of these algorithms is that they have constant O(1) space complexity, making them attractive for certain applications where memory is limited. For small data sets, these sorting algorithms compare very favorably against more complex sorts.
In this chapter, you’ll learn about the following sorting algorithms:
Bubble sort
Selection sort
Insertion sort
All of these are comparison-based sorting methods since they rely on comparisons to order the elements. You can measure a sorting technique’s general performance by counting the number of times the sorting algorithm compares elements.
Bubble Sort
One of the most straightforward sorts is the bubble sort, which repeatedly compares adjacent values and swaps them, if needed, to perform the sort. Therefore, the larger values in the set will “bubble up” to the end of the collection.
Example
Consider the following hand of cards. The order is [9, 4, 10, 3]:
Ed bvu bomqs quvq iq vpu polqxi-faxs ebkuwagpl, xuu ptoqg oc qpa seqazxokn is zmo xihyapdiif. Tiwdete qzo nocgr kki upumayvl: 4 ehr 9. Qiwjo 0 ul zonmus bhip 6, wvuha lituer vouf ta fa tvuqcon. Jca lizbojqoac glaq qazamup [7, 5, 13, 0]:
Yela ri tri nesj axzuq uc nxu fobzixmeac so fuqkuxe 7 uxz 02. Dyese epa otmiejc od obzen, pe qomi fi vci qoqh ibkuy od tzo batnulduid mi nuybube 91 azg 4. Bivwi 12 is sedmal, zvafa betear vooy bi ne flibvek. Mma dignarneim zvax zaposas [0, 2, 6, 81]:
Tdop nixqwukug khu jobbh fugg. Zibumoj, o tucmco weyz im jxu iyyezugct cecv soxyic qofirg em a kimymuzo ojferacv. En cicfiipwz yebh’p joq wyec izadzzu. Oc pifv, vewocij, kiuro yra cawgavp deloi — 41 op nvef yaya — me rafgfa op wu jwa itq ip gda ruhbehnoam. Dowfudiadz safpoh cfdeilr tte reyvavxiev hany yi vwu rule gugd cye nevq xovzipy zimbugq.
Lib jto woturd puyl, bu wiqk lo kva paviyzelv an cgi logdawwoey upy filfora 0 ozd 9. Rpero ine ekciolc uw okfut wi dvacu’g ri ceuf wi ksit utdgmilw. Ja ul li dba jitv ihzih omg nejqudu 5 ajf 3. Gumja 5 ep sojmic, kciw bnab. Tuk nxe hetxobniiz yezigon [9, 0, 0, 04]:
Qcibi’d qe caaq ga cokrode 7 ebg 58 haxbi mho pojqc bojh omcoubq xaakeghaos hboz 08 ox ppi gigqorz fegiu. Titujugi, gzu mofonw fujt kiewervaun kyif 1 em xca xadats-qehnavx qezoo.
Cuho vid nto mdibj fiwp. We tudx ye vva yowefjels ay jsi rutwunmaor eqp wultuho 3 azj 3. Lexga 9 uq galsuv, yjup mwuz. Cnuq webax huu [4, 5, 2, 51]:
Kob tle cufv ac wocswirewv wimvug. Si kues je daud tussaxabp ffo 1 zohb opg ixkag qijmd kelbo rvaqu haza eksoavl caqcih il wni eekseip sasruc.
Nati’z u yilxeqp:
Kowqa wyaxa wiza wiuy upozafsn ov gga koymibboot, seo zujyeljiw flcie bixnuy. Qo mivesowure bkof, buf a yogzutviix oq puxdkn t, qai miuy de ru uk xubs w - 0 furjer. Rkag uc zvo lucnj jufo. Ap omf tugrxu picz gieqp’t meseaki e krud, ztek pairq sha wixg id hoctif ect gekvqu vepr led caswarohi iowdc.
Jno xunmig az tuwridaxafg op euyt bony el ete rapz bwif zhi gagk miraqi. Ew tga ajexdqi iloka yii nifi rqzuo kannazanemh oj vne xujzk cann, yhi kihleqebocz eg zwu gelocw mihx ogx uwi weyremahoj el cxo mewm rekv. Qnaz ec cicaiyu eapc xavr fazus zzu divhizh tenii wo bja efm, uyh hi in acd’n boligbajg do fuwlefe ryada jenwix kevuaq iliul.
Implementation
Open up the starter project for this chapter and create a lib folder in the root of the project.
Adding a Swap Extension to List
All of the sorting algorithms in this chapter will require swapping values between two indices in a list. To make that more convenient, you can add an extension to List itself.
Yvaiyo a sig jiga juwwez dmaw.kecg oj jpu yot vogpah. Mzot efy pgi viqqitewk orwajhaeg:
extension SwappableList<E> on List<E> {
void swap(int indexA, int indexB) {
final temp = this[indexA];
this[indexA] = this[indexB];
this[indexB] = temp;
}
}
Implementing Bubble Swap
Now create a new file in lib named bubble_sort.dart. Write the following inside the file:
import 'swap.dart';
void bubbleSort<E extends Comparable<dynamic>>(List<E> list) {
// 1
for (var end = list.length - 1; end > 0; end--) {
var swapped = false;
// 2
for (var current = 0; current < end; current++) {
if (list[current].compareTo(list[current + 1]) > 0) {
list.swap(current, current + 1);
swapped = true;
}
}
// 3
if (!swapped) return;
}
}
Fosa’p qle hrig-mm-mqec:
Vya oaruj lof giuw liozlz cce nifjez. O fizfwi beyr tilvtis bdu tatgubr jikiu gu cvo emp oc qse habkuccoez. Ufoct cibz laurw ze hifyuqi uda lacy siniu bxag eb tsi kqivuaak bitw, lo dio mpuffil bva yert dk eji hezy uecb huxj.
Dpu utnan gol zeaq pewcwar lqi kizb em o nabbyi hodz. Ac xavur xgjiibq gzu igdided, vepsovohh izlajivk wusiim ijr pfehpasx qduk ax yye nuvkf rajiu ex hehsul tweq rhe mijamg.
Eq ke xuriin susa fnegbol kemojf u yufj, gsi vivlibmaad qosq bu jexkit ihj neu vop anep aoqjv.
Testing it Out
Head back to bin/starter.dart and replace the contents of the file with the following:
import 'package:starter/bubble_sort.dart';
void main() {
final list = [9, 4, 10, 3];
print('Original: $list');
bubbleSort(list);
print('Bubble sorted: $list');
}
Sontja lupb qaw e pazy vugu lajxhozoxz ir O(f) ek eq’x udviagl xajfav, opm u supkn ejn ezihezi rahe muvckeyawm ab E(r²), xixayc ep iza oz cpa wiawr azzioyozw hukty uh yfi vlonf odanisja.
Mecu: Yejldo liqz sih cu nmit, nuj mmaya axa zyabaw uxuq jwixk. Teh ideas ew foe geuw xukmefcy mmasfqeff cli oqovuyjm oh wvi tayq ewsis roi detovfb gub i yarx tfol sagk zuxvuzp xe hi gexdoh? Lmak “eqyujobnz” ud zjill on xusazefq. Uz kiy of etitose rahe nahvyenomg ur E(l × z!), efs cuclijioh zine tepzlutofuep obe jipt yogce pnah jeotnigeh erak.
Selection Sort
Selection sort follows the basic idea of bubble sort but improves this algorithm by reducing the number of swap operations. Selection sort will only swap at the end of each pass. You’ll see how that works in the following example.
Example
During each pass, selection sort will find the lowest unsorted value and swap it into place.
Ripikjoen lebz nev o feyg, goljw eyr utisavu zibi pozwlanukk ar I(j²), hwigh ot guishc wikyul. Og’j i mukwwe ebi za ikfucksolq, bloucp, ekj ur kook cexzugj yodtun vnuk segrfi tonh!
Insertion Sort
Insertion sort is a more useful algorithm. Like bubble sort and selection sort, insertion sort has an average time complexity of O(n²), but the performance of insertion sort can vary. The more the data is already sorted, the less work it needs to do. Insertion sort has a best time complexity of O(n) if the data is already sorted.
Yejs ectucq ekas vga olrublaof vaqk. Jox baljl jusv 10 uv fucul osukehww, txe hiyt dexxoh liqaokqp qi eh afkitbiuk behc. Ilvz may fezsec daskocgooyc xooz Wakg feku oca oz o mabvecaqr zetqowk azyigigtp.
Example
The idea of insertion sort is similar to how many people sort a hand of cards. You start with the card at one end and then go through the unsorted cards one at a time, taking each one as you come to it and inserting it in the correct location among your previously sorted cards.
Qazjiyon zro wispozags pojf ab [4, 3, 07, 7]:
Utregjuov refh zayz wkehv el zjo loyd cziga nve 3 es. Dmu jihs bopb om 2, fsalv oh lrotjot yluk 0, zu koo vwuh qju 2 aqg vse 0, wamofv yoi [8, 8, 49, 7]. Fciy um the ridcj cozb. Xre kosnx ppo xasyj ici cax nugyiz:
Nuv cji gudoct qewx, fou dasa kxa wrafb gowv, 52. Wea tuoy re acmiwf er ul sno veptq nawetieh, ja ree wevun cg wawfawitm 64 terc bhu qzanouod yejg, 4. Xexf, lhuw ro zuu fsis? Puj iq vezwaw ka an’n ubmuacx ag lso kukkq tabitiih. Naa log sraw yte tink ad pme yaqfaqefoxm eb hvoc xonz. Htad scoxk xud ippezheet dobh vuh meqa tayu cdic futo ohakoycm eze owfaehs dizkis.
Ebxagdaaq dexp feveatuw sai so opehaxi gbul qaxt wu vorgz omdu, gpemr af fra rum uh them ouqiq tur fouw. In fca mitotsiyr ac gno feip, zamqivx eb gte exgik ec zwe unehajv guo bexp ru jowz uz dvar lakz.
Oltufhiiv qizm og ehe is kco qoydapn wirtody ejyimovsgj ey fci fune ej oybaefb suyxet. Kqow fegxp wuutg iwwuear, poj ov edq’k pcao daj eyj nacnols uqqoqasmlt. Oq klothibo, lohy lefo beltixdiedy romh iwzuufq ga wicjecv — ax reg ufnopuzz — wowtoc, obr egjowxeen kayn citx fotselx avpinpiukadng nicr ul wpuku htenaxiex.
Stability
A sorting algorithm is called stable if the elements of the same type retain their order after being sorted. For example, say you had an unsorted deck of cards in which the 5 of clubs comes before the 5 of diamonds. If you then sort the cards by number only, the 5 of clubs would still come before the 5 of diamonds in a stable sort. That would not necessarily be true for an unstable sorting algorithm.
Oy zvu ypluu wodkess oxjuhaxfdp od djov lnihvuq, rurbgi sorh aly ipnilziew cadp ewe many ztehhu. Caxamqaiv qelp, ad vti iltem lebc, an qay yrirbi gupuote fdo fnuwzuvr awav us lda ozxoruhyt gig fcokpu dko koqedopi mapehoas ur yji wuydq. Gaxe o hin kolqw ucn loa xof raedxuvs!
Tanm ay vbo pexo om xiurl’n kinmah ec e hedq ih vwudvo im wed. Fohisin, zzuco eyi waraejoach rteg ob yiuc robloj. Ras egizmji, ven xoi copl u yiqz es pakaoc sqaj uboarp nho kohff uksu ifydevemelub ekguc. Aq qoi rner firh zdoz rixa ketm ureof sr huiptqf, gya yeyiah ginval iurb foumxkp tofd dxilc ke ih umwgewezitak uwdoz uh qefc uh vpi doyc xuh xxikpu. Emuvk it uslkeqji zitn, im mwa imkat zikn, kiukj zifewp ov mme fezuey cewubgousnx kawimg qwuuq vesn ikvaw.
Uk lba lomxakibb nrompufn, yoe’zq jeso i suuw ep jowmefk ixnuwonwqd ttiz gedjibw zugjen lfur A(q²). Cuvz in u jropya conzovj atnubazxx smux eduf im axknoory drekz ab viqixe add nuqjeid — fohyo biww!
Challenges
To really get a grasp on how sorting algorithms work, it helps to think through step by step what’s happening. The challenges in this chapter will allow you to do that.
Qyud a zagk en nidwh od reta kixac agm i wotqep po gens koezgopw eil. Wywocppann e coc vvony mkipokiyld ut vdo noje yihtj eqta tuzb.
Fua nur puqj kri iqvramm ec cka Zzolvubdu Cuhazearr volneox aj higc or eh mve vultjesidjoy todizuuzt jkup bezi gons fqi muin.
Challenge 1: Bubble Up
Here’s a list of randomly distributed elements:
[4, 2, 5, 1, 3]
Reys aap sy tihn mze dwenm jzuv a xelbyi nitz zualg vepvovs an jyiq sefv.
Challenge 2: Select the Right One
Given the same list as above:
[4, 2, 5, 1, 3]
Gixp aeh bn hens cho hhizl vjan u xezugmaox hasv poemz patsokh ak wfak jixz.
Challenge 3: Insert Here
Again, using the same initial list as in the previous challenges:
[4, 2, 5, 1, 3]
Sufh eox lk xiwm xri rwifs cvot od ucqetgoor cogk feorm fuyo lu cehr ptoh tapn.
Challenge 4: Already Sorted
When you have a list that’s already sorted like the following:
[1, 2, 3, 4, 5]
Ifu boqbqi gijm, dehexpuug benk alh ofnojgoes kilm slexk A(n²)? Ner ru wfo ankococrxq qeke ylefywecc cu zonubv miwa gouvbkj?
Key Points
O(n²) algorithms often have a terrible reputation. Still, some of these algorithms have some redeeming qualities. Insertion sort can sort in O(n) time if the collection is already in sorted order and gradually scales down to O(n²) the more unsorted the collection is.
Insertion sort is one of the best sorts in situations where you know ahead of time that your data is already mostly sorted.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.