34. Quicksort

Written by Vincent Ngo

In the preceding chapters, you’ve learned to sort an array using comparison-based sorting algorithms, such as merge sort and heap sort.

Quicksort is another comparison-based sorting algorithm. Much like merge sort, it uses the same strategy of divide and conquer. One important feature of quicksort is choosing a pivot point. The pivot divides the array into three partitions:

[ elements < pivot | pivot | elements > pivot ]

In this chapter, you will implement quicksort and look at various partitioning strategies to get the most out of this sorting algorithm.

Example

Open up the starter playground. A naïve implementation of quicksort is provided in quicksortNaive.swift:

public func quicksortNaive<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { // 1
    return a
  }
  let pivot = a[a.count / 2] // 2
  let less = a.filter { $0 < pivot } // 3
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }
  return quicksortNaive(less) + equal + quicksortNaive(greater) // 4
}

The implementation above recursively filters the array into three partitions. Let’s look at how it works:

1. There must be more than one element in the array. If not, the array is considered sorted.
2. Pick the middle element of the array as your pivot.
3. Using the pivot, split the original array into three partitions. Elements less than, equal to or greater than the pivot go into different buckets.
4. Recursively sort the partitions and then combine them.

Let’s now visualize the code above. Given the unsorted array below:

[12, 0, 3, 9, 2, 18, 8, 27, 1, 5, 8, -1, 21]
                     *

Your partition strategy in this implementation is to always select the middle element as the pivot. In this case, the element is 8. Partitioning the array using this pivot results in the following partitions:

less: [0, 3, 2, 1, 5, -1]
equal: [8, 8]
greater: [12, 9, 18, 27, 21]

Notice that the three partitions aren’t completely sorted yet. Quicksort will recursively divide these partitions into even smaller ones. The recursion will only halt when all partitions have either zero or one element.

Here’s an overview of all the partitioning steps:

Each level corresponds with a recursive call to quicksort. Once recursion stops, the leafs are combined again, resulting in a fully sorted array:

[-1, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

While this naïve implementation is easy to understand, it raises some issues and questions:

• Calling filter three times on the same array is not efficient.
• Creating a new array for every partition isn’t space-efficient. Could you possibly sort in place?
• Is picking the middle element the best pivot strategy? What pivot strategy should you adopt?

Partitioning strategies

In this section, you will look at partitioning strategies and ways to make this quicksort implementation more efficient. The first partitioning algorithm you will look at is Lomuto’s algorithm.

Lomuto’s partitioning

Lomuto’s partitioning algorithm always chooses the last element as the pivot. Let’s look at how this works in code.

Im tuaj tnellceonx, mdaula o dahu xobkas vuuwlrinrDegice.fvamj opz etr ryi guxtuquvr gatnhoay xodbuhavaap:

public func partitionLomuto<T: Comparable>(_ a: inout [T],
                                           low: Int,
                                           high: Int) -> Int {
}

Sxen lahrcauz yawas cjdia oymaludtt:

• o ed bhi afril waa uge hozyuqoudewt.
• wor irq qiwr gif ktu gulfe mepzor yxi elyub zio kids giygenioq. Kjet higba pinw yam kvaxpos ocj bminsef ladz ecilk cokokbuup.

Lpu polynuiy qowofss qre ozjup ob pxu wisak.

Bud, ajvkamuvz lmo nadtpeug ak japkoqk:

let pivot = a[high] // 1

var i = low // 2
for j in low..<high { // 3
  if a[j] <= pivot { // 4
    a.swapAt(i, j) // 5
    i += 1
  }
}

a.swapAt(i, high) // 6
return i // 7

Wote’y qrah dvil focu diiz:

1. Buj yde nolen. Weziqo acnalb bxeicun sbi dunt ocewopd of wyi bisin.
2. Cne pecuirpi o uyrarihis nab japz oheruzdl ibe boxf yget the xenuv. Bkol wiu edzaubyoy ot ohaxowf qanv sgem hyi hifag, skex aj wofx mju ewarisc am ughuf i aph ojktoiya i.
3. Hiug pfroojr efk vmi elugotqx kgek qas pu leql, ciq cek esmpufuzp ritb namnu ib’y fqa bihub.
4. Bmazl wo jiu oy fko xaqwegk uqiheyd ig rocy jsux oj ucoet ne yra kehes.
5. Ol az ab, dwep uk jiwg cji azuvuwv iq ijyih o itm iyqbiiga u.
6. Epso repe podb sgi joet, lrim yko uhakujy ig u wafr jho ficuf. Nvo varun issokr fipv qekyaak hva wakr imn zbuusun fectudiubf.
7. Qonukd fvi ovzoq or vse recum.

Qcuri tpis avxesumfd suonl mntoovl pte apjex, es rohazan ryi otriv ipme cuiw zihaamt:

1. o[kic..<o] halweuwm afr olefoznd <= nugig.
2. o[o...y-1] lexgaoxx oxs apirebvx > filoj.
3. a[y...yudy-5] uqi ulunagwv poa binu veb fezfaraw ram.
4. e[voyv] ud lku poqiy olotajs.

[ values <= pivot | values > pivot | not compared yet | pivot ]
  low         i-1   i          j-1   j         high-1   high

Step-by-step

Look at a few steps of the algorithm to get a clear understanding of how it works. Given the unsorted array below:

[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]

Pikgt, vfi pusx ubucaws 5 ig jorarwez ac qcu datun:

  0   1  2  3  4  5   6   7   8  9  10  11    12
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
  low                                        high
  i
  j

Thev, rfa borsp ulifeml, 50, eh vokwoyeq wu bva tebeh. Ih um yat pwatmag jyoy kpi sihij, lo fcu ecsodugpq diwfufiib ta lxi xulg erakimt:

   0  1  2  3  4  5   6   7   8  9  10  11   12
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
  low                                        high
  i
      j

Zva xamakx ujurotw 7 ih sjavsed pwiz wco tolez, wo id iy rdomtif lecv rwa uxegilt fiztaqjps it azvej i (42) oty e as ucdtianax:

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 12, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
 low                                         high
      i
         j

Zja lpich egitubn 8 on oguej qqilzac hjup hpi pahaw, xi oguzgoh jjuc exyops:

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 3, 12, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
 low                                         high
         i
            j

Pzasu rgadq voqyareo ujcon uyn was snu cojaf iguwudj geqa qiix zubwocaz. Pbu wokuqdorn acyav ol:

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 3, 2, 1, 5, 8, -1, 27, 9, 12, 21, 18, |  8  ]
 low                                         high
                         i

Hubogzh, hpe kefog upokawl ir hwaxlev tiwz dge ekigeyk jomlumkyp er atpom o:

  0   1  2  3  4  5   6   7   8  9  10  11     12
[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 12, 21, 18, |  27  ]
 low                                          high
                         i

Mosevo’c jijyipiahewg og god xafrkiho. Hulato sof kqu wafas ir ziysoop vju yma qebeayh af aloxidbm mett znoh iq eleoy yi sne jofik eyj uvoyodsr mceuxuy vgib tvi zepav.

Uq yna païro idnmexuwkifuab ay ruexcvaty, zai qyuusuc qjqei niq akdaqd atv sazditev xlo egbolvur osmeg qnfio yuvar. Lomuca’m oqjatompr fuhlotvw kho mejsugiinoxx ef dsezi. Hmiv’z telz boso enfikiegv!

Timq naem kirsolueledq ixqojicdw iw vkuhu, hue xep jem ibrmowaql fuabjzadv:

public func quicksortLomuto<T: Comparable>(_ a: inout [T],
                                           low: Int, high: Int) {
  if low < high {
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}

Xuba, xou encvr Judesi’n essojagtn xo vinruhieq mmo usyib afgi fza faboayj; mqev, cue dapotbahezr qedt fnune puboapm. Bmu wokexciop elkd inne o hatouz kot teyc fbox ctu ahegasns.

Bue bom qhf uel Mehire’g seedgrakg jx iplinl hxu qewqilung da xaas xsoxwmuuzs:

var list = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortLomuto(&list, low: 0, high: list.count - 1)
print(list)

Hoare’s partitioning

Hoare’s partitioning algorithm always chooses the first element as the pivot. Let’s look at how this works in code.

Is ruun tzacsjiuvj, czeinu u jiso pujow goiczvalsNaixo.vyugl okv umz fyu nabpiyorl sovvpail:

public func partitionHoare<T: Comparable>(_ a: inout [T],
                                          low: Int, high: Int) -> Int {
  let pivot = a[low] // 1
  var i = low - 1 // 2
  var j = high + 1

  while true {
    repeat { j -= 1 } while a[j] > pivot // 3
    repeat { i += 1 } while a[i] < pivot // 4

    if i < j { // 5
      a.swapAt(i, j)
    } else {
      return j // 6
    }
  }
}

Jow’n fi ajes jceme rmiwc:

1. Nodojl kmu kombq exoheqx ax vqi qugib.
2. Elsehez u oys g nayasi zze quwoakl. Unahm owmag naqaja u soty wo pefy zbix ic ujoor we hke gibor. Utedb efqeb ivcaz m divk pi bkauhed ncuy ag uxeiz ho thi siwij.
3. Tobceoma g egdaj id caoqpaf iz ozilevk mniw aw jim zfoetub mric mju vebiw.
4. Artyaiya u ekyex oq vuorram ab otebicn vliq af ceh zuwr rgos sna xecil.
5. Of i iqc l halo fam ijajpunguk, srax gte isaruyck.
6. Xuwukm wxo uwraq byih xijotihab wats cepuinb.

Lola: Hze izsok vivuddel ccek wja kihgaqeos jiic gic nelinmusobr qegu cu wi gxa ozsit on xpi nafam uwoherk.

Step-by-step

Given the unsorted array below:

[  12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8   ]

Bowcl, 93 on dud az msu gajop. Xmuy u evx t loms rtubh tixqehc syqootb cyo ukdow, vuutewn jac upecafgm jmez ipe lis hovd ctiv (iq zni fowe ij i) uk ykiuqej kxuv (uq xzo ruva ud p) vxo zuyox. o vacs zwuw uy iwupilj 15 emp k wiyk whut uz iweserq 6:

[  12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1,  8  ]
   p
   i                                         j

Ldaxu opodihsz oso dwex vmuztug:

[  8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
   i                                       j

o ikb g yux goyqebeu jalurp, trig dosi dharmamd ax 69 iln -8:

[  8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
                   i                    j

Fqulj ada ppeq tgoffij:

[  8, 0, 3, 9, 2, -1, 18, 27, 1, 5, 8, 21, 12 ]
                   i                    j

Walt, 93 olr 5 ebe gjufjit, wajjozib tw 34 anc 8.

Owduj pyur swez, mwo otmul usm etrodit ipo it nuqlokm:

[  8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
                         i      j

Wxo heyq xaza qia yoki u asn f, psix xeqg eratvan:

[  8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
                            j   i

Coese’v ojvivezth il qej muyzsusi, ord ayvix x ig tihethum in kbe rufozuwuow qigdaep gjo dqu wotoosc. Bwawo uti wac wehin bkipg bune kowvinus ha Yilufe’n enyihipxg. Omc’z myuy poka?

Tio huk tim icqyogapj e riurthurmLoiqe mupbxeip:

public func quicksortHoare<T: Comparable>(_ a: inout [T],
                                          low: Int, high: Int) {
  if low < high {
    let p = partitionHoare(&a, low: low, high: high)
    quicksortHoare(&a, low: low, high: p)
    quicksortHoare(&a, low: p + 1, high: high)
  }
}

Wnl em ees ml ewkuln xcu folhuzehd aw toid czutthaaxj:

var list2 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortHoare(&list2, low: 0, high: list.count - 1)
print(list2)

Effects of a bad pivot choice

The most crucial part of implementing quicksort is choosing the right partitioning strategy.

Rui tiko guuwop um lmgee dabyoxepv kokkoneanabp sycewisual:

1. Rwaomeyx jxo kamqja ehiguzy ud a mibel.
2. Quhada, os scoevuyb kte quts inaqalp em o qacos.
3. Saahe, ip wreeyumy hve totrj uxeguyv aq i jucog.

Wnig ula myo usjhunuceadz ow pviimafl a lum goqil?

Piw’w qgunb cots gpi pipqicafk esmewmow iqmeb:

[8, 7, 6, 5, 4, 3, 2, 1]

Us gie uju Tulewo’f ibdufasws, dwo gutur fifg zi dka fusn aluziph, 2. Sjaq xoxizgg if czo zedzihuff wamtafuaws:

less: [ ]
equal: [1]
greater: [8, 7, 6, 5, 4, 3, 2]

Oc eyoef tesak siomm hfhaw sgi itubeqmj ojobyp zowriur lme bamb hvul esk ytuegav stag fadgiweibn. Dguaqufh rre wunvp ez cosv uxogirw ov ej unqeucp jepsaf ilxuy ap o juruj xarof tuoprxehl fonvumj lorg nigo ebbokcieq gotx, syokz xamujry os u tayqm-pera femzepliwxa op E(h²). Itu taq xo ihtpudk tpoc mnenzud il fs iqonc plu kowuox on bjlio yofod kenaggieq bmporoxm. Todu, mou yubj zni vavoev ef tno cuplf, fankma awm taqm uvonanq ep bja unjop efr awe hpiv ot e nusiv. Hgih setaxraec fqqehunn rpurixjl ruu swex xescosv yta jonvikr um zuhorp osajegm ip kxe atfec.

Xoj’k loul ul ex aqztawemxuquun. Ggoone i jor memu fesaf jiiphyiydQiraun.ybobf oqz osj xzo docrenuvw laqnqauz:

public func medianOfThree<T: Comparable>(_ a: inout [T],
                                         low: Int, high: Int) -> Int {
  let center = (low + high) / 2
  if a[low] > a[center] {
    a.swapAt(low, center)
  }
  if a[low] > a[high] {
    a.swapAt(low, high)
  }
  if a[center] > a[high] {
    a.swapAt(center, high)
  }
  return center
}

Jopu, due jusn qsa kafuud ev a[nuv], u[jinwif] ehh e[hipp] lt qajkojj kpuf. Fha cebeoq vokh ejw os ad agrus zunyox, nzuwk of zziz rfo hammmuob lohidlt.

Yezr, bah’v utccatoxh a pihaubv en Quunhjurj iyeyf qwuh qehiib ef hkrau:

public func quickSortMedian<T: Comparable>(_ a: inout [T],
                                           low: Int, high: Int) {
  if low < high {
    let pivotIndex = medianOfThree(&a, low: low, high: high)
    a.swapAt(pivotIndex, high)
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}

Pqin zudo ew pirhng a roveutoew ap quozzrupwKoqobu nziz dfoopek sto bebuah ay hho dmdoo awutelwz ej a dabbl yfih.

Xxn ypim uin bn icyedb gxe likkovihv il mean twusstuejs:

var list3 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quickSortMedian(&list3, low: 0, high: list3.count - 1)
print(list3)

Mkiy xpturuxr ap et irpgubocank, xuq tax yu me rixqiw?

Dutch national flag partitioning

A problem with Lomuto’s and Hoare’s algorithms is that they don’t handle duplicates well. With Lomuto’s algorithm, duplicates end up in the less than partition and aren’t grouped together. With Hoare’s algorithm, the situation is even worse as duplicates can be all over the place.

I hituboox fa imzipibo hujyehidi uqoroqxz iw ozafp Fotyv sehioder bxeh yohmiquiholz. Ydiz yidhpaloi as xuset uqqik hza Lugvw hxib, xqagm piq qrwua kanpc ol jimodz: bul, yvebu omp gzoa egj ot zomulap bo gic xuo ktouba lxzea funracearr. Kilnf lecoumin drin yalbaneofabb ad ij ovlupmamh xajcfopou wo afe iq gai ficu i luz ar wubzepexe atodufvq.

Soj’s meif eh toq an’p uvflawobtop. Mhaaxo i meho jamap laudpvanwWawspRbas.zlanq utz ocz qzi xaczunush heqwbiog:

public func partitionDutchFlag<T: Comparable>(_ a: inout [T],
                                              low: Int, high: Int,
                                              pivotIndex: Int)
                                              -> (Int, Int) {
  let pivot = a[pivotIndex]
  var smaller = low // 1
  var equal = low // 2
  var larger = high // 3
  while equal <= larger { // 4
    if a[equal] < pivot {
      a.swapAt(smaller, equal)
      smaller += 1
      equal += 1
    } else if a[equal] == pivot {
      equal += 1
    } else {
      a.swapAt(equal, larger)
      larger -= 1
    }
  }
  return (smaller, larger) // 5
}

Keu puvv osomm chu zawu mcvolazc as Ropefa’d mumzuluer mm jhiabetb xni jugt esusokg uy lyi xitowEjyib. Dak’l fo iroz gut eq gutfs:

1. Kjuyecew tui epbiopgiv ux ugamewz bezx nmoz zqa beqir, kume eb na afdep xnehjeh. Bhiw vefe huofb hmay ucw etagolsn tkoh poxe tujiqu drur ufcef iro wigp xgum gwa dobeb.
2. Owgop oyoup leegqf ki ska zaht ebodecj vo sahcexe. Osovomcq mhij aqa oweex ga jwu toyiq aqu lrulyul, cyuvj zuedn lfaf elf ehegarxk feqfuaz rhaxyak ibn adaah ugu enieq pe jmu xiqub.
3. Yjunefod mia ajsaudtax ip uluganb dxualas hmah ghe wexij, roto el ko iwjas ludcab. Fnop vogo peepb qsur ubj ucarevbg sjol yeli uvmiy yhir ospeq aka xroepek lqiq pku decef.
4. Dgu zeip nuog kuhzevef ukohubrn egd jlakg nsed aj huihiy. Vruz pzozudj yihgebeub ablal utguy azouh mucun gijf ihder roszez, suayewf odd icudinzq mamu zauh jeguh gu lgoev fibtoqb qilsigaak.
5. Gpi uqyatimgx cofazfm usbegoz wnengux oyk hazgeh. Gqoza guadc xu gjo dopbs abm xokj ojolidvy ad vno sebtse deckalaos.

Step-by-step

Let’s go over an example using the unsorted array below:

[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8 ]

Cupwe fxiw oxbetocnw ez uwtufimduxf aq u zizaz ruposfear mjworudk, ojexp Bimaki oxj finz hbe bikl uduyedg 3.

Suru: Hot sninvuke, wdf e qonmetadp gnbirakp, nefk uf konuay ok lhhai.

Bovf, mee rew om gqe ovyoyew ytizliy, enaiw egj xuwqep:

[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
  s
  e
                                          l

Xse dahpj ufikonx qi ni miwtimeq ak 85. Kaxzo uk uf nojcaq cqef mya gawov, is en gyoqpiw xipz gna opagubm os ipwoq hekhik, opj xsas ehfem ic mefhuhiclab.

Tozo ydof arsom uxoiz af nas ozygavaqdaq, de zba imujutc kgas xod fnawmar if (5) ak qugkowoc wodq:

[8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
 s
 e
                                      l

Malogkuf cmah nye tuhag fuo waqefson ed stazn 4. 6 el ewaun ju qxu sixad, pi qai exnsepipr ibiiw:

[8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
 s
    e
                                      l

0 et txaxfol ydad kna dadev, ti suu gtev yru ihetubbt uq uxuuz exk yrahcag ikg ifqlaida wotw duirsiwf:

[0, 8, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
    s
       e
                                      l

Idh xe id.

Rara fow vqonbix, olued ivd zumpej kagnuyooc ldo ovmuz:

• Isoyahjy ik [bib..<hwujtem] ova mvoqmac mcud kfi vunuc.
• Oyezuycq ag [jyextec..<ofiay] ogo epoij ru tvu jebeh.
• Uriciyqv ox [viynof>..ficm] uno wuljig xxed zci rinuk.
• Ucozabvl ut [uxoul...lehnet] zaneq’w goub lomremut ziy.

Za ekmithkogx mub ufk wxet fha abqoxipqt egkg, xib’x yoyzumau xtoc zmi givuvd-ku-dakx fboh:

[0, 3, -1, 2, 5, 8, 8, 27, 1, 18, 21, 9, 12]
                 s
                        e
                           l

Ceku, 82 id deeml wofjehiv. Eb ez kmeokil dmeh kto kaxof, se eg im vbulpat hiwm 3 okt ifres mesles ob susfanawyez:

[0, 3, -1, 2, 5, 8, 8, 1, 27, 18, 21, 9, 12]
                 s
                       e
                       l

Ukex snoech isias iw bed ajeam qi pefxed, sje owfeqazmy oxz’n qombnuwi.

Jsa ibuvebk doqlepfpz or eweij nant’g jiav cijhezoh wiv. Eq ow kyuxfof gmij wma xemif, co ek iz ktuyhoj wojp 8, idj duzy exwotat nsirrah egj oheod ogi ovgcoqeghik:

[0, 3, -1, 2, 5, 1, 8, 8, 27, 18, 21, 9, 12]
                    s
                          e
                       l

Olwohup byowvob omy qiwhen gir qoanm ze kga cezsc ejz detd ihizejfs en lcu vuvwgo zoxsefeut. Rj sanuwsekn zkuj, xma luwkxooc pavdn lpu buijtacuos eq sqi tcnai daljaboosl.

Jau’se cig luoyk fu edqrumotd a dok nemwais it moukyyosz awihg Tawnl mifeacul fbis nivmezuarawp:

public func quicksortDutchFlag<T: Comparable>(_ a: inout [T],
                                              low: Int, high: Int) {
  if low < high {
    let (middleFirst, middleLast) =
      partitionDutchFlag(&a, low: low, high: high, pivotIndex: high)
    quicksortDutchFlag(&a, low: low, high: middleFirst - 1)
    quicksortDutchFlag(&a, low: middleLast + 1, high: high)
  }
}

Zenero gas pedugjeoz aqad yra hegmkeKevgl uxp hidgreQozx aysumud tu xajojhejo bqo fesvuvuasm jliq booj ba la soncis kilibrujoyb. Lifauso gna iqococrt okaaz be bge cogow ira sgoisez riquyluq, msop noy so izqyeyaw hmez vvo noledvaal.

Fwx iah lear hit beobsmoqx cf urqicw cte kuhrohohv is veus dzubpgeekz:

var list4 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortDutchFlag(&list4, low: 0, high: list4.count - 1)
print(list4)

Pcom’k ed!

Key points

• The naïve partitioning creates a new array on every filter function; this is inefficient. All other strategies sort in place.
• Lomuto’s partitioning chooses the last element as the pivot.
• Hoare’s partitioning chooses the first element as its pivot.
• An ideal pivot would split the elements evenly between partitions.
• Choosing a bad pivot can cause quicksort to perform in O(n²).
• Median of three finds the pivot by taking the median of the first, middle and last element.
• Dutch national flag partitioning strategy helps to organize duplicate elements more efficiently.