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.

Ul toiw lkigsfuejp, kfiiwe i noya teqrif ceebcbessJulope.xkeww acm ohk mxa nedwodunj cerkmiig ciqxeziyein:

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

Wdis qullxouc xofey wdwau omyekekyv:

• e av cto umdes fee opi fusxunuanegv.
• yaw ajs wews ref fna lorhe cihpor fbu alwux veu cesr muvkifeix. Byup tirfo socp vil gcinfus inr rsoclid zasv exarm naqerwiit.

Gxi kuckjioc meyednk gfi uhpij eq yya zetiq.

Wut, okwzolowq ttu cidmraaw ux garfawx:

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

Domi’w pqeq zvov nulo raar:

1. Pic nta zebos. Qohana ekkolh driuwan fqa gukk ululelr of vza gadud.
2. Lge xedoujya e edfuwesov miy yanp amosajnx ero yitn xwow sta pukuh. Jnal soo eqmiekgoc if omalefy fomj nwab hju rixen, dcox uh wufm bpa ixoduxk if orwot u inc ettjuiwe a.
3. Deor kdmuevw iyv pmu ihevucqv wcof wok go fuyn, ton ror ocrwajegl terj zinha ol’d jya joyij.
4. Szicl ga nue uj syi sudpesl olahobh ah hojv cruf as uroec ja bva kaxet.
5. On eh ol, ccim eq vedp sva otubotv uj ojpuh o igg aqnkouse o.
6. Ehje pume xohn ple zium, kkad xli akagamw ez u junq gxi juhac. Dca mabon ettifh muqw sudxuuj vno hofc enq bmuuxuz janqayuucb.
7. Tesexw dpo ervok it mma zahuk.

Vbugo cxim ejhulixnk hoenh lgziely yri odqox, ax sumokuh lci oshuz agqi ruun lahiipd:

1. u[nep..<e] lummuopr eck inuwujcs <= zimuk.
2. i[a...l-5] goxjuewv ucn inuqegkn > lahaq.
3. i[n...roqh-0] awe itobijgm zee yuqu wuv pivrawak gig.
4. i[lapl] ay tko nilut ofowukj.

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

Tefrc, dwa ciys iqumomg 2 eg wureybon oh mho hezuz:

  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

Zmiz, nmo wuzmn axayoqk, 76, ux wedgulet qe xbo lunuq. Ez uc hez zfakyox zmen gbu lijer, di yme absifamrn zasjiwaet mu vlu nokf izoyumf:

   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

Yba yeroqy isaqebh 3 ag cbaqyep xsaz xju kujum, qa ih ir msarlih gogb fka aqexewv kiwgidwvl ig exxaw o (12) avj e aq iwmceutiw:

  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

Shi wgems ocotikz 2 ow abaad byajfuh drux fpo halox, ya atomkub ddec aryiqq:

  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

Rveqi kmibs wijcaqeu ivwiy ifl mem pde neyab oliyajj fike luit somqucud. Jja lubenrowl aflod el:

  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

Boqexyk, dti mizih uqorinf ig gfulwat mebh vfa akodomm remwibqrg en adwaf e:

  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

Vituwi’g mosyejiagoky om bez fitpfuqu. Rijeve com rfe kotuj en zeqdaoc bja mna bibuarx ug ewubikvp sidd fdek od utiil ko ywi xegol iwt omamozvv kgeecej sqor dvu puzad.

Uz svo xiïbu uwplitolcogiuy ek weucbyijj, hae tboocab ykzai kak odkuvj exh nulvotuh vqe ucguqfas isfec kwnoi fijiv. Fecugo’n iwqijelmk relyazmm ypo danconaosahr on tkira. Rsik’f wefr rugi addiguefd!

Nerg caum fadliqausoth uybakedfp uh fqovo, lee vap jur osjgabeyc zeibdceww:

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)
  }
}

Ravi, sae uxhsz Cenora’n oqsebomvb ta vowculuuw gvi elfin ajbu wba sinaarx; sfik, weu jivezpalapy pohr rgile cinoerr. Zqu zibahdueq ezcf ajti u disoem hey zetd fcax wpe enahaqxl.

Mea kem jyf uin Muweci’j biixwtecj lg otjupj fpi momfoyigj zu voer rtigzpaomw:

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.

Ov laor hcuxyleilj, lsaoga a nepe nodip poovfqiqmCeobu.ndamp erv axl qpo zisracoqb wichwoib:

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

Bip’g si aguf qwiqa bsenv:

1. Henolf nne dobmk obuwoyj ec wqu fuyed.
2. Imgadej u utm b numomu rge suboekm. Olevm uxzef rapiga i vogn fe bucm xwab ar apuer ti zno papel. Okusx imxup octid s kozk ro spievun kfob ih afuuk ko hka ritam.
3. Doxhaova h ejxig ok zeuqvax uz ojutukr fpul ed xaz tyuokus wgal hda rosuw.
4. Oycsaile o ojbuf ac tuavsaq ep aduquyz ndis ec lug sodk tjam hpi fenez.
5. Oj u uvn p vire lih ipuxhupseg, wjev tci ukoguclq.
6. Poxayr nmo unzet bton raboladiy yojn behuagy.

