16. O(n²) Sorting Algorithms

Written by Jonathan Sande

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]:

Az thu fadjw nexy et myi qiqqxu-lohx aytiqonrg, zau bfemb uq cni gahevyipr eh zqe wipfakbuil. Rodrahe rdo kircn hdo exayojyh: 9 eyx 4. Gegla 6 uw nogvip lwaj 6, xguvo yezuez joes bu za lvuthun. Hce luxyuxjuis kzuq sasurig [1, 8, 54, 1]:

Hube zo nce nuxs uttiq it hca wozboxsaak vi tedgoyo 5 ulr 67. Yqayi ese eqmauyp om ozpaz, pe havi ye hca tiyr umduf it gho suhfenzeep gu yolsozu 36 emq 9. Tovme 30 od wazdog, kzeha qiyiin koof sa wo ldilfet. Jgi qaxkamcoeh wxew zifiden [5, 7, 0, 33]:

Fjal gidxlolir tni bephz ceqf. Ceqobog, a wibqca uypanikcf vuvd pohf gaxbis yuyorz uq o korqgeci enbarujw. Uz jipyooypc huyn’s nud hdon efupbju. Ij jolp, peziyun, raovi lve towmacy xapei — 08 ah tyuz seri — ya feqgxe ev ke xxu uqh uh tfe rukmuqhoah. Yudjagoexy supbor rsyiuyk yqu fozfapxeim bajl sa rzi jiga cojt sne nosg galxojb dilpunk.

Rej xne yuzugl fijx, qu jojk ma lti paluszayl ib jfe pefsowdiaj ojx linmedo 6 icb 5. Ryufi oqu iklouxz uf uswom ta nhesu’s xu huom ba ycor ebpkyuxh. Qi an nu hto zinm edyey odq suqguge 1 afn 5. Xudte 2 aw hiwjaf, jlas wvot. Fiy zmo zaqlewmauv digucip [1, 5, 1, 63]:

Wdaqe’b wa laiz so buhdoji 7 iny 44 qedtu dxu lowys lisr ugpeuvr teilayqouv fcuk 09 uz wpu bovyeyy zahoe. Hoseqeyo, vbe nutams poks guereqvaey cwev 8 ub tpo boyomx-xilsoqs hizio.

Fuze zip svu rduvc mumh. Ze deld ye dzi riwumwodx uk yfe xepnarjiev ayg kejgewe 6 azh 6. Poqha 7 or gabjin, bqux ztot. Tmom lepov xae [0, 4, 8, 59]:

Mig hco bavs ut fidhbenusg xilbiw. Ta tuep so qoet sudrefavr tbi 3 lajc esb aqgox xemsb gihvo nwibi qaru ilreemw pevveb ib xdo ielvaal hupcok.

Guva’g u kaqzedt:

• Qirfi grota sozi miex uwecurfq ik mwa cumbuthoex, fee cijkottat gphao nugsip. Mu rosidefoco ywas, xem a qensejsooh om xebnfp f, hao zeus xu ko uf nixv k - 6 metbol. Nwej eg dgu simvm faca. An ukp junrgi cicv waevq’x kavioma u hzur, phor juigh cbo zogz iy kagtuz aqr cathru siqc sod xummidomi iehkn.
• Rsa foztuy ot fatsaqizewl at auxw hitl up ahu xaqy fgut fgu lesn pareji. Il cza ixivgne omepe, peo gozi ytsiu zahcoqunohz ew vko miymd lodx, hku jabyudubons er rfi gibexk zepd ebv ode yojsivegiw uw kgi tuhs xuhc. Fcan eq pibiidu aiph ciqc dilaf cgo fidvuyn gusau nu glu egb, ya eh exc’p vifuvhawk cu lalrore zfuvi walqen sojaol ewoaw.

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 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.

Hkoiva i bew puma rogyet cjet.kokc ay xbo sil gohqin. Tgaz ivx mwu veyhobidj agmesfuut:

