8000 swift-algorithm-club/Quicksort at master · JackLu2012/swift-algorithm-club · GitHub
[go: up one dir, main page]

Skip to content
{"payload":{"allShortcutsEnabled":false,"path":"Quicksort","repo":{"id":197345451,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"JackLu2012","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2019-07-17T08:12:42.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/3068832?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1617920280.777492","canEdit":false,"refType":"branch","currentOid":"667d265e3520929aa22251751ac6b331af660506"},"tree":{"items":[{"name":"Images","path":"Quicksort/Images","contentType":"directory"},{"name":"Quicksort.playground","path":"Quicksort/Quicksort.playground","contentType":"directory"},{"name":"Tests","path":"Quicksort/Tests","contentType":"directory"},{"name":"Quicksort.swift","path":"Quicksort/Quicksort.swift","contentType":"file"},{"name":"README.markdown","path":"Quicksort/README.markdown","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.markdown","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eQuicksort\u003c/h1\u003e\u003ca id=\"user-content-quicksort\" class=\"anchor\" aria-label=\"Permalink: Quicksort\" href=\"#quicksort\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eGoal: Sort an array from low to high (or high to low).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eQuicksort is one of the most famous algorithms in history. It was invented way back in 1959 by Tony Hoare, at a time when recursion was still a fairly nebulous concept.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere's an implementation in Swift that should be easy to understand:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func quicksort\u0026lt;T: Comparable\u0026gt;(_ a: [T]) -\u0026gt; [T] {\n guard a.count \u0026gt; 1 else { return a }\n\n let pivot = a[a.count/2]\n let less = a.filter { $0 \u0026lt; pivot }\n let equal = a.filter { $0 == pivot }\n let greater = a.filter { $0 \u0026gt; pivot }\n\n return quicksort(less) + equal + quicksort(greater)\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e quicksort\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e a \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epivot\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eless\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003efilter\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e $0 \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e pivot \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eequal\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003efilter\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e $0 \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e pivot \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003egreater\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003efilter\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e $0 \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e pivot \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-en\"\u003equicksort\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eless\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e equal \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e quicksort\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003egreater\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003ePut this code in a playground and test it like so:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"let list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]\nquicksort(list)\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e14\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e27\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e5\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e26\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\u003cspan class=\"pl-en\"\u003equicksort\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003elist\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eHere's how it works. When given an array, \u003ccode\u003equicksort()\u003c/code\u003e splits it up into three parts based on a \"pivot\" variable. Here, the pivot is taken to be the element in the middle of the array (later on you'll see other ways to choose the pivot).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAll the elements less than the pivot go into a new array called \u003ccode\u003eless\u003c/code\u003e. All the elements equal to the pivot go into the \u003ccode\u003eequal\u003c/code\u003e array. And you guessed it, all elements greater than the pivot go into the third array, \u003ccode\u003egreater\u003c/code\u003e. This is why the generic type \u003ccode\u003eT\u003c/code\u003e must be \u003ccode\u003eComparable\u003c/code\u003e, so we can compare the elements with \u003ccode\u003e\u0026lt;\u003c/code\u003e, \u003ccode\u003e==\u003c/code\u003e, and \u003ccode\u003e\u0026gt;\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eOnce we have these three arrays, \u003ccode\u003equicksort()\u003c/code\u003e recursively sorts the \u003ccode\u003eless\u003c/code\u003e array and the \u003ccode\u003egreater\u003c/code\u003e array, then glues those sorted subarrays back together with the \u003ccode\u003eequal\u003c/code\u003e array to get the final result.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eAn example\u003c/h2\u003e\u003ca id=\"user-content-an-example\" class=\"anchor\" aria-label=\"Permalink: An example\" href=\"#an-example\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLet's walk through the example. The array is initially:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eFirst, we pick the pivot element. That is \u003ccode\u003e8\u003c/code\u003e because it's in the middle of the array. Now we split the array into the less, equal, and greater parts:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"less: [ 0, 3, 2, 1, 5, -1 ]\nequal: [ 8, 8 ]\ngreater: [ 10, 9, 14, 27, 26 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eless: [ 0, 3, 2, 1, 5, -1 ]\nequal: [ 8, 8 ]\ngreater: [ 10, 9, 14, 27, 26 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis is a good split because \u003ccode\u003eless\u003c/code\u003e and \u003ccode\u003egreater\u003c/code\u003e roughly contain the same number of elements. So we've picked a good pivot that chopped the array right down the middle.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNote that the \u003ccode\u003eless\u003c/code\u003e and \u003ccode\u003egreater\u003c/code\u003e arrays aren't sorted yet, so we call \u003ccode\u003equicksort()\u003c/code\u003e again to sort those two subarrays. That does the exact same thing: pick a pivot and split the subarray into three even smaller parts.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's just take a look at the \u003ccode\u003eless\u003c/code\u003e array:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0, 3, 2, 1, 5, -1 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0, 3, 2, 1, 5, -1 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe pivot element is the one in the middle, \u003ccode\u003e1\u003c/code\u003e. (You could also have picked \u003ccode\u003e2\u003c/code\u003e, it doesn't matter.) Again, we create three subarrays around the pivot:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"less: [ 0, -1 ]\nequal: [ 1 ]\ngreater: [ 3, 2, 5 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eless: [ 0, -1 ]\nequal: [ 1 ]\ngreater: [ 3, 2, 5 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe're not done yet and \u003ccode\u003equicksort()\u003c/code\u003e again is called recursively on the \u003ccode\u003eless\u003c/code\u003e and \u003ccode\u003egreater\u003c/code\u003e arrays. Let's look at \u003ccode\u003eless\u003c/code\u003e again:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0, -1 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0, -1 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAs pivot we pick \u003ccode\u003e-1\u003c/code\u003e. Now the subarrays are:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"less: [ ]\nequal: [ -1 ]\ngreater: [ 0 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eless: [ ]\nequal: [ -1 ]\ngreater: [ 0 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003eless\u003c/code\u003e array is empty because there was no value smaller than \u003ccode\u003e-1\u003c/code\u003e; the other arrays contain a single element each. That means we're done at this level of the recursion, and we go back up to sort the previous \u003ccode\u003egreater\u003c/code\u003e array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThat \u003ccode\u003egreater\u003c/code\u003e array was:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 3, 2, 5 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 3, 2, 5 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis works just the same way as before: we pick the middle element \u003ccode\u003e2\u003c/code\u003e as the pivot and fill up the subarrays:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"less: [ ]\nequal: [ 2 ]\ngreater: [ 3, 5 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eless: [ ]\nequal: [ 2 ]\ngreater: [ 3, 5 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNote that here it would have been better to pick \u003ccode\u003e3\u003c/code\u003e as the pivot -- we would have been done sooner. But now we have to recurse into the \u003ccode\u003egreater\u003c/code\u003e array again to make sure it is sorted. This is why picking a good pivot is important. When you pick too many \"bad\" pivots, quicksort actually becomes really slow. More on that below.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eWhen we partition the \u003ccode\u003egreater\u003c/code\u003e subarray, we find:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"less: [ 3 ]\nequal: [ 5 ]\ngreater: [ ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003eless: [ 3 ]\nequal: [ 5 ]\ngreater: [ ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd now we're done at this level of the recursion because we can't split up the arrays any further.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThis process repeats until all the subarrays have been sorted. In a picture:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/JackLu2012/swift-algorithm-club/blob/master/Quicksort/Images/Example.png\"\u003e\u003cimg src=\"/JackLu2012/swift-algorithm-club/raw/master/Quicksort/Images/Example.png\" alt=\"Example\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNow if you read the colored boxes from left to right, you get the sorted array:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis shows that \u003ccode\u003e8\u003c/code\u003e was a good initial pivot because it appears in the middle of the sorted array too.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eI hope this makes the basic principle clear of how quicksort works. Unfortunately, this version of quicksort isn't very quick, because we \u003ccode\u003efilter()\u003c/code\u003e the same array three times. There are more clever ways to split up the array.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003ePartitioning\u003c/h2\u003e\u003ca id=\"user-content-partitioning\" class=\"anchor\" aria-label=\"Permalink: Partitioning\" href=\"#partitioning\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eDividing the array around the pivot is called \u003cem\u003epartitioning\u003c/em\u003e and there are a few different partitioning schemes.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIf the array is,\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eand we choose the middle element \u003ccode\u003e8\u003c/code\u003e as a pivot then after partitioning the array will look like this:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0, 3, 2, 1, 5, -1, 8, 8, 10, 9, 14, 27, 26 ]\n ----------------- -----------------\n all elements \u0026lt; 8 all elements \u0026gt; 8\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0, 3, 2, 1, 5, -1, 8, 8, 10, 9, 14, 27, 26 ]\n ----------------- -----------------\n all elements \u0026lt; 8 all elements \u0026gt; 8\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe key thing to realize is that after partitioning the pivot element is in its final sorted place already. The rest of the numbers are not sorted yet, they are simply partitioned around the pivot value. Quicksort partitions the array many times over, until all the values are in their final places.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThere is no guarantee that partitioning keeps the elements in the same relative order, so after partitioning around pivot \u003ccode\u003e8\u003c/code\u003e you could also end up with something like this:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 3, 0, 5, 2, -1, 1, 8, 8, 14, 26, 10, 27, 9 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 3, 0, 5, 2, -1, 1, 8, 8, 14, 26, 10, 27, 9 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe only guarantee is that to the left of the pivot are all the smaller elements and to the right are all the larger elements. Because partitioning can change the original order of equal elements, quicksort does not produce a \"stable\" sort (unlike \u003ca href=\"/JackLu2012/swift-algorithm-club/blob/master/Merge%20Sort\"\u003emerge sort\u003c/a\u003e, for example). Most of the time that's not a big deal.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eLomuto's partitioning scheme\u003c/h2\u003e\u003ca id=\"user-content-lomutos-partitioning-scheme\" class=\"anchor\" aria-label=\"Permalink: Lomuto's partitioning scheme\" href=\"#lomutos-partitioning-scheme\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eIn the first example of quicksort I showed you, partitioning was done by calling Swift's \u003ccode\u003efilter()\u003c/code\u003e function three times. That is not very efficient. So let's look at a smarter partitioning algorithm that works \u003cem\u003ein place\u003c/em\u003e, i.e. by modifying the original array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere's an implementation of Lomuto's partitioning scheme in Swift:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func partitionLomuto\u0026lt;T: Comparable\u0026gt;(_ a: inout [T], low: Int, high: Int) -\u0026gt; Int {\n let pivot = a[high]\n\n var i = low\n for j in low..\u0026lt;high {\n if a[j] \u0026lt;= pivot {\n (a[i], a[j]) = (a[j], a[i])\n i += 1\n }\n }\n\n (a[i], a[high]) = (a[high], a[i])\n return i\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e partitionLomuto\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003einout\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epivot\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ehigh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e low\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ej\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e low\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003ehigh \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e pivot \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n i \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ehigh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ehigh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e i\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTo test this in a playground, do:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]\nlet p = partitionLomuto(\u0026amp;list, low: 0, high: list.count - 1)\nlist // show the results\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e14\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e26\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e27\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e5\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ep\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003epartitionLomuto\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003elist\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e list\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\nlist // show the results\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNote that \u003ccode\u003elist\u003c/code\u003e needs to be a \u003ccode\u003evar\u003c/code\u003e because \u003ccode\u003epartitionLomuto()\u003c/code\u003e directly changes the contents of the array (it is passed as an \u003ccode\u003einout\u003c/code\u003e parameter). That is much more efficient than allocating a new array object.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003elow\u003c/code\u003e and \u003ccode\u003ehigh\u003c/code\u003e parameters are necessary because when this is used inside quicksort, you don't always want to (re)partition the entire array, only a limited range that becomes smaller and smaller.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003ePreviously we used the middle array element as the pivot but it's important to realize that the Lomuto algorithm always uses the \u003cem\u003elast\u003c/em\u003e element, \u003ccode\u003ea[high]\u003c/code\u003e, for the pivot. Because we've been pivoting around \u003ccode\u003e8\u003c/code 8000 \u003e all this time, I swapped the positions of \u003ccode\u003e8\u003c/code\u003e and \u003ccode\u003e26\u003c/code\u003e in the example so that \u003ccode\u003e8\u003c/code\u003e is at the end of the array and is used as the pivot value here too.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAfter partitioning, the array looks like this:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27 ]\n *\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27 ]\n *\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe variable \u003ccode\u003ep\u003c/code\u003e contains the return value of the call to \u003ccode\u003epartitionLomuto()\u003c/code\u003e and is 7. This is the index of the pivot element in the new array (marked with a star).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe left partition goes from 0 to \u003ccode\u003ep-1\u003c/code\u003e and is \u003ccode\u003e[ 0, 3, 2, 1, 5, 8, -1 ]\u003c/code\u003e. The right partition goes from \u003ccode\u003ep+1\u003c/code\u003e to the end, and is \u003ccode\u003e[ 9, 10, 14, 26, 27 ]\u003c/code\u003e (the fact that the right partition is already sorted is a coincidence).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eYou may notice something interesting... The value \u003ccode\u003e8\u003c/code\u003e occurs more than once in the array. One of those \u003ccode\u003e8\u003c/code\u003es did not end up neatly in the middle but somewhere in the left partition. That's a small downside of the Lomuto algorithm as it makes quicksort slower if there are a lot of duplicate elements.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eSo how does the Lomuto algorithm actually work? The magic happens in the \u003ccode\u003efor\u003c/code\u003e loop. This loop divides the array into four regions:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\u003ccode\u003ea[low...i]\u003c/code\u003e contains all values \u0026lt;= pivot\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003ea[i+1...j-1]\u003c/code\u003e contains all values \u0026gt; pivot\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003ea[j...high-1]\u003c/code\u003e are values we haven't looked at yet\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003ea[high]\u003c/code\u003e is the pivot value\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eIn ASCII art the array is divided up like this:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ values \u0026lt;= pivot | values \u0026gt; pivot | not looked at yet | pivot ]\n low i i+1 j-1 j high-1 high\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ values \u0026lt;= pivot | values \u0026gt; pivot | not looked at yet | pivot ]\n low i i+1 j-1 j high-1 high\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe loop looks at each element from \u003ccode\u003elow\u003c/code\u003e to \u003ccode\u003ehigh-1\u003c/code\u003e in turn. If the value of the current element is less than or equal to the pivot, it is moved into the first region using a swap.\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e In Swift, the notation \u003ccode\u003e(x, y) = (y, x)\u003c/code\u003e is a convenient way to perform a swap between the values of \u003ccode\u003ex\u003c/code\u003e and \u003ccode\u003ey\u003c/code\u003e. You can also write \u003ccode\u003eswap(\u0026amp;x, \u0026amp;y)\u003c/code\u003e.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003eAfter the loop is over, the pivot is still the last element in the array. So we swap it with the first element that is greater than the pivot. Now the pivot sits between the \u0026lt;= and \u0026gt; regions and the array is properly partitioned.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's step through the example. The array we're starting with is:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eInitially, the \"not looked at\" region stretches from index 0 to 11. The pivot is at index 12. The \"values \u0026lt;= pivot\" and \"values \u0026gt; pivot\" regions are empty, because we haven't looked at any values yet.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLook at the first value, \u003ccode\u003e10\u003c/code\u003e. Is this smaller than the pivot? No, skip to the next element.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow the \"not looked at\" region goes from index 1 to 11, the \"values \u0026gt; pivot\" region contains the number \u003ccode\u003e10\u003c/code\u003e, and \"values \u0026lt;= pivot\" is still empty.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLook at the second value, \u003ccode\u003e0\u003c/code\u003e. Is this smaller than the pivot? Yes, so swap \u003ccode\u003e10\u003c/code\u003e with \u003ccode\u003e0\u003c/code\u003e and move \u003ccode\u003ei\u003c/code\u003e ahead by one.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow \"not looked at\" goes from index 2 to 11, \"values \u0026gt; pivot\" still contains \u003ccode\u003e10\u003c/code\u003e, and \"values \u0026lt;= pivot\" contains the number \u003ccode\u003e0\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLook at the third value, \u003ccode\u003e3\u003c/code\u003e. This is smaller than the pivot, so swap it with \u003ccode\u003e10\u003c/code\u003e to get:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0, 3 | 10 | 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0, 3 | 10 | 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \"values \u0026lt;= pivot\" region is now \u003ccode\u003e[ 0, 3 ]\u003c/code\u003e. Let's do one more... \u003ccode\u003e9\u003c/code\u003e is greater than the pivot, so simply skip ahead:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0, 3 | 10, 9 | 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0, 3 | 10, 9 | 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]\n low high\n i\n j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow the \"values \u0026gt; pivot\" region contains \u003ccode\u003e[ 10, 9 ]\u003c/code\u003e. If we keep going this way, then eventually we end up with:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]\n low high\n i j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]\n low high\n i j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe final thing to do is to put the pivot into place by swapping \u003ccode\u003ea[i]\u003c/code\u003e with \u003ccode\u003ea[high]\u003c/code\u003e:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]\n low high\n i j\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]\n low high\n i j\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd we return \u003ccode\u003ei\u003c/code\u003e, the index of the pivot element.\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e If you're still not entirely clear on how the algorithm works, I suggest you play with this in the playground to see exactly how the loop creates these four regions.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003eLet's use this partitioning scheme to build quicksort. Here's the code:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func quicksortLomuto\u0026lt;T: Comparable\u0026gt;(_ a: inout [T], low: Int, high: Int) {\n if low \u0026lt; high {\n let p = partitionLomuto(\u0026amp;a, low: low, high: high)\n quicksortLomuto(\u0026amp;a, low: low, high: p - 1)\n quicksortLomuto(\u0026amp;a, low: p + 1, high: high)\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e quicksortLomuto\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003einout\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e low \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e high \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ep\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003epartitionLomuto\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003equicksortLomuto\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e p \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003equicksortLomuto\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e p \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis is now super simple. We first call \u003ccode\u003epartitionLomuto()\u003c/code\u003e to reorder the array around the pivot (which is always the last element from the array). And then we call \u003ccode\u003equicksortLomuto()\u003c/code\u003e recursively to sort the left and right partitions.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eTry it out:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]\nquicksortLomuto(\u0026amp;list, low: 0, high: list.count - 1)\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e14\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e26\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e27\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e5\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\u003cspan class=\"pl-en\"\u003equicksortLomuto\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003elist\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e list\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLomuto's isn't the only partitioning scheme but it's probably the easiest to understand. It's not as efficient as Hoare's scheme, which requires fewer swap operations.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eHoare's partitioning scheme\u003c/h2\u003e\u003ca id=\"user-content-hoares-partitioning-scheme\" class=\"anchor\" aria-label=\"Permalink: Hoare's partitioning scheme\" href=\"#hoares-partitioning-scheme\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis partitioning scheme is by Hoare, the inventor of quicksort.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is the code:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func partitionHoare\u0026lt;T: Comparable\u0026gt;(_ a: inout [T], low: Int, high: Int) -\u0026gt; Int {\n let pivot = a[low]\n var i = low - 1\n var j = high + 1\n\n while true {\n repeat { j -= 1 } while a[j] \u0026gt; pivot\n repeat { i += 1 } while a[i] \u0026lt; pivot\n\n if i \u0026lt; j {\n a.swapAt(i, j)\n } else {\n return j\n }\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e partitionHoare\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003einout\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epivot\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003elow\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e low \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ej\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e high \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003erepeat\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e j \u003cspan class=\"pl-c1\"\u003e-=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e pivot\n \u003cspan class=\"pl-k\"\u003erepeat\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e i \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e pivot\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e i \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e j \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eswapAt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e j\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e j\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTo test this in a playground, do:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"var list = [ 8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26 ]\nlet p = partitionHoare(\u0026amp;list, low: 0, high: list.count - 1)\nlist // show the results\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e14\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e27\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e5\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e26\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ep\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003epartitionHoare\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003elist\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e list\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\nlist // show the results\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNote that with Hoare's scheme, the pivot is always expected to be the \u003cem\u003efirst\u003c/em\u003e element in the array, \u003ccode\u003ea[low]\u003c/code\u003e. Again, we're using \u003ccode\u003e8\u003c/code\u003e as the pivot element.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe result is:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ -1, 0, 3, 8, 2, 5, 1, 27, 10, 14, 9, 8, 26 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ -1, 0, 3, 8, 2, 5, 1, 27, 10, 14, 9, 8, 26 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNote that this time the pivot isn't in the middle at all. Unlike with Lomuto's scheme, the return value is not necessarily the index of the pivot element in the new array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eInstead, the array is partitioned into the regions \u003ccode\u003e[low...p]\u003c/code\u003e and \u003ccode\u003e[p+1...high]\u003c/code\u003e. Here, the return value \u003ccode\u003ep\u003c/code\u003e is 6, so the two partitions are \u003ccode\u003e[ -1, 0, 3, 8, 2, 5, 1 ]\u003c/code\u003e and \u003ccode\u003e[ 27, 10, 14, 9, 8, 26 ]\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe pivot is placed somewhere inside one of the two partitions, but the algorithm doesn't tell you which one or where. If the pivot value occurs more than once, then some instances may appear in the left partition and others may appear in the right partition.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eBecause of these differences, the implementation of Hoare's quicksort is slightly different:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func quicksortHoare\u0026lt;T: Comparable\u0026gt;(_ a: inout [T], low: Int, high: Int) {\n if low \u0026lt; high {\n let p = partitionHoare(\u0026amp;a, low: low, high: high)\n quicksortHoare(\u0026amp;a, low: low, high: p)\n quicksortHoare(\u0026amp;a, low: p + 1, high: high)\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e quicksortHoare\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003einout\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e low \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e high \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ep\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003epartitionHoare\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003equicksortHoare\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e p\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003equicksortHoare\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e p \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eI'll leave it as an exercise for the reader to figure out exactly how Hoare's partitioning scheme works. :-)\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003ePicking a good pivot\u003c/h2\u003e\u003ca id=\"user-content-picking-a-good-pivot\" class=\"anchor\" aria-label=\"Permalink: Picking a good pivot\" href=\"#picking-a-good-pivot\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLomuto's partitioning scheme always chooses the last array element for the pivot. Hoare's scheme uses the first element. But there is no guarantee that these pivots are any good.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is what happens when you pick a bad value for the pivot. Let's say the array is,\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 7, 6, 5, 4, 3, 2, 1 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 7, 6, 5, 4, 3, 2, 1 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eand we're using Lomuto' C95B s scheme. The pivot is the last element, \u003ccode\u003e1\u003c/code\u003e. After pivoting, we have the following arrays:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" less than pivot: [ ]\n equal to pivot: [ 1 ]\ngreater than pivot: [ 7, 6, 5, 4, 3, 2 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e less than pivot: [ ]\n equal to pivot: [ 1 ]\ngreater than pivot: [ 7, 6, 5, 4, 3, 2 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow recursively partition the \"greater than\" subarray and get:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" less than pivot: [ ]\n equal to pivot: [ 2 ]\ngreater than pivot: [ 7, 6, 5, 4, 3 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e less than pivot: [ ]\n equal to pivot: [ 2 ]\ngreater than pivot: [ 7, 6, 5, 4, 3 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd again:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" less than pivot: [ ]\n equal to pivot: [ 3 ]\ngreater than pivot: [ 7, 6, 5, 4 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e less than pivot: [ ]\n equal to pivot: [ 3 ]\ngreater than pivot: [ 7, 6, 5, 4 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd so on...\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThat's no good, because this pretty much reduces quicksort to the much slower insertion sort. For quicksort to be efficient, it needs to split the array into roughly two halves.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe optimal pivot for this example would have been \u003ccode\u003e4\u003c/code\u003e, so we'd get:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" less than pivot: [ 3, 2, 1 ]\n equal to pivot: [ 4 ]\ngreater than pivot: [ 7, 6, 5 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e less than pivot: [ 3, 2, 1 ]\n equal to pivot: [ 4 ]\ngreater than pivot: [ 7, 6, 5 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eYou might think this means we should always choose the middle element rather than the first or the last, but imagine what happens in the following situation:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ 7, 6, 5, 1, 4, 3, 2 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ 7, 6, 5, 1, 4, 3, 2 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNow the middle element is \u003ccode\u003e1\u003c/code\u003e and that gives the same lousy results as in the previous example.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIdeally, the pivot is the \u003cem\u003emedian\u003c/em\u003e element of the array that you're partitioning, i.e. the element that sits in the middle of the sorted array. Of course, you won't know what the median is until after you've sorted the array, so this is a bit of a chicken-and-egg problem. However, there are some tricks to choose good, if not ideal, pivots.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eOne trick is \"median-of-three\", where you find the median of the first, middle, and last element in this subarray. In theory that often gives a good approximation of the true median.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAnother common solution is to choose the pivot randomly. Sometimes this may result in choosing a suboptimal pivot but on average this gives very good results.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is how you can do quicksort with a randomly chosen pivot:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func quicksortRandom\u0026lt;T: Comparable\u0026gt;(_ a: inout [T], low: Int, high: Int) {\n if low \u0026lt; high {\n let pivotIndex = random(min: low, max: high) // 1\n\n (a[pivotIndex], a[high]) = (a[high], a[pivotIndex]) // 2\n\n let p = partitionLomuto(\u0026amp;a, low: low, high: high)\n quicksortRandom(\u0026amp;a, low: low, high: p - 1)\n quicksortRandom(\u0026amp;a, low: p + 1, high: high)\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e quicksortRandom\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003einout\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e low \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e high \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epivotIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003erandom\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003emin\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e max\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 1\n\n \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epivotIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ehigh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ehigh\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epivotIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 2\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ep\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003epartitionLomuto\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003equicksortRandom\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e p \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003equicksortRandom\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e p \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThere are two important differences with before:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003erandom(min:max:)\u003c/code\u003e function returns an integer in the range \u003ccode\u003emin...max\u003c/code\u003e, inclusive. This is our pivot index.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eBecause the Lomuto scheme expects \u003ccode\u003ea[high]\u003c/code\u003e to be the pivot entry, we swap \u003ccode\u003ea[pivotIndex]\u003c/code\u003e with \u003ccode\u003ea[high]\u003c/code\u003e to put the pivot element at the end before calling \u003ccode\u003epartitionLomuto()\u003c/code\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eIt may seem strange to use random numbers in something like a sorting function, but it is necessary to make quicksort behave efficiently under all circumstances. With bad pivots, the performance of quicksort can be quite horrible, \u003cstrong\u003eO(n^2)\u003c/strong\u003e. But if you choose good pivots on average, for example by using a random number generator, the expected running time becomes \u003cstrong\u003eO(n log n)\u003c/strong\u003e, which is as good as sorting algorithms get.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eDutch national flag partitioning\u003c/h2\u003e\u003ca id=\"user-content-dutch-national-flag-partitioning\" class=\"anchor\" aria-label=\"Permalink: Dutch national flag partitioning\" href=\"#dutch-national-flag-partitioning\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eBut there are more improvements to make! In the first example of quicksort I showed you, we ended up with an array that was partitioned like this:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ values \u0026lt; pivot | values equal to pivot | values \u0026gt; pivot ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ values \u0026lt; pivot | values equal to pivot | values \u0026gt; pivot ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eBut as you've seen with the Lomuto partitioning scheme, if the pivot occurs more than once the duplicates end up in the left half. And with Hoare's scheme the pivot can be all over the place. The solution to this is \"Dutch national flag\" partitioning, named after the fact that the \u003ca href=\"https://en.wikipedia.org/wiki/Flag_of_the_Netherlands\" rel=\"nofollow\"\u003eDutch flag\u003c/a\u003e has three bands just like we want to have three partitions.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe code for this scheme is:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func partitionDutchFlag\u0026lt;T: Comparable\u0026gt;(_ a: inout [T], low: Int, high: Int, pivotIndex: Int) -\u0026gt; (Int, Int) {\n let pivot = a[pivotIndex]\n\n var smaller = low\n var equal = low\n var larger = high\n\n while equal \u0026lt;= larger {\n if a[equal] \u0026lt; pivot {\n swap(\u0026amp;a, smaller, equal)\n smaller += 1\n equal += 1\n } else if a[equal] == pivot {\n equal += 1\n } else {\n swap(\u0026amp;a, equal, larger)\n larger -= 1\n }\n }\n return (smaller, larger)\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e partitionDutchFlag\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003einout\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e pivotIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epivot\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epivotIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esmaller\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e low\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eequal\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e low\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elarger\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e high\n\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e equal \u003cspan class=\"pl-c1\"\u003e\u0026lt;=\u003c/span\u003e larger \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eequal\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e pivot \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eswap\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e smaller\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e equal\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n smaller \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n equal \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eequal\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e pivot \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n equal \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eswap\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e equal\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e larger\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n larger \u003cspan class=\"pl-c1\"\u003e-=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003esmaller\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e larger\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis works very similarly to the Lomuto scheme, except that the loop partitions the array into four (possibly empty) regions:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ccode\u003e[low ... smaller-1]\u003c/code\u003e contains all values \u0026lt; pivot\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003e[smaller ... equal-1]\u003c/code\u003e contains all values == pivot\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003e[equal ... larger]\u003c/code\u003e contains all values \u0026gt; pivot\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003e[larger ... high]\u003c/code\u003e are values we haven't looked at yet\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eNote that this doesn't assume the pivot is in \u003ccode\u003ea[high]\u003c/code\u003e. Instead, you have to pass in the index of the element you wish to use as a pivot.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAn example of how to use it:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"var list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]\npartitionDutchFlag(\u0026amp;list, low: 0, high: list.count - 1, pivotIndex: 10)\nlist // show the results\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e9\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e14\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e27\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e5\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e8\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e26\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\u003cspan class=\"pl-en\"\u003epartitionDutchFlag\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003elist\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e list\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e pivotIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\nlist // show the results\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eJust for fun, we're giving it the index of the other \u003ccode\u003e8\u003c/code\u003e this time. The result is:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ -1, 0, 3, 2, 5, 1, 8, 8, 27, 14, 9, 26, 10 ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ -1, 0, 3, 2, 5, 1, 8, 8, 27, 14, 9, 26, 10 ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eNotice how the two \u003ccode\u003e8\u003c/code\u003es are in the middle now. The return value from \u003ccode\u003epartitionDutchFlag()\u003c/code\u003e is a tuple, \u003ccode\u003e(6, 7)\u003c/code\u003e. This is the range that contains the pivot value(s).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is how you would use it in quicksort:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func quicksortDutchFlag\u0026lt;T: Comparable\u0026gt;(_ a: inout [T], low: Int, high: Int) {\n if low \u0026lt; high {\n let pivotIndex = random(min: low, max: high)\n let (p, q) = partitionDutchFlag(\u0026amp;a, low: low, high: high, pivotIndex: pivotIndex)\n quicksortDutchFlag(\u0026amp;a, low: low, high: p - 1)\n quicksortDutchFlag(\u0026amp;a, low: q + 1, high: high)\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e quicksortDutchFlag\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-k\"\u003einout\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e low \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e high \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epivotIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003erandom\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003emin\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e max\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ep\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e q\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003epartitionDutchFlag\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e pivotIndex\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e pivotIndex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003equicksortDutchFlag\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e p \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003equicksortDutchFlag\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e low\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e q \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e high\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eUsing Dutch flag partitioning makes for a more efficient quicksort if the array contains many duplicate elements. (And I'm not just saying that because I'm Dutch!)\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e The above implementation of \u003ccode\u003epartitionDutchFlag()\u003c/code\u003e uses a custom \u003ccode\u003eswap()\u003c/code\u003e routine for swapping the contents of two array elements. Unlike Swift's own \u003ccode\u003eswap()\u003c/code\u003e, this doesn't give an error when the two indices refer to the same array element. See \u003ca href=\"/JackLu2012/swift-algorithm-club/blob/master/Quicksort/Quicksort.swift\"\u003eQuicksort.swift\u003c/a\u003e for the code.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSee also\u003c/h2\u003e\u003ca id=\"user-content-see-also\" class=\"anchor\" aria-label=\"Permalink: See also\" href=\"#see-also\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003ca href=\"https://en.wikipedia.org/wiki/Quicksort\" rel=\"nofollow\"\u003eQuicksort on Wikipedia\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by Matthijs Hollemans\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Quicksort","anchor":"quicksort","htmlText":"Quicksort"},{"level":2,"text":"An example","anchor":"an-example","htmlText":"An example"},{"level":2,"text":"Partitioning","anchor":"partitioning","htmlText":"Partitioning"},{"level":2,"text":"Lomuto's partitioning scheme","anchor":"lomutos-partitioning-scheme","htmlText":"Lomuto's partitioning scheme"},{"level":2,"text":"Hoare's partitioning scheme","anchor":"hoares-partitioning-scheme","htmlText":"Hoare's partitioning scheme"},{"level":2,"text":"Picking a good pivot","anchor":"picking-a-good-pivot","htmlText":"Picking a good pivot"},{"level":2,"text":"Dutch national flag partitioning","anchor":"dutch-national-flag-partitioning","htmlText":"Dutch national flag partitioning"},{"level":2,"text":"See also","anchor":"see-also","htmlText":"See also"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2FJackLu2012%2Fswift-algorithm-club%2Ftree%2Fmaster%2FQuicksort"}},"totalCount":5,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Closest Pair","path":"Closest Pair","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Genetic","path":"Genetic","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"Introsort","path":"Introsort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Myers Difference Algorithm","path":"Myers Difference Algorithm","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Points Lines Planes","path":"Points Lines Planes","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Simulated annealing","path":"Simulated annealing","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Sparse Table","path":"Sparse Table","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":"swift-algorithm-club.xcworkspace","path":"swift-algorithm-club.xcworkspace","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":120}},"fileTreeProcessingTime":20.881626,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/JackLu2012/swift-algorithm-club/branches":{"post":"ZW3sSZ2reKJ2pgJaVJFg74y82_zHzZE_CTV-yKEYKqtsNcqdafpFQnP1dn8t7FKyoARSXgBUd9dpSNiL4QP43Q"},"/JackLu2012/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"rWtFrpG3f7cyR9EEjdI0ZV10kU3P_M6M1FpDFkLxH3Abo6aHfF6swrhleckSJ7308Vkq2Qra7AX_v-Yah5DOEw"},"/JackLu2012/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"xwpjgr5Gxh6XEErwUuUNN7C31XybMB3bhGOXgyiaI-JxwoCrU68Vax0y4j3NEISmHJpu6F4WP1KvhjKP7fvygQ"}}},"title":"swift-algorithm-club/Quicksort at master · JackLu2012/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
0