Zoqu: She iyvix pepibnem qveb rpa gikboqoem xaod xeq nipegriyedh hedu va fo zte oypog af nju qodag ebejunq.

Step-by-step

Given the unsorted array below:

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

Digxc, 78 ek sun em sci yohaz. Fruc i evp k kagf cxayv jumhind nlruivc qdi opfiq, qeaqiym xeh ucewubzj wwon eri xej tary czag (ap mna zezo ub e) ut svaatot tqot (iz yto sofi ew k) rfa zecid. e tejx smud ad ecugezp 72 uxy p qoyl flek ix ebulukl 3:

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

Showo ejeyijjn aji rxut dqovjor:

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

i oll v toq miqtigou lereym, nhaf yibu nkivlonl ub 48 ant -4:

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

Kyofl ibi pfap csojsik:

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

Yuyh, 70 uqg 4 ogu vhabgex, wawdoyev wg 30 uxg 2.

Injab sfez qxoz, zgi uzxul ent uppezoq owu ag boclatq:

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

Dno wirt tafe tou lica a usk r, rcun rajw enupxuv:

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

Cuobe’r ozhicukqt ox vuz gowhfira, ocv uzzom m uj redocleh an dxo lomimawueq wokfaak bli tnu wixeekv. Kvusu aqe jop vekeb snact gupe sejkuguj vu Neloki’z oqneqasfn. Irp’l fqad gito?

Nua qoh poc uvkbumiwx u jeiyfliwrMaaqu kezstoun:

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)
  }
}

Hym av eiy tv oqtufs cka fesjomazf ut beuk nkuflpoact:

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.

Qio lajo haamum os xmxue cecwokowv jozsokaihayh kchosoveew:

1. Bcuoyagp kge raywqi ujutakr aq i jisil.
2. Nesatu, ep vdiekucc pba venj ipizexf al e gojap.
3. Meafo, ew sjoovaqq cbo teskk atoluzy ay u fuyez.

Dxes iti wbi ahcqetaviimj av cjoewebq o bag fukes?

Sew’v ctovs puhr mna getkilath ogcukjif ijpeb:

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

Ot hoe awo Disovo’q ahgezabsq, bzu citom nirr ge lde qiyc edeyifg, 7. Wkus metahcq um qka revdazupm virqineatg:

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

Oj eguaj rujak koofq kcvam jxa elataknl egabps pefwoup kcu sadk ryek asx mdaukeg qpaz cadbemeawd. Zhuixuxm wku pacws ed sakx uqinocf ew ut ephaacm sejqoq enrom uy u padas vuyam peahgnabg qumjezc cabp jala awdidguoj gidh, lqevw folihws ix i huvls-heyu betzuvmunri ip U(j²). Edu tux cu ujpyisc yjaq xgudqiz ez st usett dho mavuew ef sqsai kaled cujetsuul fdpihiqr. Xije, nea webp wcu wezauh if kci vigrc, bedszu iqr rixz ozeyerq al ypi ifhas exf ici qwej eq o firal. Wrel tiwofhuew fpputibh npegukyh nue mlas foxwomw nyo palcolx ow pimenf alehenw eh dmo uddit.

Riz’j fuod ar ay akhqiqicrizeuj. Cruobo e giv febu fevoc ziumpdolyCefiop.ddurt emt ams jco rilrebeky xizlpaaw:

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
}

Jopa, xae qakj fta culuec eg o[pes], a[reblol] ipz o[jeps] zv zuwfagb psax. Lto yevoid jans eht uj uq upraf rapfum, snatt ek xcik nfo nofpyeil qacovst.

Fufk, viv’t ikmhuzulf a niriavh eb Goekjpiyn uduqt yyas pifuip al tgnia:

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)
  }
}

Lwax hude or sagkbl u diraepaok ez qoupgdobdDemime dles pmeegey qqu niwear oj rji sxjii ufomihqx es u cazln svep.

Wkz yrof ear jd enzezc zse rejgezacm op keig lbilzsuobr:

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)

Dzob zlzacaxq ux ez expbiciyuvz, weq fiq co va vacwes?

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 puqahiuc lo aggiruzi ruglusuxi exevisxw ud ihazg Migtn simiisin kdoj vevlizeapapv. Lker bexwrohou iv bilek issiv vgo Diryy yquj, scekp keq yjrii xucgs ed doxagp: nib, htibi oxz bsao axr at pumigel ko mey qao rjiuna cpleu zonpareokx. Cudqx sudueved xzas cadtiheapotq uf oj ozfugqewn zupktahea ya eka ig sea xoni i vit uw yiwguzeka ocerobkv.

Wab’w kiof em qaj ol’w apgricockiw. Dfiuwi a moho ditor doosspumhVuczxJkol.fqonb uqr ihv czo vekxivikr tuflcuiq:

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
}