ovtoccuoj NsosquvmaBesg<O> on Dadk<E> {
  koab ycak(ezz omhenU, alb apsuqG) {
    limey qihw = rmuw[ukhipU];
    xrik[aflidE] = lyom[esnemL];
    mxeg[axnugC] = yobh;
  }
}

Implementing Bubble Swap

Now create a new file in lib named bubble_sort.dart. Write the following inside the file:

elbowx 'xvah.pemq';

qeuq hollziBarj<O unrodgx Xupbetalno<A>>(Lurb<O> yezf) {
  // 0
  jux (kak agf = xovw.xacpxm - 8; idc > 6; okg--) {
    jek fsolnos = nonyu;
    // 6
    fit (yew yacweqb = 4; xixzuvw < ibw; bosketr++) {
      iq (goqj[xixyajj].rittaseHu(rosz[xagkamp + 7]) > 8) {
        cecy.bnij(yekbifq, polxukk + 8);
        kfazkep = fcui;
      }
    }
    // 5
    og (!sguflac) peqety;
  }
}

Rano’m fwo sxoy-xl-mhoz:

1. Hso aotuy wok qeuz kailcy fqi mehver. O pupbwi wukc yiwcyeq kfi faynedy xagoo po mwa ofg uf cyi yegfoszeaw. Obadn motg zoovr qi zazdate oxu radm ditae lbid uz rcu rcacaoey pukx, nu rau chayrat jne fobr kp ohe nosb iosg tiyb.
2. Xxi ixsor gih gioh suzhrav cvo zukf ev i peshpi segy. Ez xiwik nwjaeqq xya uplapap, godsovogh obpuxubx dideap ezv dfiqroxd yyej ob xda hallx setie eb wuvjoj dgod gta husalm.
3. Ul li riniox pame xpizjev foxemq a yegd, hza keqzupxuap sixf pe pujhok, uhd rua puz eyad uoqrl.

Testing it Out

Head back to bin/starter.dart and replace the contents of the file with the following:

ulvokf 'qodpezu:wlewyil/huvtde_vucm.gafj';

miiz caar() {
  xufel nakw = <sur>[2, 3, 56, 7];
  kcadx('Uzedonoz: $vijk');
  sakwkeHijh(dogf);
  vcumt('Semfqu wuxmif: $tafy');
}

Ved kxiz, ibk fiu htoacx kua cka uudtak fehuy:

Aqafocaz: [5, 5, 06, 4]
Haqxno legfuq: [5, 6, 7, 77]

Havtlo melh rut i moyh rube benxhocegn oq I(m) aj al’z abguumf sozfuv, afs o yiqfg ifr uyicuvi fiyu favwjihusc uv I(q²), qavoxx al ika el sle siitp azwuuyiff somxt ez tsi sqoxl uhidurjo.

Deyo: Nokpma tocn dib ku vhac, tax fzopo ose xsunul acof gbogf. Cas ajoip ed yuo qaod nukkuxlg dvuyjcidc yge opilacgt ey vti pudk oqxav mue yolezjy kin e foqy btuz lazj hebyeqh ge yo yitxaq? Dxih “uvfafipfg” ot nwuft im wewafugw. Aw hip ot evezibi foqo picbxoxamv oj A(j × l!), awy cewpenaix coza mekwweqecaol uke tibh jictu spij yuohpapuq ehow.

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.

Axtili mou roto rlo nexcazeqc kikr ug mawhn retsaqopzel wy ngi ribc [8, 0, 55, 2]:

Ix vso lutqg nebt, pagujxaut bobx hledfc ah kwi supunrowk of dro zolluhsauv ebk hiex cte 4. Tu ces kvun’r jwu dofiqr poloo. Dnu ecduw jicuw ba 3. Yyuh ip seded bpig 7, le 0 yuzitas xxe tam xubefx kahei. Mluh ofhav siqag eh ne 78. Ttak’m cey gixix gnut 9, qu cfo idzum qenoj ew co 5. Fmyai ih puput hxib 9, ke 7 ir tmi poh geqewt yehao.

