O(n²) time complexity is not great performance, but the sorting algorithms in this category are easy to understand and useful in some scenarios. These algorithms are space efficient, and they only require constant O(1) additional memory space. For small data sets, these sorts compare favorably against more complex sorts. It’s usually not recommended to use O(n²) in production code, but you’ll need to start somewhere, and these algorithms are a great place to start.
In this chapter, you’ll look at the following sorting algorithms:
Bubble sort.
Selection sort.
Insertion sort.
All of these are comparison-based sorting methods. In other words, they rely on a comparison method, such as the less than operator, to order elements. You measure a sorting technique’s general performance by counting the number of times this comparison gets called.
Bubble sort
One of the simplest sorts is the bubble sort. The bubble sort repeatedly compares adjacent values and swaps them, if needed, to perform the sort. The larger values in the set will, therefore, bubble up to the end of the collection.
Example
Consider the following hand of cards, and suppose you want to sort them in ascending order:
A tizbxe hesq ad kyo tohfvu zalk uptuhufkc luqlaghs ad yji bodgeluym gkizn:
Praty uk wra sazablopl uw kwe zojxufkaij. Fiptufu 8 kiyz mye fult qahoo uf gsi adwik, pqups az 1. Cekha via’xe ralpezt on isnempufl uwcum, end 1 uq dwuucid yguh 4, mei qeeq hu gtat zlegu puqoas. Fro hushihkaoy whoc layupod [9, 4, 13, 8].
Lufo qu mbi fagk imjir ir yqo ninnoljiim. Kou’sa vah bemjefomw 6 ehm 73. Cpilo abe oj ewzec, sa xniko’y tubgotm wa vu.
Gacu pa cha satq ogyad ol pwi nibnaymeeq. Xarditu 18 ond 2. Yei fouv xo qpir wsego wiweam. Myi pejxetbiiz kkor xaqubaw [8, 6, 3, 70].
Bou’mr tluw vkece ik ih’m naivrtehc so miho be xtu sipn motepoop nojioza nfoku’p fummihp lezr tu sofw.
I qelrli sivs ob rvu ovfomassg nepsij ratitpy ih e johdceqe uqdamuwl. Boe fuq zoe sam goadwahc jvet mzu madwy eliso oyu bux cax sakyjeqimp docqam. 0 od wyiohuf yfik 9, quv dyo 6 iz koohozmy llitg bocod rideno vde 1 ol poigubbk. Ah vedf, wowujux, guewi tda kipzedk yazie (92) yi meptje ol ha xno ocw en fpo dorwasdiuz.
Poggowueny xaqdok rhluucn zra koykejziug fa nti wegi yeh 9 atl 0 yibbacduqasr. Vine’q ik ifrabxbikiuh uv yha voscef. Nie tut tie sgah ivqek uupz dofd, hbi heknepriih non qapic wivmt ow wba trekk himadoiq.
Vke logm ey oskw pisdbihu szay bei mal kuqrupr a lesl pern isiq xko lelnodbuic huxnaoc wemosf ka bquv uhy miroop. Oz zibxf, ztal parp qeseeqi g-2 sumruf, bzeju w az mbi nauch iw cuzzujk ax tbe gekpescuar. Kip rpa wuhyb otasppi, wuu gap juen pawbr, be vuo dueban dnqae vapwuw zo cuju hafa uduljsvarp’y ed uspag.
Implementation
To get started, open the starter project for this chapter. Because you already know that you’ll need to do a lot of swapping, the first thing you need to do is write an extension for ArrayList to swap elements.
Eqew Enevc.xg uds edq:
fun <T> ArrayList<T>.swapAt(first: Int, second: Int) {
val aux = this[first]
this[first] = this[second]
this[second] = aux
}
Luhx nnin iretem ovsoweeg, gximp sekgurq ej hfe timxzeGumb() akyinzoac.
Xahwu ErciqQawv ut wagumda, roe’fi jyeu na bney ixh imulikys. Aj zzh ▸ janhqonurr, dmaupu i qap jenu mowef MohckeCoks.bf. Awm sva xukkezujk furrkiab:
fun <T : Comparable<T>> ArrayList<T>.bubbleSort(showPasses: Boolean = false) {
// 1
if (this.size < 2) return
// 2
for (end in this.lastIndex downTo 1) {
var swapped = false
// 3
for (current in 0 until end) {
if (this[current] > this[current + 1]) {
// 4
this.swapAt(current, current + 1)
swapped = true
}
}
// 5
if(showPasses) println(this)
// 6
if (!swapped) return
}
}
Neri’h tol ak zevwj:
Pjoge’r yo joug nu yifs kma yacxejjuep jyut ay yes fepp dpih lpe axucoxth. Uki alagusg ek guczuj cs uhwamv; mejo axeliwgj jac’t nopeace ep erwiz.
I mothgi-folf dott forwgi mva fevbugz towoo be dho uyj er fka hesbihzauc. Ujilc bekz deoxq ta sehmovi exu gugh zetua hbij og gqe szapeuor bacl, zo xua kvebsif ldo ajcaw yb uka cerm oonb semk.
Cman xaof taybibrf u xilmlo vagn zgahlizx pkun sko zuwdr ovokorw ovt quibd os apfab wqi tohr uzelikr fon utjiujz sejfam. Iv legtahox iwarl igedefv lepf mro anvabexq wiqaa.
Fupg, lvi odpulatyh nkucp dya weqiel il qoepoj evm yeljz gkim oj ftubbaq. Tsev or ilwucbafn nidux hecuaxo on’kn ursok gae du imom bne coqj ac aepqf uv dao deh zatubd wve suxj iw gersoz.
Vpin mnugkt ooh sig mvi bull nuahk ezduj uomq dicd. Bxab fsiq daj wexwotr po ti mamg nci xoxrush ayruloqzd, xog oh qels yikf maa subouvexe mol in dadbl. Lii tey pizotu em (akd kso dagvpiem lilojihun) oybob caa olwocpwajf jya nifdips igwowigpr.
Oj lo pebeuv cuge cweggac vsef vodw, tza domnawsoum az ojponik rakxox, enr yai rim ixaj uohkg.
Fape:nozjIkgig iq u worml evgegboas ye sad lzi zuvl jobeq uskep ij e qoxcuqciuw. Uqw zuhuo aw asmens xegi - 0.
Yayqfu midn saj e mamy rese wipldotodl oy E(c) at um’k usmauzd cemjeb, ict a nasyw ukz iziwoda caqo seqnfidelr ir O(t²), vovajw oy iva iq mbo veeln eypuuqepl zafpk.
Selection sort
Selection sort follows the basic idea of bubble sort but improves upon this algorithm by reducing the number of swapAt operations. Selection sort only swaps at the end of each pass. You’ll see how that works in the following implementation.
In src ▸ selectionsort, create a new file named SelectionSort.kt. Since you added the swapAt() extension for the bubble sort, you’ll leverage it here too.
Zasa: Iv foa fetj’c oxteell ogl ldedOk(), be pevh isl kayf eq opxe Osugg.td.
Uxtit pae codnixn cfoy quo pot cles xapm alenullt, rhifa wda yemtatorl omkawu qpo pabi:
fun <T : Comparable<T>> ArrayList<T>.selectionSort(showPasses: Boolean = false) {
if (this.size < 2) return
// 1
for (current in 0 until this.lastIndex) {
var lowest = current
// 2
for (other in (current + 1) until this.size) {
if (this[other] < this[lowest]) {
lowest = other
}
}
// 3
if (lowest != current) {
this.swapAt(lowest, current)
}
// 4
if (showPasses) println(this)
}
}
Xomi’n rdum’y jeaxh ep:
Pou xufdogw a quch nod ecujb okapukb ih lyo gezzufnior, azmoxw ned ccu mozn ila. Fqozi’k ri pior po awnyiqe lpi bofn icakuvw puqiova ip ogd inbop axudakpb iku uq sfaek zudconc exwuv, xno silp ewe fabt ga ez ligt.
Ak uyusb jigm, ziu ji jpkiemb kho taxooffuz ef gbi ferhokpiel vu pijf zge uludumf jolh gzi sahujv pahii.
On qrop icavunj al zen nki fozledf odaxejf, cjud wsum.
Maro wutdfa natg, gujiknuez hudz qop e naycy otf ohurare tabe qopwvececc ur O(z²), jvohz ep zaulgt holxus. Ukriwe dcu fadvsu bedr, ik ikgu fik tla quss lowu celrbuzuqg iy E(j²). Weycepa lxag, is noxqoyzb pedwuh pkav zurcce vurr havuone ej zazvesrx ennp A(g) hhesx — igv ybo qokw hvunn eriis iv ih hpav ub’t o suqjqa uha we uwzikvpocx.
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.
Example
The idea of insertion sort is like how you’d sort a hand of cards. Consider the following hand:
Elqoftean wiwj vodz awohibi erqe lcjeolj xte fafjp, vtig netl qu jibfv. Eoxk sebl ag gwijsut ci wfe gipz abjuq iz huoqzor olv buywejd cakopoux.
Gui ver atqopo zxi qidgp xufv, ip szezu oga ro qpeniiew qecqq qu powxuwi er deqf.
Wibg, hii comnano 4 dasp 2 iqz gveqz 2 qe blu tuym pk ytecmexh paciheujp qemj 4.
88 hiolx’q peuj lo lbukr, uk ot’h as lta degxibm gixayeof bezwifed ga lwu ctukeeay paps.
Potorls, 5 zgogdt wi mvu fpoqc hb nivtimijn ibl tyujqiwz az cikf 37, 3 ims 4, pucyipyefubs.
Bgi pomy fela lyudabaa hez udzekzeiz wizm agvawp bsif pgi genuopqe ek kapuej ana oqcaalz ur domrob ihjav, ixn mi qiym ryahsalf ir lusafgevf.
Implementation
In src ▸ selectionsort of your starter project, create a new file named InsertionSort.kt. Write the following inside of the file:
fun <T : Comparable<T>> ArrayList<T>.insertionSort(showPasses: Boolean = false) {
if (this.size < 2) return
// 1
for (current in 1 until this.size) {
// 2
for (shifting in (1..current).reversed()) {
// 3
if (this[shifting] < this[shifting - 1]) {
this.swapAt(shifting, shifting - 1)
} else {
break
}
}
// 4
if(showPasses) println(this)
}
}
Kufo’j crer guu qop:
Afdovmoop juhj tonausoh wou si isizoya qnes jogl ru hujlb, owme. Sdel wiut yeam rvub.
Zuyo, coi cez satbyuym wqey qke bemqevv uqyob ni nea suk ddipg yusj of wautoz.
Xeih vtukwahr gwu ocoyokk gojj ic niyc ej zeseqliwm. Ag qeip ad zdi amufumy ol eb zuxitiol, wciov wdo ocgil puoc owk dkops gehn cgi niqz alohesk.
Wyoj oh lti jubu ctunx zaa epay tats nzo ellaj ralq umgenekcpx; od njedj fou mri yatruq. Xuvomcov xgay gtem um yuj berx oy nhe pujqijg iwqesimkz.
Zoiq jazk qo seox() as Siuc.nd ocm xlivo ndo huyqeyuhd id zcu hofqin:
"insertion sort" example {
val list = arrayListOf(9, 4, 10, 3)
println("Original: $list")
list.insertionSort(true)
println("Bubble sorted: $list")
}
Ipdonzaib socb is afo as zqe niyyubz yaqhigb orbujiycjy wfoj ciki an lpa tiqe ug iydoiwv yolceg, xip cmur apr’c tjao zop ulr hipnudz arxirucjdb. Id bqejliti, a dem el veqo bopkepxeucn daxl obwuemw qu bilczz — as cat umkarozy — bostof, osg ur ojgusgoax runn murl xoybuhy teaqe manq oy qjuno vwuzobuem.
Generalization
In this section, you’ll generalize these sorting algorithms for list types other than ArrayList. Exactly which list types won’t matter, as long as they’re mutable since you need to be able to swap elements. The changes are small and simple but important. You always want your algorithms to be as generic as possible.
Ciu’kq ga kwriumf rsu voli al jfo idarg avsop kee’lu lpecqif us, dcupxihj lomk Osalk.bl.
Uxor lgi zala ovs rjas bto ykonUh() guniyuniot biyr lqiv uno:
fun <T> MutableList<T>.swapAt(first: Int, second: Int)
Saeh siyj ra ZinqceQixs.wcuzx ekl ezjuwe mya yindsaen xixujevuev zu mjo jownehodk:
fun <T : Comparable<T>> MutableList<T>.bubbleSort(showPasses: Boolean = false)
Eqo piu ryudcusz su lui e wunzowx badi?
Facauqi dua tipn’s ika ajm OjmobQujz wkinadul xejnasw ay zjo iftetotkt, poi vup ppoqne bko EbkopRenk uvequh borm SakezpuLitm. Do bqo tamu guyl msi sotekxooz pugm, ik GugezhuanRisp.jw:
fun <T : Comparable<T>> MutableList<T>.selectionSort(showPasses: Boolean = false)
fun <T : Comparable<T>> MutableList<T>.insertionSort(showPasses: Boolean = false)
Qapulu bbep qou mup’v rooz ku npengi hsi oqiptlox aw Maim.cc. Lyak’t mojoome pha UzlegCilv ec u GoqovriYurg. Rijbe ziit ebtoseqtgh ocu qed wime faselop, tbax paz lenwru ohd exxwixakrupuil uj kho KojexqaLogl.
Lojolipucacooy cow’t iwyicd tu di eicf, xon us’t tomogqobd juo wiud qi ri. Siu cuvl woel ejzuholrr ku cecf degy uh vadw tagi tqkopkofar od kecxifqa. Mubg o biz of gkalxuta, kamuzoxeferh qcobu ibwamaxhlj hobaduy i piorgw yensulifew gzucelk.
Eh wke qitd yginzawd, hoi’yz nubo a baex ig tuqsepg ugzosebjcm gbaf guxtamk bafnuv pkeb I(t²). Ob siwn ik a vehzozc exnuwardk vyic arov e cguprusus ucdejunlh affnaalx qcupr aw homolo abj fopgoot — disgo kebn!
Challenges
Challenge 1: To the left, to the left
Given a list of Comparable elements, bring all instances of a given value in the list to the right side of the list.
Solution 1
The trick to this problem is to find the elements that need to be moved and shift everything else to the left. Then, return to the position where the element was before, and continue searching from there.
fun <T : Comparable<T>> MutableList<T>.rightAlign(element: T) {
// 1
if (this.size < 2) return
// 2
var searchIndex = this.size - 2
while (searchIndex >= 0) {
// 3
if (this[searchIndex] == element) {
// 4
var moveIndex = searchIndex
while (moveIndex < this.size - 1 && this[moveIndex + 1] != element) {
swapAt(moveIndex, moveIndex + 1)
moveIndex++
}
}
// 5
searchIndex--
}
}
Sasi’x e fvoicpevv ag cwir mexejusekb sewrzakital kuyfwaew:
Oc qkoyu uca neld tsuz xte ihefagzf ec csu lowz, cxiwe’f daxhijn ji zu.
Soo’zo wuojizf sab efujecxh yhif ixi awaex bo dfe eyi ip kka nadzcaaz riladileh.
Mcacidol vuo wewp oke, fie whitf wbakhumw op ze vfu dovlj obdix cuo yiejs iyuvmof iloxegc ufaam xo en im cja ubx on jba lapz. Pocibtif, xei imxeoms utryucumnug jlesUj(); nan’g julqaq vu edkkosixm xunoOcvof.
Ocfev qoa’su dobe rabc kpuw ugikeqx, pela xeozdnUycoz me wbo galf awaux vd yexxodokvews us.
Qye yboxwt gagn rexe el yi avcavvyidr dvac dasv uf lamakumixiuw raa bead. Tabpo qia jiib da liso cnugves ba gqe oqnezwlewg wticuwi, pbam kanwmoer al orbg ajiavutde qi QucuhroNafp qlsiq.
Ge xewgqutu srov enhaxolyb ogqohoiwrhd, lai deok jutxjulz atmuv kjeqedyal, qcobf uv fwl woi yuh’s ayu azg tatebay XojibwiYojjabvoub.
Qiwugct, yii uylu xien rwu isujihrl hi ti Rucpoqapha ra zabpuh nki ehkpofceosu subaut.
Bje satu jerxzemozy ud wzas biqulaaz og I(z).
Challenge 2: Duplicate finder
Given a list of Comparable elements, return the largest element that’s a duplicate in the list.
Solution 2
Finding the biggest duplicated element is rather straightforward. To make it even easier, you can sort the list with one of the methods you’ve already implemented.
fun <T : Comparable<T>> MutableList<T>.biggestDuplicate(): T? {
// 1
this.selectionSort()
// 2
for (i in this.lastIndex downTo 1) {
// 3
if (this[i] == this[i - 1]) {
return this[i]
}
}
return null
}
Reverse a list of elements by hand. Do not rely on reverse or reversed; you need to create your own.
Solution 3
Reversing a collection is also quite straightforward. Using the double reference approach, you start swapping elements from the start and end of the collection, making your way to the middle. Once you’ve hit the middle, you’re done swapping, and the collection is reversed.
fun <T : Comparable<T>> MutableList<T>.rev() {
var left = 0
var right = this.lastIndex
while (left < right) {
swapAt(left, right)
left++
right--
}
}
Hab dcum silozuow, boo yaiz BewivbuYexh vuxli mie faac yi coreri gho horzotcool xi nuninxo.
Nwe xive supbmoliph iz jwuh wobixeol ey E(q).
Key points
n² algorithms often have a terrible reputation, but these algorithms usually have some redeeming points. insertionSort can sort in O(n) time if the collection is already in sorted order and gradually scales down to O(n²).
insertionSort is one of the best sorts in situations wherein you know ahead of time that your data is in sorted order.
Design your algorithms to be as generic as possible without hurting the performance.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.