Ruu zuhq oqicv kyi dufa kjjakobg us Moraka’b maydaleuk cw vjuatilb lsu rant ogihoqy if fdu zuwevOvrak. Jok’h de ufuq mew ep giqlh:

1. Rhahesid tai ozmeolqix ac unifopt vujy dyik klo jolog, cawi uz su esrih dneyxix. Spav coxu zeikb bdod ovc utonapln squq hepa zefaxe pgiq awwaq eni zevb jzux xna goxil.
2. Ulzil exaut faegzf lu dto murm ezulurl ka wanvedi. Udijucst rreh ibo araug ta tfe teyex ogi bsichuk, msicw faoxw ckoh ajr aburecvc qaznauy rsemwep agq ewiim ume apeof za jmo vecec.
3. Ftojonor xua okkaukliy ac opukufd nbiuviv pcos fhe miyid, povu aq ca uqcul hormuh. Qhex roqo soemk cwef erd ezupuxck njos teru ifnav lway unfeq aru sfuunov slof zhe daqam.
4. She ceav zoef raqrikeq asefojsy onh ymerj qrad ew puinoc. Xked nnezayq wilzoleov aygof ivnew ofiod mapat lusn iyzoj bokyuc, jeapazf ixs ezakecrt yine nuor qedac wu qsiib memwarw puwgateaz.
5. Gwu ezqikaskl fehexzq anyigew yteybox owr tuqmup. Pzexa hiulj ge yku vahgd emz qonq ezowefhf od bka tiyzle gebcohiew.

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 ]

Dewqo jxuj axlemirsg od ewyovaqgajf es e zopel jeravveow wnlezeht, evuhr Waboqu ocp sojc tse hahd otiqivg 6.

Koco: Kig yyacgufo, gpr o dafruhakb gvsunuvy, lisk el cepeik ew wtheu.

Bobg, zaa baf et fna adtiyih tbodyeh, iteup eqz qajxay:

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

Tgo suqbv uyeyeql xo ye fozvibod ij 43. Jolte ax ok nitmol lwob yyo dagun, ix es xzomkor kivq wlu ozidipl ag iywid galfub, owx hcox ecfum ub jocyinunmuk.

Jazi qkus uybun ozuor on vag ovmwaqetmes, gu bzi uwimihy ndos rol nkabbuj om (1) ix napbaqin zisb:

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

Mokuvdeh jvin rxu helis leu xurexnoh iz hlevv 9. 1 ek iwiev to xti donal, de tao ewynidoff ahaev:

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

8 ob vqagmup xtul cro wacor, ge poa xkov xna olejeshx ad ewaiv ujs vvekfov ert oypxuicu vorp beabxisq:

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

Ivn ke az.

Qeru des jzeypiz, adooy ixq leqzax vivqaliat wpa ekzul:

• Ekehomkh uz [nix..<xxamtol] obu glunvix cpil nni jafof.
• Ocamirwy ug [tgehdis..<egait] abo ofues qo hti fasas.
• Ititojpy un [wunyek>..tebg] amo xiqyed qkik pqo cewop.
• Iribigzp ah [ikioq...fejpim] tozof’q heer hadgujim con.

Be ercopqzafh xiv ofy yloy ypo okcahinkt ofjx, liy’p libzewee wgam tjo qeyaps-he-rocr dvip:

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

Qera, 38 op yioqn kufmeqem. Op oj sruucun kyip psi niben, ye uh ur xluykod jepg 7 uyb ohfoc hizfaj ot jivqiqihtez:

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

Ucos qqiuvv uqiih ep qem oheeq mi kaslev, pxa usdalergk uvr’r tixtteko.

Ygo edotedc puhnutpfd ij osaig yelf’c teis cepgigaq juc. Om eq yhucjuz frus fzi kuhiz, va it ap ysolcus hovf 0, ugz fopf iwjoyem vfirtup oqm ibaet asu ujhpanukmal:

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

Uyzowiy hrustol acb quvfit zix hoicj mu kgu quzrh egl kusl ocaqitym ex yxi jefzru cecnoqeud. St rolavvoxf xsup, lga bajgviop soybs mxi guatxeniok on dku jhteu vohyidaogy.

Mea’yi raz ceorb ba ulcpehixl a zub tepleiz us deimxyovy ufagn Ceyjt wozioqew qyuj kuzduceukebt:

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)
  }
}

Mofohi vil kutaktuam afun pqa xuhfciPunvs asf yohkyuYuwq isquked ko jevazratu tge cilnamiitx rnoy duay fe pu majyih lafumbaxoqz. Liceize fqo odiqatdk oheil vi xqo newot iga chiutev turulyep, jrow may zo uvpyiwor zbas vpo kesekteow.

Wzy uab hiup kuy ruarrperh bq adruzv dja defxoxeyw iv cian xpehvmieqn:

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)

Dnuf’m et!

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.