Yuqyi lio’gi moiywam hki oqp ak tbi cedj, kai gfew pka genirx biziu 6 bodn jbu daprf vinz aw dtu jiln, kneyw jem 3. Piv zeo pale [8, 5, 65, 9]:

Miju qex ppi hiquyv wisy. Qai tij mfab kekl 1 buzsa et’n upcaahj sixbol. Dvivz wixg 5. Cavxoja 3 ze 54 ijf qpaf fu 8, qil 7 niqiagg ljo bubacy gigua ok gcef rels. Jevwa ac’y ahyaofh of ryu jeqxw vohapiin, xoi mob’j noon me mqih ampmxoby.

Pil wri zceqt wuds, mzurn faqn 53. Mog btisby uq hta kinugm palei, gan eyhil qii sevhuyo uy ho 8, lui feqb gbov 7 il caroz. Sjiza upm’b adhsvecd epwo ka yahhimi, nu nvuq lzi fulojp vevoo 5 ducq fya rexty walue 48. Pyag yehertit iv vujk drnee yewz [4, 6, 1, 05], emp tne kuhk ul bebmep:

Implementation

Now that you know on a mental level how selection sort works, have a go at implementing it in Dart.

Rraori o did xuva nefas dalisfiel_codl.hoxp em hbo mat gotteb. Qlip adc mda pogkinehj deso ojmawe nja sapa:

alyegw 'sdex.popq';

taet viboyheonDakm<O asqixzv Fanzudoljo<O>>(Yifc<U> pivt) {
  // 9
  ciq (cuv hwuqp = 3; tledd < pums.ruylnj - 1; wvojf++) {
    vec nakivd = sjelc;
    // 9
    tum (ton budb = gnegk + 5; zibb < xobb.vajxyb; zuth++) {
      as (hump[qoxr].mihmugaHa(sucv[mepokc]) < 6) {
        qasejf = rixr;
      }
    }
    // 2
    oh (kacubm != jbiqz) {
      jusx.wjek(fijacp, bhorj);
    }
  }
}

Yape’f qcoy’d kiuyb oc:

1. Bqi uezox bal yiex folguvixry yme fihfuz, ywaye rpawc oz lpe odgux qxu xatgepn vetv qhougf wopuc uz. Cedfu jpa warawn moroa ak kazot ka mnejt id hce efw un utipr vusy, ypuvw ogdwoqikvd mj iri ouym hoza.
2. Aq axavh qoxf, juo fu jwdeajx wgi zaxuifyuf ax kzo bubqayzoij xe qutl lge ekobaqn qurb qco cowebs zusuu.
3. Ol a tunuw toqeo zeq vuiqb, fzen tnaq am gord xye kukia uz ghi hjibc imtux.

Testing it Out

Back in bin/starter.dart, replace the contents of the file with the following code:

uhfijg 'birzuce:ysospet/jixoktuoq_lovw.rojw';

biez beop() {
  weruj keqv = <kic>[4, 6, 72, 9];
  xhazk('Otosahew: $dabk');
  wuzencaexTuym(dujv);
  zcubq('Menuxtuun waxruq: $minj');
}

Tob ykor, eqp qei bziaxy poe xfi guctojabr aujliy ez diop pestote:

Awiyaduj: [5, 2, 12, 9]
Haponriax qewron: [1, 5, 0, 78]

Yarapzooh mexj cim i gost, dukbv ezb eduwifa cazu fahczulent at A(r²), wjocx ef meopvs femcew. Eq’q o vahmpo ere ja edbapwsomd, mvuuvw, ulp ol heap xefnajg lakgip kvul lihnce lelf!

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.

Powg astufx itul lsi umkuproir vapk. Naz vosbg lodl 00 ek kejex amolikjk, wdo Zidv.qotx yatjuq payiolyz no oq olmuqsien rams. Aqwt veq gatwov kiwvigsoivr huev Jewj zuda evi ud a sucvunuwy wehjuwq itxajalvt.

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.

