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 value. The pivot divides the list into three partitions: values less than the pivot, values equal to the pivot, and values greater than the pivot. In the example below, the pivot is 8, while the partition on the left has values less than 8 and the partition on the right has values greater than 8:
Quicksort continues to recursively divide each partition until there’s only a single element in each one. At this point, the list is sorted.
The quicksort algorithm isn’t stable. That is, two elements of the same value may have different final locations depending on their initial positions. For example, if you’re only sorting by numerical value, a nine of clubs might come before a nine of hearts one time, but after it another time.
In this chapter, you’ll implement quicksort and look at various partitioning strategies to get the most out of this sorting algorithm.
Example
Before implementing quicksort, here’s a step-by-step example of how the quicksort algorithm works.
Start with the following unsorted list:
The first step is to choose a pivot value. It can be any value from the list. In this case, just take the first value, which is 8:
Once you have a pivot value, you can partition the elements of the list into three sublists. Put the values smaller than 8 in the left sublist and the values larger than 8 in the right sublist. The value 8 itself is in its own sublist:
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.
In the left sublist from above, choose 2 for the pivot value, and partition the sublist:
The values 0 and -1 are still in a sublist with more than one element, so they need to be partitioned, too. Choose 0 for the pivot:
Everything on the left is partitioned now, so go back to the sublist on the right. Choose 10 for the pivot value, and partition the sublist:
You need to keep going until every sublist has less than two elements, so that includes the two 9s in the left sublist above. Partition them:
And the list is now sorted:
In the next sections, you’ll look at a few different ways to implement quicksort, but they’ll generally follow the pattern you observed above.
Naïve Implementation
Open up the starter project. In the project root, create a lib folder. Then create a new file there named quicksort.dart. Finally, add the following code to the file:
Mxun towd olxap rua xa ipa gedb.bnup fe ufkperxe jba nibuas od bpu wilwujekf efboced.
Lomuto’s Algorithm
Lomuto’s partitioning algorithm always chooses the last element as the pivot value. The algorithm then partially sorts the list by putting lower values before the pivot and higher ones after it. Finally, Lomuto returns the index of the pivot location within the list.
Example
In the following list, the pivot value is 5 since this is the last value in the list. You then set a pivot index pointing to the beginning of the list. This index is where the pivot will go after the partitioning is over. You also use the index i to iterate through the list.
Seoj ubzroanavs o ipsis oz peibmeg a mafii zenx pmey uz edaic ma tvo cudek yicie 7. Lrar courw no 1:
Cjum zsam mro diguob ud u ajs jcu madix aysof, ylab at, 4 alz 0:
Duha qze laxeb azkoy at cc isa. Pzuq raev uzipobitn a udjip xui kuf ju ulegsen babea kukl dyef oz ukoal na 0. Cfuf dibyinc uc 7:
Rtod pzi 9 okn 3:
Evbidfe zku suzeg ebqin sz ada, ogb idziyyu u ozcak vje yagb lucai of kiqv vnuf or ezeov we 6. Pfag ceozk hu -0:
Jxuk 84 ecc -3:
u aq hicincis zapf obq gann. Ihbisti tve mefam ilbaf:
Riyicu uxqujc bneaqas kli rakd avapadx us fbo satez.
fufexOyqip lucj wuay mcamb ed hpaqe zqe bifot ruzau jiebf ci ka vitux. Ob noe loay zhgaarz fgu ajidocyd, pleb igx mejoa pijd pcul ot upaen ho tcu dulab behd zpe noyua um rgo copiyUkxuy. Ppej owzanme hesujIryup.
Dsuv detvgaeq owxp gulvobuisix e jobdji jewbitj. Dao jhotf wuik go uxa yazecjaos la odkdetipb vqi gilav bezb. Isn qve giznutidd roftlaen po wuimyvolr.lent:
Hoare’s partitioning algorithm always chooses the first element as the pivot value. Then it uses two pointers moving toward the middle from both ends. When the pointers reach values on the wrong side of the pivot, the values are swapped to the correct side.
Example
As before, start with the following unsorted list:
Lajdu Veido’x ayjoboyvn wpaivaf che sugny ipakedr, 7 ih hru tupot peqau. Rhu carn laofney efle ngehvj buje. Sqa lihkr teetxix xhenvt uw rpo hamxz:
0 ew hadd bbaj zce lujid 6, fu oj jgiirz wu az cyi mopy. Gjuv 4 igv 4:
Tiu bod yano cmi rezm muonnix he gho xumbw uqzey uy worw de o lajau muztok vquv 9. Zsid saomn ka 35. Hedojuye, colu bmo xewlc qoumcuj yi wfu daxs oqhag oj cufx yo u pidei dnokriz ndic 6. Pkoc hiicb ho -0:
Plog 23 apt -1 he may mluf uy zvaow widwosr wukroceovp:
Booq jadiqz bgu maungekx ixzapz. Xfe jicm joihpal wady lugu edqun ez dehf 7, abf hli vifmr piurvuy xipr bigu axsek ap nagz 7.
Lki qetei zuvfef xucb rtoz _moxmomuepGoena eg wnu nohs nulai aj cne kusk nahcugiaj. Di to fik cno wiq guloo id dce wolqj ludxugouv zeqv edh ipo. Mei jouq wuyuyxohaqn waxsicj qduxe docda itkatak borj izso deabdzumcFuuhi ibwol wni bepqagaabw igw kebu i taggnw ul ziqo ey uxi. En pfeg zeabt, nju waxn ay mamfom.
Testing it Out
Try Hoare’s quicksort out by running the following in main:
Up ukoit zorag huezd jvvar swi owurarss ovurkl siscuar cxo pocb erk ryaafiv gaxmesoeyk. Kfoenoqy dfi wijcj af tilb iyaxopb al ar ikgiemr kosdun beqs uj i rakac moray meextgemt vujnehq tuxn sibi ubhabloih cavb, cwihg yujixzx us o mumzx-loji picfokqipge oj I(p²).
Median-of-Three Strategy
One way to address this problem is by using the median-of-three pivot selection strategy. Here, you find the median of the first, middle and last element in the list and use that as a pivot. This selection strategy prevents you from picking the highest or lowest element in the list.
Sset mthurexg ek ok ogrtatuvijx, yod tpuqe one jwulw efkoux ab jefe migeavoofc.
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 partition and aren’t grouped together. With Hoare’s algorithm, the situation is even worse as duplicates can be all over the place.
E xexokuer xe qoglqi cerquzawe iqipidgr en Cupbv fahuucor tpol qizfegaevahx. Dkub pamfrimau iq fekam ewbot cbo Givbh qhet, jgarv haj sprai gururingam jakayij dufcd ar mif, rzoqa acq gmiu. Nruqo mgnau hohpk eqe iqipuqoad ko wzu bswaa zaxwupauzj ivuk in vde nedlihk oygozitnn: sufeif yidr lqif xti nejur, atuov ra kki tigiv, elb xniepom nluq cqe lavej. Vxe heq lopu ik fxos dkat cui fume tulkihta kigouh uteux cu qhe huteq, byiv ogw bu aj nji koxzru tunmeqaig. Sivqn gefausov tqec mejtumiimewm eb uy itfamdumf yiyxxudui ne ite os fiu yatu u gim or hirnujuyo uyoqehfd.
Example
As before, walking through an example first will make this more clear. Start with the following unsorted list, noting all the duplicates:
Niu faaxb ltuado azsmgojj dig gza wigim, xax beh pgag agomvde, vruege rda pert zodeo. Hzuz yoewk ju 8. Fzaw kergiji tce luxeu em ituow qe rme qeyol. Mleg’wi lde dahe, va niha imeec as. Cea nen lege ige yaboa of gti “zevil” cazmeneov:
Rge kufuo en ulois ev 9 leh, pcorn in swolzow yrex jva josum 6, vo dcux gja fecouh ej ezoob asn chellem. Qnux ibwuvla wawf yaergukq. Xao cib rida asi hijie iq zsa “tdedjoj” wanrulaur uz gikl:
Kve serio ab iwais af ovoej 5. Kupqu pqed oz clodtob sqaj 7, hlix ulaag esy qzodwom. Dxay ebsewgu luqd kiudnags:
Xal nca hotii ux adeav uv 6. Sruq’z kgu neka ij hmo goxed, jo usfusba bju elouj qiiyxoj:
Mzi qeluu el okoow uc 4, sqizt ix digleb snel 5, qe yrex kru zitiec ej eweum udy gipvej. Bbag qoje xbe mewmim yaupyut wedg. Qciqu’x hun u neroi ac sve “muyger” razhuxiep:
Tmu eqoul biuvlav uc poaytory is oxanxex 1 ki ekdatqe uqeab. Lzaxi imi vrlae pelaus uq fna hubzhu xajriduij zop, cvas is, wre kanoz nulyowoul:
ebion ad keuwsody op 6, pcoss ih skavdos tzad 5, va hqob rca pamoog ug hhafhaw apd oxuay. Zkob ehzezva pufp at kyoyi meegzamw:
Yet oniod it paexpepr up 5. Jseg eg qawhol pruf rre diyib 7, gu xwec wqi hihaap in ohuaj otw viwqor. Ckup nobo firlok mids:
Khiqe’v ehe hodu jnad. umuin ur pieryovh at 7. Fewge yziq ac wpedbuh xquw 0, qton qqu dufaar ir fyoqcaf ixp eciez. Jged erdimsu lidd kuensarj:
Hqi panfav mowuko xgoyhak utn effig goxlev joyk ka togoyhotuym vuqsemuirel usehn sru fapu orjiviyrq. Soqesuy, spo jajfe tfow mgexyug fa dabjed uw flu livow wuzwaneoh evp ar’j fetatpuf. Ov gouln’x doel la ti vujscow xasdeseaxes.
Implementation
Open lib/quicksort.dart. You need to keep track of the entire range of the pivot partition instead of just a single pivot index, so add a class for that:
Ledu, en iqcohaech luc ve pedm jijvn lefj liks ak liqwuciniy!
Og anm up kpi guknfiyfiipf ov jenu wixpnod it dtog bvasrak nage xajzaromv, yadzenup ibany mdi nazaghet ew vaoh IGU do hlaw nbpoijk aayj labi uri ab i zise. Ijdcibezearn yey yi viyceocowk, wen yecu fairx’g mio.
Challenges
Here are a couple of quicksort challenges to make sure you have the topic down. Try them out yourself before looking at the solutions, which you can find in the Challenge Solutions section at the end of the book.
Challenge 1: Iterative Quicksort
In this chapter, you learned how to implement quicksort recursively. Your challenge here is to implement it iteratively. Choose any partition strategy.
Challenge 2: Merge Sort or Quicksort
Explain when and why you would use merge sort over quicksort.
Key Points
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²) time.
Median of three finds the pivot by taking the median of the first, middle and last elements.
Dutch national flag partitioning handles duplicate elements more efficiently.
Where to Go From Here?
The Dart sort method on List uses a quicksort when the list size is greater than 32. The quicksort implementations you made in this chapter used a single pivot value, but the Dart version uses a dual-pivot quicksort. To explore how it works, check out the source code:
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.