@font-face{font-family:Comfortaa;src:url(/fonts/Comfortaa-Regular.ttf);font-weight:400}@font-face{font-family:Comfortaa;src:url(/fonts/Comfortaa-Bold.ttf);font-weight:700}:root{--primary: #5d9eda;--secondary: #b1d0ee;--background: #282c34;--pane: #21252b;--surface: #31353f;--surface2: #51555f;--text: #d1d1d1;--headline: #ffffff;--hint: #797979;color:var(--text);--default-gap: 16px}a{text-decoration:none;color:var(--secondary)}nav>a{color:var(--text)}body{margin:0;min-height:100vh;display:flex;flex-direction:column}html{margin:0;font-family:system-ui,sans-serif;background:var(--background)}main{flex:1}header{background:var(--pane)}header>div{display:flex;flex-direction:row;align-items:center;justify-content:space-between;gap:2rem;margin:auto;padding:16px;font-family:Comfortaa;font-weight:700;font-size:1rem;@media (min-width: 1200px){width:1200px}}nav{display:flex;flex-direction:row;align-items:center;gap:2rem}#logo{font-size:2rem;color:var(--primary);text-wrap:nowrap}h1,h2,h3,h4{font-family:Comfortaa;font-weight:400;color:var(--headline);padding:0}h1{color:var(--primary);font-size:3rem}h2{font-size:2rem}h3{font-size:1.5rem}h4{font-size:1.25rem}code{font-family:Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace}code:not(pre>code){background-color:#21252b;font-size:.9rem;padding:0 4px;border-radius:4px}.astro-code{padding:16px;max-width:80vw}pre{background-color:#21252b!important}.markdown-alert-title{margin-bottom:8px}footer{color:var(--hint);text-align:center;margin-bottom:16px}
</style></head><body><header><div><ahref="/"id="logo">> _</a><nav><ahref="https://code.evalyte.net"target="_blank">Repositories</a><!--<a href="/devlog">Devlog</a>--><ahref="/notes">Notes</a><!--<a href="/utilities">Utilities</a>--><!--<a href="/services">Services</a>--><ahref="/about">About</a></nav></div></header><maindata-astro-cid-hhdr4bp3><divstyle="display:flex;flex-direction:column;gap:var(--default-gap);justify-content:center;align-items:start"><divstyle="display:flex;flex-direction:column;gap:var(--default-gap);justify-content:center;align-items:start"><h1data-astro-cid-hhdr4bp3>Quick Sort algorithm</h1></div><divstyle="flex:1"><pdata-astro-cid-hhdr4bp3><p>To explain the Quick Sort algorithm, let’s take a simple example:</p>
<p>We have an array of number (integer) in random order, but we want them in ascending order, so we have to sort them, here comes the Quick Sort algorithm.</p>
<p><em>Note: The range of the numbers and the length of the array have no importance for the algorithm itself, but it will have a performance cost.</em></p>
<h2id="algorithm">Algorithm</h2>
<p>Select a number, called “pivot”, chosen arbritrary from the array itself, put all the numbers lower than the pivot before it and all the numbers greater after it, split the current partition into 2 new partitions (the ones before and after the pivot), and repeat the procedure for each partition until there is no partition left (when the array length is 1).</p>
<p>The Quick Sort algorithm steps are:</p>
<ul>
<li>Select a pivot value from the partition and move it at the end of the partition (P, the pivot value).</li>
<li>Remember the start index of the current partition (S, the start index).</li>
<li>for each element (E), if E is lower or equal than P, then swap value E with the value at index S, then increment S.</li>
<li>Use the pivot P to divide the partition into 2 new partitions.</li>
<li>Repeat the algorithm for the 2 newly created partitions until there is no partition left.</li>
<spanclass="line"><spanstyle="color:#B392F0"> Swap</span><spanstyle="color:#E1E4E8">(partition, </span><spanstyle="color:#B392F0">len</span><spanstyle="color:#E1E4E8">(partition) </span><spanstyle="color:#F97583">/</span><spanstyle="color:#79B8FF"> 2</span><spanstyle="color:#E1E4E8">, </span><spanstyle="color:#B392F0">len</span><spanstyle="color:#E1E4E8">(partition) </span><spanstyle="color:#F97583">-</span><spanstyle="color:#79B8FF"> 1</span><spanstyle="color:#E1E4E8">) </span><spanstyle="color:#6A737D">// Select the pivot from the middle (arbitrary) of the partition and swap it with the last element</span></span>
<spanclass="line"><spanstyle="color:#E1E4E8"> pivot </span><spanstyle="color:#F97583">:=</span><spanstyle="color:#E1E4E8"> partition[</span><spanstyle="color:#B392F0">len</span><spanstyle="color:#E1E4E8">(partition) </span><spanstyle="color:#F97583">-</span><spanstyle="color:#79B8FF"> 1</span><spanstyle="color:#E1E4E8">] </span><spanstyle="color:#6A737D">// Since we already swapped the pivot, we get the value directly from the end of the partition</span></span>
<spanclass="line"></span>
<spanclass="line"><spanstyle="color:#F97583"> for</span><spanstyle="color:#E1E4E8"> i </span><spanstyle="color:#F97583">:=</span><spanstyle="color:#E1E4E8"> startIndex; i </span><spanstyle="color:#F97583"><</span><spanstyle="color:#B392F0"> len</span><spanstyle="color:#E1E4E8">(partition); i</span><spanstyle="color:#F97583">++</span><spanstyle="color:#E1E4E8"> {</span></span>