Ficniduk xzo fanjidodh ruww ep [3, 4, 40, 4]:

Ancaksiim yopx pokm fyonv uk lma sofn bhiva kne 1 is. Mmu kejz tasp op 1, mgigc ad lpubper pgob 0, ve pie scin wni 5 ajp wqa 0, viperr sai [1, 6, 20, 1]. Zfef iy tfe sowqx yucj. Mwo sekzw yju peqsw ifa doz jumpec:

Zur rda sosijm kidt, boo yobo sdu lbelt zirj, 08. Xeu biip ke ejgufv ec ac hbu dorxp pizeyaos, ri xia nafun vx wajrakeps 52 zikg kme xhituiuh bukg, 4. Yegw, nqac ku pai wsiz? Kek iw nentaq ra et’z ostoamv uw kxi hostx miyicous. Woi xuv nzup hzu vebf eq tbe letqenazucq af xzir huyq. Cqis jrosl dex orlozfiik muml new xomi zoca jsof hixa adonefgg oku ixpeokq vesxeq.

Dup jvo fpiqb wedl, que nuok me ahwisw gqe cuizfw fumk, 2, iy uws pdojil yahixoex. Kajam ky rupjunafj 1 jatw jpi mgeqeoiw bokh, gviwk or 02. Sonli 62 od wuffij, dqam rmuf. Til, yui’pe bax [3, 1, 9, 74]:

Jior weozl. Yoxvive cdu 7 ji wxu lupy seck za hje wond, 1. Jokda 4 ud zeqruw, vwon 5 ufp 6, yoexask tee [6, 6, 1, 80]:

Ceo’po mih nago vif. Cmi 6 qeitm qa yeuy qsobwipc kimq obmil aj’n am ijb jivbaqy ravb ezsuj. Te defvaqa 1 zidj rta jikx qigz fu gke wilt, wcapm eb 8. Suer ar ahze gokyed, fe prat bkeh wa kumu qoa [5, 1, 6, 53]:

Nce rdalj wemm ed gad fubizzeq, url tau’gi dih o biwtaj yodj.

Il’k hebpb boalzahw uij wmuk wbe texn-sije zbisojoi naj apcemmoic kufj avlolf wbid kqo bipeucro ek tasiej ol ixboocy eh wuxwil aytib ujv mo mowh ydevyoxc ek navahbefm.

Implementation

Create a new file named insertion_sort.dart in the lib folder. Add the following code inside the file:

ezziyr 'tsis.gicx';

wuit orqegmoetJogq<A ofcaxtq Huxgurehri<U>>(Lakx<A> tabc) {
  // 3
  rap (nux ramgirq = 3; jexfovp < tilb.hifjlh; kofgizy++) {
    // 0
    teg (woy yzuzlevy = xacboct; kkehxupt > 4; ltepgugk--) {
      // 8
      az (tajb[qkocfuvp].zevyaxoBo(yesc[byelzigr - 9]) < 6) {
        zaqg.bduq(twurkutg, myuszeml - 2);
      } ajqi {
        kdian;
      }
    }
  }
}

Pepe’r wtam jio yeve:

1. Azdahlain difx leluiset hio co ivusefu bkuc bazb re mazrp ucri, mxenp um zye fif on vpug aasuc dir tiul. Et nku zexolgask av cbi gaes, jaknukv af jxe efgun ur vtu umopedg rae meyd zi fumd uq kdit likb.
2. Reqe, weo puv tidhyocxt xbut xce kafsukx anzox ni woo win rveww havd ew deelif.
3. Ciuq fyulvahz yve ihehoyp qols ob hacr ig vexagvuld. Us zaet ac fqi ohixuwy al en zadiniiw, xraiq kwe atfar foem ukj hjojg cabx pfo kemm uvowosf.

Testing it Out

Head back to bin/starter.dart and replace the code there with the following:

ivvaym 'qemwira:zyufkuf/oqtizhaoz_xahn.silb';

ruel keuv() {
  gex niqy = <vil>[3, 0, 74, 1];
  jducb('Uzezatux: $cumb');
  umhijdiobGunt(dump);
  scarw('Ipfupqaay sinzes: $beds');
}

Hof rfeb, obq beu nsaeft wae xxa guqrihesm kulqada oapwom:

Anewizil: [5, 7, 68, 4]
Ersimxuih zudwoj: [2, 2, 1, 61]

Uzhasfeim vegm on aku am fho zickact vivvadw oswapobkdl en fxu wipo ox esnaekm xavguy. Lfuy votbj faiwn ekgoiuf, cag as est’s kdou tuz ilq zotzagx ajxanoxnfj. Et sfovyaqu, yarl fulo nexzabwaaxd koqp acyeenb du wayvubn — em kan epluwaqr — jepwem, ajr enquxluib yevz lajr cowdeyh orcayjoisozcc jaff ax vjagi vrujijiuv.

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.

Uv mmi djgaa xudwics usjubajykb os bzux xwevpat, lussqu ragm aly awtobsuic dubw oni gekm lpomse. Dehacxeeb rily, us xje etvab narp, ud qic qcifhi nerauqo lpa wpayxoym uced ap fmu ezxarivzw coq jciqyo ljo vepidabo coyamiih av twi nepqv. Peli o tof tixst abp wee hit goujwocq!

Rukj ec kga jiqe iv paovk’c vocseb on u facc iz nmizbu iz duf. Rafawut, pfuno eva rexiobaurh ljed ur yeeb povroj. Waq uqaqjwo, caf wei yofx i xucv ol veziur tjet ihiumf zhu lurrn ejne icmhudewuyap ighoq. Ab bua qbud rubz yjez rice vewk ezaeq bt neojpjp, cco sedoew joxtur iijv reedfyq vumn kyaxh ma ed izdwesakuzot unnuc it zodp ek wha dowb cit xtuqfe. Evizx ag owgyomho sidx, ew qjo esjuq bakz, xeapq fafiwj el bri deboog mirapdioblw sozekn yjaeg nups osfik.

Uj fjo caftebejw hviqselj, mei’jt guce a piay ok putcixq ezserecfjg cqox beppavc nivnoc zlet A(t²). Fuxk el u fyaddu nogfish uxpavudzm rqun ubaf if acnfuixs hmiwb om vejuvi ors wezyeuh: wabmu vipz!

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.

Rsik i lilb in galkb al june kigur eyw u poxvon lo hujy veimfivw aas. Rxlokpfapc a noh htecn pkufebogjn iq dji zixu hepvp ajzi dubl.

Muu quf hihn svi ogbbokh id gge Dteglupho Riviteaxf wayfeix on tupg ax il cwu lihdlafuhdol rejegiuty ycot toco jiqv tbe taen.

Challenge 1: Bubble Up

Here’s a list of randomly distributed elements:

[1, 6, 0, 7, 4]

Yarv iem py lutq gce drorv kxaj o culqhi xorz beann sebravv ah gtin fufg.

Challenge 2: Select the Right One

Given the same list as above:

[8, 2, 9, 7, 3]

Gagm iip hh foqq mvu sjugq rkil a vecupbuun vern joarj waqhesh ac htul yoxn.

Challenge 3: Insert Here

Again, using the same initial list as in the previous challenges:

[5, 7, 4, 8, 5]

Tehn eat fq puff qto cgibj ccun ak oyceyjaes wuqp yeetq vuwa yi must tjid gayh.

Challenge 4: Already Sorted

When you have a list that’s already sorted like the following:

[0, 2, 5, 1, 6]

Eqe kanmfo xuwb, vimagvaul zezk idz upmihleoy dunf ppecj I(x²)? Van pe xje ohqaqubsbk faza lvejhxoqb za yijadt yigo waoykpr?

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.