<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Tim Nelson on Medium]]></title>
        <description><![CDATA[Stories by Tim Nelson on Medium]]></description>
        <link>https://medium.com/@tdnelson?source=rss-9c4f0e75ff0------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*besdDHopld_t4C6O.</url>
            <title>Stories by Tim Nelson on Medium</title>
            <link>https://medium.com/@tdnelson?source=rss-9c4f0e75ff0------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 00:08:05 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@tdnelson/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[JavaScript Algorithms: Merge Sort]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-merge-sort-577953335a42?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/577953335a42</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Mon, 10 Dec 2018 21:03:33 GMT</pubDate>
            <atom:updated>2018-12-13T06:37:37.974Z</atom:updated>
            <content:encoded><![CDATA[<p><em>If you haven’t already done so, I strongly encourage you to read my post on </em><a href="https://medium.com/@tdnelson/javascript-algorithms-quick-sort-526874044bb"><em>Quick Sort</em></a><em> first as this post builds upon the principles discussed therein </em>😊</p><p>Merge Sort is another divide and conquer algorithm which, like Quick Sort, is far more efficient than any of the other methods we’ve discussed so far.</p><p><strong>How does it work?</strong></p><p>Well, the theory behind Merge Sort is that it’s much easier to sort smaller lists than larger lists, so why not divide the list in two? To illustrate this, lets say we have a list…</p><pre>[ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ]</pre><p>In Merge sort you would start out by dividing it into two parts:</p><pre>[ 10,   1,   9,   2,   8 ][  3,   7,   4,   6,   5 ]</pre><p>So now we have two parts. Now we focus on just the left list. What do we do? Well, we divide it into two parts again:</p><pre>[ 10,   1 ][ 9,   2,   8 ]</pre><p>Believe it or not, we just keep on dividing…</p><pre>[ 10 ][ 1 ]<br>           [ 9 ][ 2,   8 ]<br>                [ 2 ][ 8 ]</pre><p>… until everything is in it’s own list. What do we do now? Well, we start merging the lists back together, two by two, and because each list is now sorted, we can make a <em>key assumption</em> when merging two lists:</p><blockquote><em>Key assumption</em>: When provided an item at a particular index in a sorted list, the remaining items in the list <strong>cannot be smaller</strong>. Furthermore, the items before that particular item at that particular index <strong>cannot be larger</strong>.</blockquote><p>What does this mean? Say you have two lists—list1 and list2—and both lists are sorted from smallest to largest. If you compare the first item in list1 to the first item in list2 and find that the first item in list2 is larger than the first item in list1, the <em>key assumption</em> tells us that each of the remaining items in list2 are also larger than the first item in list1. Mind blown 🤯</p><p>Okay, I admit it, the <em>key assumption </em>is not very profound. However, it turns out you can even make this assumption about lists that only contain one item. Everything that comes after the first item in the single-item lists is guaranteed to be larger than (or at least equal to) the first item in the list. This is technically a true statement even though we know a single-item list only has, well, one item so there won’t be anything after the first first item. Nevertheless, in our original example we can merge the first pair of single-item lists using this <em>key assumption</em>:</p><pre>Start comparing... <br>[ <strong>10</strong> ] [ <strong>1</strong> ] <br><strong>1</strong> is SMALLER than <strong>10</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>10</strong>. <br>No need to compare <strong>1</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>1</strong> to tempArray. <br>tempArray: [ <strong>1</strong> ] </pre><pre>No more items to compare... <br>Add the rest of the <strong>left array</strong> to tempArray: <br>tempArray: [ 1, <strong>10</strong> ]</pre><p>And we do the same with the next pair of single-item lists…</p><pre>Start comparing... <br>[ <strong>2</strong> ] [ <strong>8</strong> ] <br><strong>2</strong> is SMALLER than <strong>8</strong>. <br>The <strong>right array</strong> is sorted so nothing larger will be found after <strong>8</strong>. <br>No need to compare <strong>2</strong> to the rest of the items in the <strong>right array</strong>. <br>Add <strong>8</strong> to tempArray. <br>tempArray: [ <strong>2</strong> ] </pre><pre>No more items to compare... <br>Add the rest of the <strong>right array</strong> to tempArray: <br>tempArray: [ 2, <strong>8</strong> ]</pre><p>This is where things start getting more interesting. If you’ve been paying attention, you’ll know that the current state of things looks like this:</p><pre>[ 1, 10 ][ 2, 8 ][ 9 ]</pre><p>Looks good right? We’ve got three sorted lists. Now we need to find a way to add 9 to one of those lists. Which one should we put it in? Well, the algorithm ultimately figures this out and it just so happens that it chooses to combine it like so…</p><pre>Start comparing... <br>[ <strong>9</strong> ] [ <strong>2</strong>, 8 ] <br><strong>2</strong> is SMALLER than <strong>9</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>9</strong>. <br>No need to compare <strong>2</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>2</strong> to tempArray. <br>tempArray: [ <strong>2</strong> ] </pre><pre>Continue comparing...<br>[ <strong>9</strong> ] [ 2, <strong>8</strong> ] <br><strong>8</strong> is SMALLER than <strong>9</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>9</strong>. <br>No need to compare <strong>8</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>8</strong> to tempArray. <br>tempArray: [ 2, <strong>8</strong> ] </pre><pre>No more items to compare... <br>Add the rest of the <strong>left array</strong> to tempArray: <br>tempArray: [ 2, 8, <strong>9</strong> ]</pre><p>So now we’re left with two arrays:</p><pre>[ 1, 10 ][ 2, 8, 9 ]</pre><p>What do we do now? Well, we keep on merging…</p><pre>Start comparing... <br>[ <strong>1</strong>, 10 ] [ <strong>2</strong>, 8, 9 ] <br><strong>1</strong> is SMALLER than <strong>2</strong>. <br>The <strong>right array</strong> is sorted so nothing larger will be found after <strong>2</strong>. <br>No need to compare <strong>1</strong> to the rest of the items in the <strong>right array</strong>. <br>Add <strong>1</strong> to tempArray. <br>tempArray: [ <strong>1</strong> ]</pre><pre>Continue comparing...<br>[ 1, <strong>10</strong> ] [ <strong>2</strong>, 8, 9 ] <br><strong>2</strong> is SMALLER than <strong>10</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>10</strong>. <br>No need to compare <strong>2</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>2</strong> to tempArray. <br>tempArray: [ 1, <strong>2</strong> ]</pre><pre>Continue comparing...<br>[ 1, <strong>10</strong> ] [ 2, <strong>8</strong>, 9 ] <br><strong>8</strong> is SMALLER than <strong>10</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>10</strong>. <br>No need to compare <strong>8</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>8</strong> to tempArray. <br>tempArray: [ 1, 2, <strong>8</strong> ]</pre><pre>Continue comparing...<br>[ 1, <strong>10</strong> ] [ 2, 8, <strong>9</strong> ] <br><strong>9</strong> is SMALLER than <strong>10</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>10</strong>. <br>No need to compare <strong>9</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>9</strong> to tempArray. <br>tempArray: [ 1, 2, 8, <strong>9</strong> ] </pre><pre>No more items to compare... <br>Add the rest of the <strong>left array</strong> to tempArray: <br>tempArray: [ 1, 2, 8, 9, <strong>10</strong> ]</pre><p>And there you have it! The first half of the list is ordered. Okay so now that you’ve seen how we first divided then recombined (merged) the first half of the list, let’s do it with the second half. Rather than showing every step in the process (which I’m sure you’re sick of seeing), I’m just going to skip to the part where we have two sorted lists…</p><p>… so we’re <em>fast-forwarding</em> to this state:</p><pre>[ 1, 2, 8, 9, 10 ][ 3, 4, 5, 6, 7 ]</pre><p>So now all we need to do is <em>merge</em> these two ordered lists (<em>merge</em>, yep, that’s why they call it Merge Sort). How do we do that? Well, we just keep on using the same logic from the <em>key assumption</em>:</p><pre>Start comparing... <br>[ <strong>1</strong>, 2, 8, 9, 10 ] [ <strong>3</strong>, 4, 5, 6, 7 ] <br><strong>1</strong> is SMALLER than <strong>3</strong>. <br>The <strong>right array</strong> is sorted so nothing larger will be found after <strong>3</strong>. <br>No need to compare <strong>1</strong> to the rest of the items in the <strong>right array</strong>. <br>Add <strong>1</strong> to tempArray. <br>tempArray: [ <strong>1</strong> ]</pre><pre>Continue comparing...<br>[ 1, <strong>2</strong>, 8, 9, 10 ] [ <strong>3</strong>, 4, 5, 6, 7 ] <br><strong>2</strong> is SMALLER than <strong>3</strong>. <br>The <strong>right array</strong> is sorted so nothing larger will be found after <strong>3</strong>. <br>No need to compare <strong>2</strong> to the rest of the items in the <strong>right array</strong>. <br>Add <strong>2</strong> to tempArray. <br>tempArray: [ 1, <strong>2</strong> ]</pre><pre>Continue comparing...<br>[ 1, 2, <strong>8</strong>, 9, 10 ] [ <strong>3</strong>, 4, 5, 6, 7 ] <br><strong>3</strong> is SMALLER than <strong>8</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>8</strong>. <br>No need to compare <strong>3</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>3</strong> to tempArray. <br>tempArray: [ 1, 2, <strong>3</strong> ]</pre><pre>Continue comparing...<br>[ 1, 2, <strong>8</strong>, 9, 10 ] [ 3, <strong>4</strong>, 5, 6, 7 ] <br><strong>4</strong> is SMALLER than <strong>8</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>8</strong>. <br>No need to compare <strong>4</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>4</strong> to tempArray. <br>tempArray: [ 1, 2, 3, <strong>4</strong> ]</pre><pre>Continue comparing...<br>[ 1, 2, <strong>8</strong>, 9, 10 ] [ 3, 4, <strong>5</strong>, 6, 7 ] <br><strong>5</strong> is SMALLER than <strong>8</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>8</strong>. <br>No need to compare <strong>5</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>5</strong> to tempArray. <br>tempArray: [ 1, 2, 3, 4, <strong>5</strong> ]</pre><pre>Continue comparing...<br>[ 1, 2, <strong>8</strong>, 9, 10 ] [ 3, 4, 5, <strong>6</strong>, 7 ] <br><strong>6</strong> is SMALLER than <strong>8</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>8</strong>. <br>No need to compare <strong>6</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>6</strong> to tempArray. <br>tempArray: [ 1, 2, 3, 4, 5, <strong>6</strong> ]</pre><pre>Continue comparing...<br>[ 1, 2, <strong>8</strong>, 9, 10 ] [ 3, 4, 5, 6, <strong>7</strong> ] <br><strong>7</strong> is SMALLER than <strong>8</strong> <br>The <strong>left array</strong> is sorted so nothing larger will be found after <strong>8</strong>. <br>No need to compare <strong>7</strong> to the rest of the items in the <strong>left array</strong>. <br>Add <strong>7</strong> to tempArray. <br>tempArray: [ 1, 2, 3, 4, 5, 6, <strong>7</strong> ] </pre><pre>No more items to compare... <br>Add the rest of the <strong>left array</strong> to tempArray: <br>tempArray: [ 1, 2, 3, 4, 5, 6, 7, <strong>8</strong>, <strong>9</strong>, <strong>10</strong> ]</pre><p>And now everything is sorted! Easy-peasy right? The beauty of Merge Sort is each comparison results in a definitive decision. You don’t have to worry about anything that comes before or after the two items you’re comparing. All you need to worry about is which of the two is smaller and add it to tempArray. An added bonus is once you’ve reached the end of either of the lists, you can just add the remaining items from the other list to tempArray because it’s safe to assume they’re all equal to or larger than the last item in tempArray.</p><p><strong>Let’s do it in JavaScript!</strong></p><p>There is one minor disadvantage to using Merge Sort. Unlike Quick Sort, there isn’t really a good way to do <em>in-place</em> sorting. That means you end up creating a whole bunch of new arrays before you can finally return an ordered array. If this were a lower-level programing language like C, that could be a problem, but since this is JavaScript we’re not going to worry about it. Besides, if you <a href="https://jsperf.com/5-sort-algorithms">compare the performance</a> of Bubble Sort, Select Sort, Insertion Sort, Quick Sort, and Merge Sort <em>in JavaScript</em>, ironically Quick Sort and Merge Sort are the two slowest. Insertion Sort is actually the fastest. But that’s beside the point. The point of this blog is to explore CS concepts using JavaScript and since every modern programing language has built in sorting methods which are way faster than anything we can create on our own, there really aren’t many real-world use cases for these sorting algorithms in their current form. However the CS principles they teach us are important and there are plenty of times we do need to create algorithms. My hope is that after exploring these algorithms we’ll be a little better prepared the next time circumstances require us to create a custom algorithm.</p><p>I digress… anyway, let’s get back to talking about implementing Merge Sort in JavaScript.</p><p><em>Step 1</em>: Define the function:</p><pre><strong>const mergeSort = (array) =&gt; {<br>  </strong>// more stuff will go here<strong><br>}</strong></pre><p><em>Step 2</em>: Return if array only contains one item:</p><pre>const mergeSort = (array) =&gt; {<br>  <strong>if (array.length === 1) return array;</strong><br>  // more stuff will go here<br>}</pre><p><em>Step 3</em>: Get the middle-ish index of array:</p><pre>const mergeSort = (array) =&gt; {<br>  if (array.length === 1) return array;<br>  <br>  <strong>const middle = Math.floor(array.length / 2);</strong><br>  // more stuff will go here<br>}</pre><p><em>Step 4</em>: Recursively call mergeSort on the left half of array.</p><pre>const mergeSort = (array) =&gt; {<br>  if (array.length === 1) return array;<br>  <br>  const middle = Math.floor(array.length / 2);<br>  <strong>const leftArr = mergeSort(array.slice(0, middle));</strong><br>  // more stuff will go here<br>}</pre><p><em>Step 5</em>: Recursively call mergeSort on the right half of array.</p><pre>const mergeSort = (array) =&gt; {<br>  if (array.length === 1) return array;<br>  <br>  const middle = Math.floor(array.length / 2);<br>  const leftArr = mergeSort(array.slice(0, middle));<br>  <strong>const rightArr = mergeSort(array.slice(middle));</strong><br>  // more stuff will go here<br>}</pre><p>At this point if you were to run mergeSort([10,1,9,2,8,3,7,4,6,5]), it would appear nothing is happening. However, trust me, things are happening. When the program gets to this line: const leftArr = mergeSort(array.slice(0, middle));, recursion steps in and in and because the only condition for a return statement is array.length === 1, recursion will keep hitting const leftArr = mergeSort(array.slice(0, middle)); and const rightArr = mergeSort(array.slice(middle)); until we’ve divided everything to the point where array.length === 1.</p><p>However, because we aren’t yet doing anything with each of these single-item lists, they get created and left in limbo. How do we get them out of limbo? I’m glad you asked! Keep reading!</p><p><em>Step 6</em>: Call (a yet to be defined function called) merge to merge leftArr and rightArr into a single, sorted array:</p><pre>const mergeSort = (array) =&gt; {<br>  if (array.length === 1) return array;<br>  <br>  const middle = Math.floor(array.length / 2);<br>  const leftArr = mergeSort(array.slice(0, middle));<br>  const rightArr = mergeSort(array.slice(middle));<br>  <br>  <strong>return merge(leftArr, rightArr);</strong><br>}</pre><p>So merge won’t kick in until recursion meets its exit condition (array.length === 1) and at that point we can finally move beyond defining const leftArr and const rightArr in each of the successive recursive instances of mergeSort. Starting at the inner-most recursive instance with our two single-item lists (leftArr and rightArr), we finally are allowed to advance to merge(leftArr, rightArr). The output of merge gets passed to the next outer recursive instance of mergeSort… then all the way up the line of instances until we finally get to the original instance—the first instance of mergeSort which we called with our original array ([10,1,9,2,8,3,7,4,6,5]). (If none of this recursive stuff is making any sense to you, please read my in-depth discussion on the topic <a href="https://medium.com/@tdnelson/javascript-algorithms-factorial-8aad841e883d#83d0">here</a>.)</p><p><em>Step 7</em>: Define merge:</p><pre><strong>const merge = (leftArr, rightArr) =&gt; {<br>  </strong>// more stuff will go here<strong><br>}</strong></pre><p><em>Step 8</em>: Create counters for leftArr and rightArr:</p><pre>const merge = (leftArr, rightArr) =&gt; {<br><strong>  let left = 0; <br>  let right = 0; </strong><br>  // more stuff will go here<br>}</pre><p><em>Step 9</em>: Define a new array where we’ll put everything from leftArr and rightArr as we determine the order in which they get added:</p><pre>const merge = (leftArr, rightArr) =&gt; {<br>  let left = 0; <br>  let right = 0; <br>  <strong>let mergedArr = [];</strong><br>  // more stuff will go here<br>}</pre><p><em>Step 10</em>: Define a while loop and set the exit condition to when we reach the end of either leftArr or rightArr:</p><pre>const merge = (leftArr, rightArr) =&gt; {<br>  let left = 0; <br>  let right = 0; <br>  let mergedArr = [];<br>  <strong>while (left &lt; leftArr.length &amp;&amp; right &lt; rightArr.length) {</strong><br>    // more stuff will go here<br>  <strong>}</strong><br>}</pre><p>So the while loop will continue looping forever as long as left is less than the length of leftArr and right is less than the length of rightArray. However, the presence of the &amp;&amp; operator means that if either of those conditions are no longer true, the loop will exit.</p><p><em>Step 11</em>: Check if leftArr[left] is greater than rightArr[right] and add rightArr[right] to mergeArr if it is:</p><pre>const merge = (leftArr, rightArr) =&gt; {<br>  let left = 0; <br>  let right = 0; <br>  let mergedArr = [];<br>  while (left &lt; leftArr.length &amp;&amp; right &lt; rightArr.length) {<br>    <strong>if (leftArr[left] &gt; rightArr[right]) {<br>      mergedArr.push(rightArr[right]);</strong><br>      // something else will go here<strong><br>    }</strong> // mores stuff will go here<br>  }<br>}</pre><p><em>Step 12</em>: Check if rightArr[right] is greater than or equal to leftArr[left] and add leftArr[left] to mergeArr if it is:</p><pre>const merge = (leftArr, rightArr) =&gt; {<br>  let left = 0; <br>  let right = 0; <br>  let mergedArr = [];<br>  while (left &lt; leftArr.length &amp;&amp; right &lt; rightArr.length) {<br>    if (leftArr[left] &gt; rightArr[right]) {<br>      mergedArr.push(rightArr[right]);<br>      // something else will go here<br>    } <strong>else {<br>      mergedArr.push(leftArr[left]);</strong><br>      // something else will go here<br>    <strong>}</strong><br>  }<br>  // more stuff will go here<br>}</pre><p><em>Step 13</em>: Increment left or right as needed:</p><pre>const merge = (leftArr, rightArr) =&gt; {<br>  let left = 0; <br>  let right = 0; <br>  let mergedArr = [];<br>  while (left &lt; leftArr.length &amp;&amp; right &lt; rightArr.length) {<br>    if (leftArr[left] &gt; rightArr[right]) {<br>      mergedArr.push(rightArr[right]);<br>      <strong>right++;</strong><br>    } else {<br>      mergedArr.push(leftArr[left]);<br>      <strong>left++;</strong><br>    }<br>  }<br>  // more stuff will go here<br>}</pre><p><em>Step 14</em>: Once an exit condition has been met, add whatever remains from leftArr and rightArr to mergedArr and return:</p><pre>const merge = (leftArr, rightArr) =&gt; {<br>  let left = 0; <br>  let right = 0; <br>  let mergedArr = [];<br>  while (left &lt; leftArr.length &amp;&amp; right &lt; rightArr.length) {<br>    if (leftArr[left] &gt; rightArr[right]) {<br>      mergedArr.push(rightArr[right]);<br>      right++;<br>    } else {<br>      mergedArr.push(leftArr[left]);<br>      left++;<br>    }<br>  }<br><strong>  mergedArr.push(...leftArr.slice(left));<br>  mergedArr.push(...rightArr.slice(right));<br>  return mergedArr;</strong><br>}</pre><p>Like I said earlier, once either one of the lists has finished comparing with the other, the while loop should exit. However, this means that one of the lists always has something left over. Since we know whatever is left over is greater than (or equal to) the last item in mergedArr, we can just add it to the end of mergedArr. However, we won’t know which list will have stuff left over—and that’s okay. We just add whatever remains from both lists using the ES6 spread operator (...).</p><p>And that’s it! We’re done!</p><p>Lets run through it one more time with our example list:</p><pre>mergeSort([10,1,9,2,8,3,7,4,6,5])</pre><p>First the list gets divided into two parts…</p><pre>[ 10,   1,   9,   2,   8 ][  3,   7,   4,   6,   5 ]</pre><p>Then it hits the recursive patch and the first half gets divided and divided and divided…</p><pre>[ 10,   1 ][ 9,   2,   8 ]<br>[ 10 ][ 1 ]<br>           [ 9 ][ 2,   8 ]<br>                [ 2 ][ 8 ]</pre><p>Until we’ve got a bunch of single-item lists.</p><p>At this point, recursion stops the first two values get assigned to the first two single-item lists as leftArr and rightArr in the inner-most recursive instance of mergeSort:</p><pre>leftArr: [ 10 ] <br>rightArr: [ 1 ]</pre><p>They’re now free to advance to merge(leftArr, rightArr). merge, well, merges the two lists using the <em>key assumption</em> logic and returns a new sorted array:</p><pre>[ 1, 10 ]</pre><p>This repeats for the rest of the single-item lists, merging them into two-item lists, three-item and finally five-item sorted lists.</p><p>So let’s take a minute to review. We created a whole bunch of successive recursive instances of mergeSort and we know that eventually the innermost instances start hitting the single-item “exit condition”, at which the next recursive instance up is allowed to continued to merge and then return its sorted two-item, three-item and finally five-item list to the outer mergeSort instance. Now, we’re back at the original, outermost mergeSort call—we’re no longer in recursionland. The first half of the list has been sorted and assigned to leftArr. Hooray!</p><p>So what happens now? Yep, you guessed it. We do it all over again until we have an ordered rightArr and the function advances to merge for the last time. Finally, after much splitting, merging and merging the merged with other merges, we’ve arrived at our final merge—the merge to end all merges—and we return the full sorted array. Hip hip hooray array!</p><p><strong>Solution</strong></p><p>Here’s the full solution (with some slight tweaks)!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/86a1eac14e809caf6954816a88bafaf3/href">https://medium.com/media/86a1eac14e809caf6954816a88bafaf3/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=577953335a42" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: Quick Sort]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-quick-sort-526874044bb?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/526874044bb</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Fri, 07 Dec 2018 19:23:12 GMT</pubDate>
            <atom:updated>2018-12-13T06:30:39.951Z</atom:updated>
            <content:encoded><![CDATA[<p><em>If you haven’t already done so, I strongly encourage you to read my post on </em><a href="https://medium.com/@tdnelson/javascript-algorithms-insertion-sort-904366f333e3"><em>Insertion Sort</em></a><em> first as this post builds upon the principles discussed therein </em>😊</p><p>Quick Sort is far more efficient than anything we’ve discussed so far. It’s also a bit more complicated and difficult to explain but I’ll do my best.</p><p><strong>How does it work?</strong></p><p>Well, in order to understand quick sort, you’ll need to understand two main concepts: <em>pivots</em> and <em>partitions</em>. A <em>pivot</em> is a position in the array where we <em>partition</em> the array so that items larger than value at the <em>pivot</em> index are to the right and items smaller are to the left. The order of the items to the left and right of the <em>pivot</em> does not matter. All that matters is that everything smaller than the value at the <em>pivot</em> index is on the left and everything larger than the value at the <em>pivot</em> index is on the right. I use the term <em>partition</em> in two ways in this post: as a <em>noun</em> and as a <em>verb</em>. As a <em>noun</em> to describe a part of the array that contains values larger or smaller than the pivot. As a <em>verb</em> to indicate the action of dividing the array around a pivot.</p><p>It might not be obvious, but if you <em>partition</em> all the smaller items to the left of the <em>pivot</em> and the larger items to the right of the <em>pivot</em>, the <em>pivot</em> will always end up in the correct position—the <em>pivot</em> will be sorted.</p><p>Make sense? No? Yeah, it didn’t make much sense to me at first either. An example is needed.</p><p>Say you have an array…</p><pre>[ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ]</pre><p>… this is how Quick Sort would start out:</p><pre>[ 10, 1, 9, 2, <strong>8</strong>, 3, 7, 4, 6, 5 ] <br>The pivot is <strong>8 </strong>(chosen at random). <br>Swap pivot with the last item (to get it out of the way): <br>[ 10, 1, 9, 2, 5, 3, 7, 4, 6, <strong>8</strong> ] <br><br>Searching left and right for swaps... <br>[ <strong>10</strong>, 1, 9, 2, 5, 3, 7, 4, <strong>6</strong>, <em>8</em> ] <br><strong>10</strong> is LARGER than the pivot. <strong>6</strong> is SMALLER than the pivot. <br><strong>10</strong> and <strong>6</strong> should SWAP. <br>...<br>[ 6, 1, <strong>9</strong>, 2, 5, 3, 7, <strong>4</strong>, 10, <em>8</em> ] <br><strong>9</strong> is LARGER than the pivot. <strong>4</strong> is SMALLER than the pivot. <br><strong>9</strong> and <strong>4</strong> should SWAP. <br>...<br>No more swaps found. <br>End searching... <br>Swap pivot with the last left search position: <br>[ 6, 1, 4, 2, 5, 3, 7, <strong>8</strong>, 10, 9 ]</pre><p>So as you can see, we’re choosing a pivot randomly then swapping it with the last item in the array to get it out of the way. We then start at the beginning and end of the list and move towards the center. Each time we find an item on the left that is larger than the pivot we look for an item on the right the swap it with. When we run out of items that can be swapped, we swap the pivot item at the last left search position. Miraculously, the pivot value is now “sorted”, meaning it’s a the correct index.</p><p>What do we do now? Well, remember when I said there are two concepts, <em>pivot</em> and <em>partition</em>? This is where <em>partition</em> comes in. We repeat the process with the partition to the left of the pivot, that is, all the values that are less than the value at the pivot index:</p><pre>[ <strong>6</strong>, 1, 4, 2, 5, 3, 7 ] <br>The pivot is <strong>6</strong>. <br>Swap pivot with the last item: <br>[ 7, 1, 4, 2, 5, 3, <strong>6</strong> ] <br><br>Searching left and right for swaps...<br>[ <strong>7</strong>, 1, 4, 2, 5, <strong>3,</strong> <em>6</em> ] <br><strong>7</strong> is LARGER than the pivot. <strong>3</strong> is SMALLER than the pivot. <br><strong>7</strong> and <strong>3</strong> should SWAP. <br>...<br>No more swaps found. <br>End searching... <br>Swap pivot with the last left search position:<br>[ 3, 1, 4, 2, 5, <strong>6</strong>, 7 ]</pre><p>Then we continue repeating with the left partitions…</p><pre>[ 3, 1, <strong>4</strong>, 2, 5 ] <br>The pivot is <strong>4</strong>. <br>Swap pivot with the last item: <br>[ 3, 1, 5, 2, <strong>4</strong> ] <br><br>Searching left and right for swaps...<br>[ 3, 1, <strong>5</strong>, <strong>2,</strong> <em>4</em> ] <br><strong>5</strong> is LARGER than the pivot. <strong>2</strong> is SMALLER than the pivot. <br><strong>5</strong> and <strong>2</strong> should SWAP. <br>...<br>No more swaps found. <br>End searching... <br>Swap pivot with the last left search position:<br>[ 3, 1, 2, <strong>4</strong>, 5 ] <br><br>------------------------------<br><br>[ 3, 1, <strong>2</strong> ] <br>The pivot is <strong>2</strong>. <br>(no need to swap it to the end)<br><br>Searching left and right for swaps...<br>[ <strong>3</strong>, <strong>1,</strong> <em>2</em> ] <br><strong>3</strong> is LARGER than the pivot. <strong>1</strong> is SMALLER than the pivot. <br><strong>3</strong> and <strong>1</strong> should SWAP. <br>...<br>No more swaps found. <br>End searching... <br>Swap pivot with the last left search position:<br>[ 1, <strong>2</strong>, 3 ]</pre><p>… until everything to the left of the original pivot (8) has been pivoted and partitioned over and over again until, as a whole, the array looks like this:</p><pre>[ <strong>1, 2, 3, 4, 5, 6, 7, 8,</strong> 10, 9 ]</pre><p>What do we have left to do? Yep, you guessed it. We need to do the same thing on the right side of the original pivot (8).</p><pre>[ 10, <strong>9</strong> ] <br>The pivot is <strong>9</strong>. <br>(no need to swap it to the end)<br><br>Searching left and right for swaps...<br>No swaps found. <br>End searching... <br>Swap pivot with the last left search position:<br>[ <strong>9</strong>, 10 ]</pre><p>And finally we’re left with a sorted array:</p><pre>[ <strong>1, 2, 3, 4, 5, 6, 7, 8,</strong> <strong>9, 10</strong>]</pre><p><strong>How do we choose a pivot?</strong></p><p>Ideally you would want your pivot to result in an evenly partitioned list. However since there is no way of knowing which value will create even partitions without first sorting the list, often people simply choose a pivot at random. Another common strategy is to choose three pivot candidates then take the median of the three. Yet another, is to simply make the last item in the partition the pivot, since the last item is just as likely as any other to create an evenly partitioned list. Choosing the last item is the most common method since it eliminates the need to swap the pivot to the end of the list.</p><p><strong>Let’s do it in JavaScript!</strong></p><p>There are at least two ways to approach this: the <em>in-place</em> method and the <em>new array</em> method. The <em>in-place</em> method sorts the original array <em>in-place</em>. It returns the original array after sorting. The <em>new array</em> method uses the values from the original array but ultimately returns a new array. I’ll discuss both methods but the <em>new array</em> method happens to be much easier to understand so I’ll start with that one.</p><p><strong><em>New array</em> method:</strong></p><p><em>Step 1</em>: define the function.</p><pre>const quickSort = (arr) =&gt; {<br>  // stuff will go here<br>}</pre><p><em>Step 2</em>: Return if the array only contains one item.</p><pre>const quickSort = (arr) =&gt; {<br>  <strong>if (arr.length &lt;= 1) return arr;</strong><br>  // more stuff will go here<br>}</pre><p><em>Step 3</em>: Choose a pivot. In this case, we simply choose the last item in the list.</p><pre>const quickSort = (arr) =&gt; {<br>  if (arr.length &lt;= 1) return arr;<br>  <strong>const p = arr.pop();</strong><br>  // more stuff will go here<br>}</pre><p>Note: by calling .pop() on the array, we’re also removing the last item from that array. You’ll understand why we did that in step 7.</p><p><em>Step 4</em>: Define leftArr and rightArr. This is where we’ll put the partitioned values.</p><pre>const quickSort = (arr) =&gt; {<br>  if (arr.length &lt;= 1) return arr;<br>  const p = arr.pop();<br>  <strong>const leftArr = [];<br>  const rightArr = [];</strong><br>  // more stuff will go here<br>}</pre><p><em>Step 5</em>: Define a for loop</p><pre>const quickSort = (arr) =&gt; {<br>  if (arr.length &lt;= 1) return arr;<br>  const p = arr.pop();<br>  const leftArr = [];<br>  const rightArr = [];<br><strong>  for (const item of arr) {<br><br>  }</strong><br>}</pre><p><em>Step 6</em>: Add the items to the appropriate partition array based on whether they are greater or less than the pivot value.</p><pre>const quickSort = (arr) =&gt; {<br>  if (arr.length &lt;= 1) return arr;<br>  const p = arr.pop();<br>  const leftArr = [];<br>  const rightArr = [];<br>  for (const item of arr) {<br>    <strong>if (item &lt;= p) {<br>      leftArr.push(item);<br>    } else {<br>      rightArr.push(item);<br>    }</strong><br>  }<br>}</pre><p><em>Step 7</em>: Return a new array in which we’ll put the result of calling quickSort recursively on the leftArr and the rightArr with the pivot value (p) sandwiched between the two.</p><pre>const quickSort = (arr) =&gt; {<br>  if (arr.length &lt;= 1) return arr;<br>  const p = arr.pop();<br>  const leftArr = [];<br>  const rightArr = [];<br>  for (const item of arr) {<br>    if (item &lt;= p) {<br>      leftArr.push(item);<br>    } else {<br>      rightArr.push(item);<br>    }<br>  }<br>  <strong>return [...quickSort(leftArr), p, ...quickSort(rightArr)];</strong><br>}</pre><p>I feel like step 7 needs a little more explaining. There are several things going on. First off, we’re using recursion because we’re calling quickSort from within quickSort. If you don’t know what that is, I talk about it in depth <a href="https://medium.com/@tdnelson/javascript-algorithms-factorial-8aad841e883d#83d0">here</a> and <a href="https://medium.com/@tdnelson/javascript-algorithms-no-repeats-please-173c3abb29fc#deac">here</a>. Secondly, we use the spread operator (...) to concat the results of calling quickSort on the left and the right with p, the pivot value, sandwiched between. Why does p get sandwiched? Well, remember earlier when we talked about how partitioning make it so the pivot value ends up sorted at the correct index? That’s exactly what’s happening here. p ends up sandwiched between a bunch of values that are smaller than it and a bunch of values that are larger than it.</p><p><strong><em>In-place</em> method:</strong></p><p>The <em>in-place</em> method is much more common and probably a lot more efficient since it doesn’t involve constructing new arrays for each new partition. However, it’s far less intuitive and requires quite a bit more brain power to understand what all is happening.</p><p><em>Step 1</em>: Define a function for swapping values at indices.</p><pre>const swap = (arr, x, y) =&gt; {<br>  [arr[x], arr[y]] = [arr[y], arr[x]];<br>}</pre><p>Notice how we’re using <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment">destructuring</a> syntax. This is a slick new feature of ES6. You can read about it more <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment">here</a> if you like.</p><p><em>Step 2</em>: Define the quickSort function.</p><pre>const quickSort = (arr, left = 0, right = arr.length - 1) =&gt; {<br>  // stuff will go here<br>  return arr;<br>}</pre><p>Notice there are several default parameters (left = 0, right = arr.length — 1). This is because the first time you call quickSort it’ll be partitioning the entire array. As you’ll see, we later call quickSort recursively and override those default parameters.</p><p><em>Step 3</em>: If left is greater than right, there’s nothing to do so check for this condition before proceeding.</p><pre>const quickSort = (arr, left = 0, right = arr.length - 1) =&gt; {<br><strong>  if (left &lt; right) {<br>    </strong>// stuff will go here<strong><br>  }</strong><br>  return arr;<br>}</pre><p>This also has to do with how we’ll be calling quickSort recursively. Since we’re doing an in-place sort, the left and right index values will get closer and closer together as recursion progresses. Eventually they’ll meet. Obviously, when that happens there’s nothing do so we check for it.</p><p><em>Step 4</em>: call a (yet to be defined) function for partitioning the array.</p><pre>const quickSort = (arr, left = 0, right = arr.length - 1) =&gt; {<br>  if (left &lt; right) {<br>    <strong>const pivotIndex = partition(arr, left, right);<br></strong>    // more stuff will go here<br>  }<br>  return arr;<br>}</pre><p>So the (yet to be defined) partition function will be choosing the pivot index and partitioning the values on the left and the right of the pivot based on whether those values are smaller or larger than the value at the pivot index. It returns the pivotIndex which is the index in which the pivot is located.</p><p><em>Step 5</em>: Call quickSort recursively for the values on the <strong>left</strong> of pivotIndex.</p><pre>const quickSort = (arr, left = 0, right = arr.length - 1) =&gt; {<br>  if (left &lt; right) {<br>    const pivotIndex = partition(arr, left, right);<br>    <strong>quickSort(arr, left, pivotIndex - 1);<br></strong>    // more stuff will go here<strong><br></strong>  }<br>  return arr;<br>}</pre><p><em>Step 6</em>: Call quickSort recursively for the values on the <strong>right</strong> of the pivotIndex.</p><pre>const quickSort = (arr, left = 0, right = arr.length - 1) =&gt; {<br>  if (left &lt; right) {<br>    const pivotIndex = partition(arr, left, right);<br>    quickSort(arr, left, pivotIndex - 1);<br>    <strong>quickSort(arr, pivotIndex + 1, right);</strong><br>  }<br>  return arr;<br>}</pre><p>Notice how we don’t touch pivotIndex when calling quickSort on the partition to the left and the right? Well, that’s because this is no different than the <em>new array</em> method where the pivot (p) ended up sorted in the right place. The partitions to the left and right of the pivotIndex are smaller and larger than the value at pivotIndex but otherwise unsorted so that’s why we need to call quickSort on them recursively again and again until they become sorted. Let’s talk more about how partition works…</p><p><em>Step 7</em>: Define the partition function.</p><pre>const partition = (arr, left, right) =&gt; {<br>  // stuff will go here<br>}</pre><p><em>Step 8</em>: Set pivot to the last item in the partition (right) and decrement right to take pivot out of the search.</p><pre>const partition = (arr, left, right) =&gt; {<br>  <strong>const pivot = right--;</strong><br>  // more stuff will go here<br>}</pre><p>Note how we do right-- instead of --right. That’s because when you put -- before the variable, decrements before performing assignment operation. When you put -- after the variable, it decrements after the assignment operation.</p><p><em>Step 9</em>: Define a while loop which continues until left and right intersect.</p><pre>const partition = (arr, left, right) =&gt; {<br>  const pivot = right--;<br>  <strong>while (left &lt;= right) {</strong><br>    // more stuff will go here<br>  <strong>}</strong><br>}</pre><p><em>Step 10</em>: Add an inner while loop to <strong>increment</strong> left as long as the arr[left] is less than arr[pivot].</p><pre>const partition = (arr, left, right) =&gt; {<br>  const pivot = right--;<br>  while (left &lt;= right) {<br><strong>    while (arr[left] &lt; arr[pivot]) {<br>      left++;<br>    }</strong><br>    // more stuff will go here<br>  }<br>}</pre><p><em>Step 11</em>: Add an inner while loop to <strong>decrement</strong> right as long as the arr[right] is greater than arr[pivot].</p><pre>const partition = (arr, left, right) =&gt; {<br>  const pivot = right--;<br>  while (left &lt;= right) {<br>    while (arr[left] &lt; arr[pivot]) {<br>      left++;<br>    }<br><strong>    while (arr[right] &gt; arr[pivot]) {<br>      right--;<br>    }</strong><br>    // more stuff will go here<br>  }<br>}</pre><p><em>Step 12</em>: Swap values at indices of left and right if matches are found.</p><pre>const partition = (arr, left, right) =&gt; {<br>  const pivot = right--;<br>  while (left &lt;= right) {<br>    while (arr[left] &lt; arr[pivot]) {<br>      left++;<br>    }<br>    while (arr[right] &gt; arr[pivot]) {<br>      right--;<br>    }<br><strong>    if (left &lt;= right) {<br>      swap(arr, left, right);</strong><br>      // more stuff will go here<br><strong>    }</strong><br>  }<br>}</pre><p><em>Step 13</em>: Increment and decrement left and right after the swap has been made.</p><pre>const partition = (arr, left, right) =&gt; {<br>  const pivot = right--;<br>  while (left &lt;= right) {<br>    while (arr[left] &lt; arr[pivot]) {<br>      left++;<br>    }<br>    while (arr[right] &gt; arr[pivot]) {<br>      right--;<br>    }<br>    if (left &lt;= right) {<br>      swap(arr, left, right);<br><strong>      left++;<br>      right--;</strong><br>    }<br>  }<br>  // more stuff will go here<br>}</pre><p><em>Step 14</em>: Swap the pivot for the last known left position since this is the position in which the search no longer could find a match and therefore is the true pivot index point.</p><pre>const partition = (arr, left, right) =&gt; {<br>  const pivot = right--;<br>  while (left &lt;= right) {<br>    while (arr[left] &lt; arr[pivot]) {<br>      left++;<br>    }<br>    while (arr[right] &gt; arr[pivot]) {<br>      right--;<br>    }<br>    if (left &lt;= right) {<br>      swap(arr, left, right);<br>      left++;<br>      right--;<br>    }<br>  }<br>  <strong>swap(arr, left, pivot);</strong><br>  // something else will go here<br>}</pre><p>How do we know pivot will be in the correct position after swapping with left? Well if you think about what’s happening in the while loops you’ll realize that even if no swaps are found, left will get incremented to the point where it eventually lands on pivot and stops. At this point, it won’t matter where right ends up because left will have exceeded right and that’s a condition for the outer while loop to exit. That will also mean everything to the left of pivot is smaller than the value at pivot index which means pivot is in the right place and no swap is needed.</p><p><em>Step 15</em>: Return left because it is the pivot index—the index at which the pivot value is located.</p><pre>const partition = (arr, left, right) =&gt; {<br>  const pivot = right--;<br>  while (left &lt;= right) {<br>    while (arr[left] &lt; arr[pivot]) {<br>      left++;<br>    }<br>    while (arr[right] &gt; arr[pivot]) {<br>      right--;<br>    }<br>    if (left &lt;= right) {<br>      swap(arr, left, right);<br>      left++;<br>      right--;<br>    }<br>  }<br>  swap(arr, left, pivot);<br>  <strong>return left;</strong><br>}</pre><p>And we’re done! Wow! That was a lot.</p><p>Just to be extra thorough another example is needed. Lets say we call quickSort like so:</p><pre>quickSort([ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ])</pre><p>Below is a map of all the swaps. The partition swaps are in <strong>bold </strong>and the pivot is shown in <em>italics</em>. When the pivot gets swapped, it’s shown in <strong><em>bold-italics</em></strong>.</p><pre>[ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ] &lt;- Initial State<br>[ <strong>4</strong>, 1, 9, 2, 8, 3, 7, <strong>10</strong>, 6, <em>5</em> ] <br>[ 4, 1, <strong>3</strong>, 2, 8, <strong>9</strong>, 7, 10, 6, <em>5</em> ] <br>[ 4, 1, 3, 2, <strong><em>5</em></strong>, 9, 7, 10, 6, <strong>8</strong> ] <br>[ <strong>1</strong>, <strong>4</strong>, 3, <em>2</em>                    ] <br>[ 1, <strong><em>2</em></strong>, 3, <strong>4</strong>                    ] <br>[       3, <strong><em>4</em></strong>                    ] <br>[                <strong>6</strong>, 7, 10, <strong>9</strong>, <em>8</em> ] <br>[                6, 7, <strong><em>8</em></strong>, 9, <strong>10</strong> ] <br>[                6, <strong><em>7</em></strong>           ] <br>[                         9, <strong><em>10</em></strong> ]<br>[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] &lt;- End State</pre><p>Notice how little actual swapping needs to occur to reach the state where everything is sorted. The process of partitioning results in a natural sorting because there are exponentially fewer permutations each time you make a partition. Unlike other sorting algorithms where each element needs to be compared to every other element in the list, Quick Sort uses the pivots as comparison proxies. After the first partition, you know nothing on the left is larger than anything on the right so you never need to make a direct comparison between anything on the left and the right. That therein lies the reasons for Quick Sort’s superior efficiency.</p><p><strong>Solution</strong></p><p>So I already shown you the two possible solutions, but here they are again in color!</p><p><em>In-place method:</em></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/58ae95d47653a8f53b8e44195aee1819/href">https://medium.com/media/58ae95d47653a8f53b8e44195aee1819/href</a></iframe><p><em>New array method:</em></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a190aae6f77481965c7d1c644600b4a3/href">https://medium.com/media/a190aae6f77481965c7d1c644600b4a3/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=526874044bb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: Insertion Sort]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-insertion-sort-904366f333e3?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/904366f333e3</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Sat, 01 Dec 2018 04:14:54 GMT</pubDate>
            <atom:updated>2018-12-01T06:08:05.325Z</atom:updated>
            <content:encoded><![CDATA[<p><em>If you haven’t already done so, I strongly encourage you to read </em><a href="https://medium.com/@tdnelson/javascript-algorithms-select-sort-68e9d5bf2aae"><em>my post on Select Sort</em></a><em> first as this post builds upon the principles discussed therein </em>😊</p><p>Insertion Sort is different from Bubble Sort and Select Sort in that there is no swapping. Instead, items are shifted around until a spot can be found to <em>insert</em> another item.</p><p>Here’s how it works. Say you have a list…</p><pre>[ 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 ]</pre><p>… and you want to sort if from 1 to 10. Insertion Sort assumes the beginning part of the list is sorted then finds a place in the beginning part to insert another item. Each time it adds an item, the beginning/sorted part of the list grows larger until the entire list is sorted. So using the above list, at the start of the process we would assume the sorted part of the list consist of 10 and an empty slot ([ 10, _ ]). The empty slot is because 1 was set aside while we try to find a spot to put it. The process for finding a spot looks like this:</p><pre>SEARCHING FOR A SPOT TO INSERT <strong>1</strong>...<br>[ <strong>10</strong>, _ ] <br><strong>1</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ _, 10 ] <br>No remaining items to compare with.<br>---------<br><strong>Insert 1 in open spot.</strong><br>SORTED:<br>[ <strong>1</strong>, 10 ] <br>UNSORTED:<br>[ 9, 2, 8, 3, 7, 4, 6, 5 ] </pre><p>Pretty simple right? If you look under UNSORTED, you’ll notice 9 is next up to be sorted. How do we do that? Just like this:</p><pre>SEARCHING FOR A SPOT TO INSERT <strong>9</strong>...<br>[ 1, <strong>10</strong>, _ ] <br><strong>9</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ <strong>1</strong>, _, 10 ] <br><strong>9</strong> is LARGER than <strong>1</strong>.<br>Keep <strong>1</strong> at current position.<br>---------<br><strong>Insert 9 in open spot.</strong><br>SORTED:<br>[ 1, <strong>9</strong>, 10 ] <br>UNSORTED:<br>[ 2, 8, 3, 7, 4, 6, 5 ] </pre><p>Rinse and repeat a whole bunch of more times…</p><pre>SEARCHING FOR A SPOT TO INSERT <strong>2</strong>...<br>[ 1, 9, <strong>10</strong>, _ ] <br><strong>2</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ 1, <strong>9</strong>, _, 10 ] <br><strong>2</strong> is smaller than <strong>9</strong>.<br>Shift <strong>9</strong> to the RIGHT<br>---------<br>[ <strong>1</strong>, _, 9, 10 ] <br><strong>2</strong> is LARGER than <strong>1</strong>.<br>Keep <strong>1</strong> at current position.<br>---------<br><strong>Insert 2 in open spot.</strong><br>SORTED:<br>[ 1, <strong>2</strong>, 9, 10 ] <br>UNSORTED:<br>[ 8, 3, 7, 4, 6, 5 ] </pre><pre>-------------------------------------------</pre><pre>SEARCHING FOR A SPOT TO INSERT <strong>8</strong>...<br>[ 1, 2, 9, <strong>10</strong>, _ ] <br><strong>8</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ 1, 2, <strong>9</strong>, _, 10 ] <br><strong>8</strong> is smaller than <strong>9</strong>.<br>Shift <strong>9</strong> to the RIGHT<br>---------<br>[ 1, <strong>2</strong>, _, 9, 10 ] <br><strong>8</strong> is LARGER than <strong>2</strong>.<br>Keep <strong>2</strong> at current position.<br>---------<br><strong>Insert 8 in open spot.</strong><br>SORTED:<br>[ 1, 2, <strong>8</strong>, 9, 10 ] <br>UNSORTED:<br>[ 3, 7, 4, 6, 5 ] </pre><pre>-------------------------------------------</pre><pre>SEARCHING FOR A SPOT TO INSERT <strong>3</strong>...<br>[ 1, 2, 8, 9, <strong>10</strong>, _ ] <br><strong>3</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ 1, 2, 8, <strong>9</strong>, _, 10 ] <br><strong>3</strong> is smaller than <strong>9</strong>.<br>Shift <strong>9</strong> to the RIGHT<br>---------<br>[ 1, 2, <strong>8</strong>, _, 9, 10 ] <br><strong>3</strong> is smaller than <strong>8</strong>.<br>Shift <strong>8</strong> to the RIGHT<br>---------<br>[ 1, <strong>2</strong>, _, 8, 9, 10 ] <br><strong>3</strong> is LARGER than <strong>2</strong>.<br>Keep <strong>2</strong> at current position.<br>---------<br><strong>Insert 3 in open spot.</strong><br>SORTED:<br>[ 1, 2, <strong>3</strong>, 8, 9, 10 ] <br>UNSORTED:<br>[ 7, 4, 6, 5 ] </pre><pre>-------------------------------------------</pre><pre>SEARCHING FOR A SPOT TO INSERT <strong>7</strong>...<br>[ 1, 2, 3, 8, 9, <strong>10</strong>, _ ] <br><strong>7</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 8, <strong>9</strong>, _, 10 ] <br><strong>7</strong> is smaller than <strong>9</strong>.<br>Shift <strong>9</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, <strong>8</strong>, _, 9, 10 ] <br><strong>7</strong> is smaller than <strong>8</strong>.<br>Shift <strong>8</strong> to the RIGHT<br>---------<br>[ 1, 2, <strong>3</strong>, _, 8, 9, 10 ] <br><strong>7</strong> is LARGER than <strong>3</strong>.<br>Keep <strong>3</strong> at current position.<br>---------<br><strong>Insert 7 in open spot.</strong><br>SORTED:<br>[ 1, 2, 3, <strong>7</strong>, 8, 9, 10 ] <br>UNSORTED:<br>[ 4, 6, 5 ] </pre><pre>-------------------------------------------</pre><pre>SEARCHING FOR A SPOT TO INSERT <strong>4</strong>...<br>[ 1, 2, 3, 7, 8, 9, <strong>10</strong>, _ ] <br><strong>4</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 7, 8, <strong>9</strong>, _, 10 ] <br><strong>4</strong> is smaller than <strong>9</strong>.<br>Shift <strong>9</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 7, <strong>8</strong>, _, 9, 10 ] <br><strong>4</strong> is smaller than <strong>8</strong>.<br>Shift <strong>8</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, <strong>7</strong>, _, 8, 9, 10 ] <br><strong>4</strong> is smaller than <strong>7</strong>.<br>Shift <strong>7</strong> to the RIGHT<br>---------<br>[ 1, 2, <strong>3</strong>, _, 7, 8, 9, 10 ] <br><strong>4</strong> is LARGER than <strong>3</strong>.<br>Keep <strong>3</strong> at current position.<br>---------<br><strong>Insert 4 in open spot.</strong><br>SORTED:<br>[ 1, 2, 3, <strong>4</strong>, 7, 8, 9, 10 ] <br>UNSORTED:<br>[ 6, 5 ] </pre><pre>-------------------------------------------</pre><pre>SEARCHING FOR A SPOT TO INSERT <strong>6</strong>...<br>[ 1, 2, 3, 4, 7, 8, 9, <strong>10</strong>, _ ] <br><strong>6</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 4, 7, 8, <strong>9</strong>, _, 10 ] <br><strong>6</strong> is smaller than <strong>9</strong>.<br>Shift <strong>9</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 4, 7, <strong>8</strong>, _, 9, 10 ] <br><strong>6</strong> is smaller than <strong>8</strong>.<br>Shift <strong>8</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 4, <strong>7</strong>, _, 8, 9, 10 ] <br><strong>6</strong> is smaller than <strong>7</strong>.<br>Shift <strong>7</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, <strong>4</strong>, _, 7, 8, 9, 10 ] <br><strong>6</strong> is LARGER than <strong>4</strong>.<br>Keep <strong>4</strong> at current position.<br>---------<br><strong>Insert 6 in open spot.</strong><br>SORTED:<br>[ 1, 2, 3, 4, <strong>6</strong>, 7, 8, 9, 10 ] <br>UNSORTED:<br>[ 5 ] </pre><pre>-------------------------------------------</pre><pre>SEARCHING FOR A SPOT TO INSERT <strong>5</strong>...<br>[ 1, 2, 3, 4, 6, 7, 8, 9, <strong>10</strong>, _ ] <br><strong>5</strong> is smaller than <strong>10</strong>.<br>Shift <strong>10</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 4, 6, 7, 8, <strong>9</strong>, _, 10 ] <br><strong>5</strong> is smaller than <strong>9</strong>.<br>Shift <strong>9</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 4, 6, 7, <strong>8</strong>, _, 9, 10 ] <br><strong>5</strong> is smaller than <strong>8</strong>.<br>Shift <strong>8</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 4, 6, <strong>7</strong>, _, 8, 9, 10 ] <br><strong>5</strong> is smaller than <strong>7</strong>.<br>Shift <strong>7</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, 4, <strong>6</strong>, _, 7, 8, 9, 10 ] <br><strong>5</strong> is smaller than <strong>6</strong>.<br>Shift <strong>6</strong> to the RIGHT<br>---------<br>[ 1, 2, 3, <strong>4</strong>, _, 6, 7, 8, 9, 10 ] <br><strong>5</strong> is LARGER than <strong>4</strong>.<br>Keep <strong>4</strong> at current position.<br>---------<br><strong>Insert 5 in open spot.</strong><br>SORTED:<br>[ 1, 2, 3, 4, <strong>5</strong>, 6, 7, 8, 9, 10 ] <br>UNSORTED:<br>[]</pre><p>And it’s sorted!</p><p><strong>Let’s do it in JavaScript!</strong></p><p>As with Bubble Sort and Select Sort, Insertion Sort uses two nested for loops. The main difference is the inner for loop operates in reverse and only concerns itself with shifting items in the sorted part of the loop until a spot is found to put the item in question. Let’s write the function in pieces so it’s we can break it down as we go:</p><p><em>Step 1:</em> Define the function:</p><pre>const insertionSort = (array) =&gt; {<br>  // stuff will go here<br>}</pre><p><em>Step 2:</em> Add the outer loop:</p><pre>const insertionSort = (array) =&gt; {<br><strong>  for (let i = 1; i &lt; array.length; i++) {<br>    const curItem = array[i];<br>    // more stuff will go here<br>  }</strong><br>}</pre><p>Have iteration start at 1 (let i = 1). Set curItem to the item you want to insert in the ordered part of the list.</p><p><em>Step 3:</em> Define the inner for loop (for (var x = i — 1; x &gt;= 0 &amp;&amp; array[x] &gt; curItem; x—- )):</p><pre>const insertionSort = (array) =&gt; {<br>  for (let i = 1; i &lt; array.length; i++) {<br>    const curItem = array[i];<br><strong>    for (var x = i - 1; x &gt;= 0 &amp;&amp; array[x] &gt; curItem; x--) {<br>      // even more stuff will go here<br>    }</strong><br>  }<br>}</pre><p>Let’s take a look at what’s going on here.</p><ul><li>var x = i — 1; We initialize x at i minus one (the sorted portion of the list). Also notice we use var instead of let. More on that latter.</li><li>x &gt;= 0 &amp;&amp; array[x] &gt; curItem; The condition for exiting the loop is somewhat complex. x &gt;= 0: if x is equal to or less than zero, we exit. array[x] &gt; curItem: if array[x] is greater than curItem (the item we’re trying to find a place to insert), we exit.</li><li>x—- At the end of each loop, we decrement x. So this means we’ll be moving backwards.</li></ul><p>Taken as a whole you can read this like this:</p><blockquote>Start at the end of the sorted portion of the list and iterate backwards until we get to the beginning of the list or encounter a value which is higher than the item we’re trying to find a place to insert.</blockquote><p><em>Step 4:</em> Shift the item at index x one place to the right:</p><pre>const insertionSort = (array) =&gt; {<br>  for (let i = 1; i &lt; array.length; i++) {<br>    const curItem = array[i];<br>    for (var x = i - 1; x &gt;= 0 &amp;&amp; array[x] &gt; curItem; x--) {<br>      <strong>array[x + 1] = array[x];</strong><br>    }<br>    // we&#39;ll do something here next<br>  }<br>}</pre><p>We can be sure it’s safe to shift the the item because we know as long as we’re inside the inner for loop we’re meeting the condition that curItem is smaller than the item currently being iterated (the item at index x). Why are we shifting larger items to the right? Well, if you remember from the example, we’re trying to find a spot to put curItem and <em>shifting </em>is the method we use to make space for that item.</p><p>Step 5: Insert curItem in the correct spot:</p><pre>const insertionSort = (array) =&gt; {<br>  for (let i = 1; i &lt; array.length; i++) {<br>    const curItem = array[i];<br>    for (var x = i - 1; x &gt;= 0 &amp;&amp; array[x] &gt; curItem; x--) {<br>      array[x + 1] = array[x];<br>    }<br>    <strong>array[x + 1] = curItem;</strong><br>  }<br>  <strong>return array;</strong><br>}</pre><p>Since the inner for loop decrements at the end of each iteration then checks for an exit condition at the beginning of each loop, we know that array[x] either doesn’t exist (because array[x + 1] is the first item in the array) or is smaller than curItem and, therefore, array[x + 1] is the “empty” spot — the spot where the item to the left is less than curItem and the item to the right is greater than curItem. Sound like the place we should put curItem, right?</p><p><em>One more thing of note</em>: Remember when I told you to notice we used <strong>var</strong> x = i — 1 instead of <strong>let</strong> x = i — 1? Well, the reason for doing this has to do with a key difference between var and let. When we use var, we can define it pretty much anywhere inside the function (unless it’s in a closure or a nested function) and access that value anywhere else within the function. This is called <em>function scope</em>. With let however, things work differently. Variables defined using let only have scope within whichever code block they are define. This is called <em>block scope</em>. If we were to use let instead of var, we wouldn’t have access to x outside of the inner for loop, and that is why we used var instead. There a not a lot of reasons to use var anymore, but this is one of the few and it serves as a good opportunity to learn more about JavaScript scope.</p><p><strong>Solution</strong></p><p>So I already gave the solution, but here it is again in color (and with parameter validation)!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e88af9a648702e0c8888e7f9dd570440/href">https://medium.com/media/e88af9a648702e0c8888e7f9dd570440/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=904366f333e3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: Select Sort]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-select-sort-68e9d5bf2aae?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/68e9d5bf2aae</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Wed, 28 Nov 2018 00:17:24 GMT</pubDate>
            <atom:updated>2018-11-28T20:46:37.497Z</atom:updated>
            <content:encoded><![CDATA[<p><em>If you haven’t already done so, I strongly encourage you to read </em><a href="https://medium.com/@tdnelson/javascript-algorithms-bubble-sort-401140ad111c"><em>my post on Bubble Sor</em></a><em>t first as this post builds upon the principles discussed therein </em>😊</p><p>Select Sort is similar to Bubble Sort except instead of swapping each time a change is found, it first determines which element is best suited to swap. As a result, the maximum times a swap would ever be needed is only whatever the length of the array is.</p><p><strong>How does it work?</strong></p><p>I’m glad you asked. Let me tell you! Say you have a list…</p><pre>[10,9,8,7,6,5,4,3,2,1]</pre><p>… and you want to sort it so it starts with 1 and ends with 10. With Select Sort you would start at the beginning of the list and compare the first item against all the other items in the list. Each time an item which is less than the first item is found, we remember that item and continue comparing the rest of list against it instead of the first item. So for example, using the above array, the steps needed to arrive at the first swap would look like this:</p><pre>10 =&gt; <strong>9,</strong>8,7,6,5,4,3,2,1<br>10 is greater than 9<br>9 =&gt; 9,<strong>8</strong>,7,6,5,4,3,2,1<br>9 is greater than 8<br>8 =&gt; 9,8,<strong>7</strong>,6,5,4,3,2,1<br>8 is greater than 7<br>7 =&gt; 9,8,7,<strong>6</strong>,5,4,3,2,1<br>7 is greater than 6<br>6 =&gt; 9,8,7,6,<strong>5</strong>,4,3,2,1<br>6 is greater than 5<br>5 =&gt; 9,8,7,6,5,<strong>4</strong>,3,2,1<br>5 is greater than 4<br>4 =&gt; 9,8,7,6,5,4,<strong>3</strong>,2,1<br>4 is greater than 3<br>3 =&gt; 9,8,7,6,5,4,3,<strong>2</strong>,1<br>3 is greater than 2<br>2 =&gt; 9,8,7,6,5,4,3,2,<strong>1</strong><br>2 is greater than 1</pre><pre>Should swap <strong>10</strong> and<strong> 1</strong></pre><pre><strong>EXECUTE SWAP:</strong><br>[ <strong>1</strong>, 9, 8, 7, 6, 5, 4, 3, 2, <strong>10</strong> ]</pre><p>Got it? Good. Now we start over again. Except this time because we know for sure that the first item is the smallest item in the list, instead of starting with the first item, we start with the second item:</p><pre>9 =&gt; <strong>8</strong>,7,6,5,4,3,2,10<br>9 is greater than 8<br>8 =&gt; 8,<strong>7</strong>,6,5,4,3,2,10<br>8 is greater than 7<br>7 =&gt; 8,7,<strong>6</strong>,5,4,3,2,10<br>7 is greater than 6<br>6 =&gt; 8,7,6,<strong>5</strong>,4,3,2,10<br>6 is greater than 5<br>5 =&gt; 8,7,6,5,<strong>4</strong>,3,2,10<br>5 is greater than 4<br>4 =&gt; 8,7,6,5,4,<strong>3</strong>,2,10<br>4 is greater than 3<br>3 =&gt; 8,7,6,5,4,3,<strong>2</strong>,10<br>3 is greater than 2<br>2 =&gt; 8,7,6,5,4,3,2,<strong>10</strong><br><br>Should swap <strong>9</strong> and <strong>2</strong><br><br><strong>EXECUTE SWAP:</strong><br>[ 1, <strong>2</strong>, 8, 7, 6, 5, 4, 3, <strong>9</strong>, 10 ]</pre><p>So the first two items in the list (1,2)are now sorted. How do we sort the rest? You guessed it, increment to the next item and compare it against the rest of the list, then rinse and repeat until you ain’t got nothing left to compare:</p><pre>8 =&gt; <strong>7</strong>,6,5,4,3,9,10<br>8 is greater than 7<br>7 =&gt; 7,<strong>6</strong>,5,4,3,9,10<br>7 is greater than 6<br>6 =&gt; 7,6,<strong>5</strong>,4,3,9,10<br>6 is greater than 5<br>5 =&gt; 7,6,5,<strong>4</strong>,3,9,10<br>5 is greater than 4<br>4 =&gt; 7,6,5,4,<strong>3</strong>,9,10<br>4 is greater than 3<br>3 =&gt; 7,6,5,4,3,<strong>9</strong>,10<br>3 =&gt; 7,6,5,4,3,9,<strong>10</strong><br><br>Should swap <strong>8</strong> and <strong>3</strong><br><br><strong>EXECUTE SWAP:</strong><br>[ 1, 2, <strong>3</strong>, 7, 6, 5, 4, <strong>8</strong>, 9, 10 ] </pre><pre>-------------------------------------</pre><pre>7 =&gt; <strong>6</strong>,5,4,8,9,10<br>7 is greater than 6<br>6 =&gt; 6,<strong>5</strong>,4,8,9,10<br>6 is greater than 5<br>5 =&gt; 6,5,<strong>4</strong>,8,9,10<br>5 is greater than 4<br>4 =&gt; 6,5,4,<strong>8</strong>,9,10<br>4 =&gt; 6,5,4,8,<strong>9</strong>,10<br>4 =&gt; 6,5,4,8,9,<strong>10</strong><br><br>Should swap <strong>7</strong> and <strong>4</strong><br><br><strong>EXECUTE SWAP:</strong><br>[ 1, 2, 3, <strong>4</strong>, 6, 5, <strong>7</strong>, 8, 9, 10 ] </pre><pre>-------------------------------------</pre><pre>6 =&gt; <strong>5</strong>,7,8,9,10<br>6 is greater than 5<br>5 =&gt; 5,<strong>7</strong>,8,9,10<br>5 =&gt; 5,7,<strong>8</strong>,9,10<br>5 =&gt; 5,7,8,<strong>9</strong>,10<br>5 =&gt; 5,7,8,9,<strong>10</strong><br><br>Should swap <strong>6</strong> and <strong>5</strong><br><br><strong>EXECUTE SWAP:</strong><br>[ 1, 2, 3, 4, <strong>5</strong>, <strong>6</strong>, 7, 8, 9, 10 ]</pre><pre>-------------------------------------<br><br>6 =&gt; <strong>7</strong>,8,9,10<br>6 =&gt; 7,<strong>8</strong>,9,10<br>6 =&gt; 7,8,<strong>9</strong>,10<br>6 =&gt; 7,8,9,<strong>10</strong><br><br><strong>NO SWAP FOUND</strong></pre><pre>-------------------------------------<br><br>7 =&gt; <strong>8</strong>,9,10<br>7 =&gt; 8,<strong>9</strong>,10<br>7 =&gt; 8,9,<strong>10</strong><br><br><strong>NO SWAP FOUND</strong></pre><pre>-------------------------------------<br><br>8 =&gt; <strong>9</strong>,10<br>8 =&gt; 9,<strong>10</strong><br><br><strong>NO SWAP FOUND</strong></pre><pre>-------------------------------------<br><br>9 =&gt; <strong>10</strong><br><br><strong>NO SWAP FOUND</strong></pre><p>Hopefully that make sense. Notice that halfway through the sort process (when 5 and 6 swap), the rest of the list has already sorted itself. You might be tempted to think this is something that always happens in Select Sort. Sadly you would be wrong ☹️. Just because a swap isn’t found at any point, doesn’t mean there won’t be a swap found at a later point. For example say you want to sort this list:</p><pre>[7,10,9,8]</pre><p>The first time you iterate through it, the following will happen:</p><pre>7 =&gt; <strong>10</strong>,9,8<br>7 =&gt; 10,<strong>9</strong>,8<br>7 =&gt; 10,9,<strong>8</strong>,<br><br><strong>NO SWAP FOUND</strong></pre><p>This doesn’t mean the rest of the list is ordered. It’s not. All it means is that 7 is in the right place. 7 doesn’t need to move.</p><p>To illustrate the point, let’s advance to the next item in the list (10):</p><pre>10 =&gt; <strong>9</strong>,8<br>10 is greater than 9<br>9 =&gt; 9,<strong>8</strong><br>9 is greater than 8<br><br>Should swap <strong>10</strong> and <strong>8</strong><br><br><strong>EXECUTE SWAP:</strong><br>[ 7, <strong>8</strong>, 9, <strong>10</strong> ]</pre><p>This is different from <a href="https://medium.com/@tdnelson/javascript-algorithms-bubble-sort-401140ad111c">Bubble Sort</a>. In Bubble Sort if you go through one iteration without needing to execute a swap, you know that the list is sorted because each iteration is actively looking to see if the list is ordered. Select Sort is different. Each iteration is only looking to see if the element in the current position should swap with another element. In other words, each iteration only concerns itself with whether the current element is the smallest possible element for that particular position in the list.</p><p><strong>Let’s do it in JavaScript!</strong></p><p>To make things simple, I’m going to start where we left off when <a href="https://medium.com/@tdnelson/javascript-algorithms-bubble-sort-401140ad111c">we talked about Bubble Sort</a>. That way you can see the similarities and differences between the two methods.</p><p>Here is Bubble Sort:</p><pre>const bubbleSort = (array) =&gt; {<br>  for (let i = 0; i &lt; array.length; i++) {<br>    for (let x = 0; x &lt; array.length - 1 - i; x++) {<br>      if (array[x] &gt; array[x + 1]) {<br>        [array[x], array[x + 1]] = [array[x + 1], array[x]];<br>      }<br>    }<br>  }<br>  return array;<br>}</pre><p>Ta-da! Okay so lets convert this to Select Sort.</p><pre>const <strong>selectionSort</strong> = (array) =&gt; {<br>  for (let i = 0; i &lt; array.length; i++) {<br>    <strong>let min = i;</strong><br>    for (let x = <strong>i + 1</strong>; x &lt; array.length<strong>;</strong> x++) {<br>      if (array[<strong>min</strong>] &gt; array[<strong>x</strong>]) <strong>min = x;</strong><br>    }<br>    <strong>if (i !== min) [array[i], array[min]] = [array[min], array[i]];</strong><br>  }<br>  return array;<br>}</pre><p>Ta-da! So what changed? Well, the two methods actually have more similarities than they do differences.</p><ul><li>Both use nested for loops.</li><li>Both concern themselves with only the part of the list which has not yet been ordered.</li></ul><p>And the differences:</p><ul><li>Bubble Sort makes swaps within the inner for loop each time it encounters disorder. The inner for loop’s job in Select Sort is to determine which element is best suited for whatever particular index the outer for loop gives it. The inner for loop makes no swaps. It only determines which element is best suited to be swapped.</li><li>Bubble Sort can determine whether order has been achieved at any point after a termination of the inner for loop. Select Sort cannot.</li></ul><p><strong>So what’s going on here?</strong></p><p>Taking the function step by step:</p><ol><li>Outer for loop sets i to 0.</li><li>min gets set to i.</li><li>Inner for loop starts at i + 1.</li><li>It looks to see if the element at index min is greater than the element at index x. That is, if the first element in the array (or whatever min happens to be) is greater than the second element in the array (or whatever x happens to be).</li><li>If it is, the value from x get passed into min.</li><li>The inner loop iterates again and x increments to the next index.</li><li>Step 4, 5 and 6 repeat until all the indices have been looked at and min has been set to the index of the smallest possible value. At this point, the inner for loop terminates and we return to the outer for loop.</li><li>Next we check to see if a swap is even necessary (if (i !== min)). If it is, we swap the item at index i with a smaller item at index min.</li><li>The outer for loop iterates and i increments to the next index.</li><li>Steps 1 through 9 repeat until the outer for loop terminates.</li><li>Return the sorted list.</li></ol><p><em>… and that’s how it’s done!</em></p><p><strong>Solution</strong></p><p>So I already gave the solution, but here it is again in color (and with parameter validation)!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1fcec9a7356af4e1b1c57703f7911fb4/href">https://medium.com/media/1fcec9a7356af4e1b1c57703f7911fb4/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=68e9d5bf2aae" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: Bubble Sort]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-bubble-sort-401140ad111c?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/401140ad111c</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Mon, 26 Nov 2018 22:28:28 GMT</pubDate>
            <atom:updated>2018-12-10T03:50:40.271Z</atom:updated>
            <content:encoded><![CDATA[<p>Bubble sort is often one of the first algorithms you learn when starting out. It’s a simple (but inefficient) way to sort a list of numbers, characters or strings and it could also be adapted to sort other types too.</p><p>Here’s how it works. Say you have a list…</p><pre>[10,9,8,7,6,5,4,3,2,1]</pre><p>… and you want to sort it so it starts with 1 and ends with 10. With bubble sort you start at the beginning and compare the element at index 0 with the element directly to the right (index 1):</p><pre>10 is greater than 9 so 10 and 9 should swap</pre><p>So after the first swap, the list looks like:</p><pre>[9,10,8,7,6,5,4,3,2,1]</pre><p>That’s progress! Okay lets do it with the element at index 1.</p><pre>10 is greater than 8 so 10 and 8 should swap</pre><p>and we get:</p><pre>[9,8,10,7,6,5,4,3,2,1]</pre><p>Rinse and repeat 5 more times…</p><pre>[9,8,7,6,10,5,4,3,2,1]<br>[9,8,7,6,5,10,4,3,2,1]<br>[9,8,7,6,5,4,10,3,2,1]<br>[9,8,7,6,5,4,3,10,2,1]<br>[9,8,7,6,5,4,3,2,10,1]<br>[9,8,7,6,5,4,3,2,1,10]</pre><p>And 10 is finally sorted to the end of the list!</p><p>What happens now? Well, we start all over again. Yeah, pretty tedious, I know:</p><pre>9 is greater than 8 so 9 and 8 should swap</pre><p>Rinse and repeat 35 more times…</p><pre>[8,9,7,6,5,4,3,2,1,10]<br>[8,7,9,6,5,4,3,2,1,10]<br>[8,7,6,9,5,4,3,2,1,10]<br>[8,7,6,5,9,4,3,2,1,10]<br>[8,7,6,5,4,9,3,2,1,10]<br>[8,7,6,5,4,3,9,2,1,10]<br>[8,7,6,5,4,3,2,9,1,10]<br>[8,7,6,5,4,3,2,1,9,10]<br>[7,8,6,5,4,3,2,1,9,10]<br>[7,6,8,5,4,3,2,1,9,10]<br>[7,6,5,8,4,3,2,1,9,10]<br>[7,6,5,4,8,3,2,1,9,10]<br>[7,6,5,4,3,8,2,1,9,10]<br>[7,6,5,4,3,2,8,1,9,10]<br>[7,6,5,4,3,2,1,8,9,10]<br>[6,7,5,4,3,2,1,8,9,10]<br>[6,5,7,4,3,2,1,8,9,10]<br>[6,5,4,7,3,2,1,8,9,10]<br>[6,5,4,3,7,2,1,8,9,10]<br>[6,5,4,3,2,7,1,8,9,10]<br>[6,5,4,3,2,1,7,8,9,10]<br>[5,6,4,3,2,1,7,8,9,10]<br>[5,4,6,3,2,1,7,8,9,10]<br>[5,4,3,6,2,1,7,8,9,10]<br>[5,4,3,2,6,1,7,8,9,10]<br>[5,4,3,2,1,6,7,8,9,10]<br>[4,5,3,2,1,6,7,8,9,10]<br>[4,3,5,2,1,6,7,8,9,10]<br>[4,3,2,5,1,6,7,8,9,10]<br>[4,3,2,1,5,6,7,8,9,10]<br>[3,4,2,1,5,6,7,8,9,10]<br>[3,2,4,1,5,6,7,8,9,10]<br>[3,2,1,4,5,6,7,8,9,10]<br>[2,3,1,4,5,6,7,8,9,10]<br>[2,1,3,4,5,6,7,8,9,10]</pre><p>until finally everything is ordered like so:</p><pre>[1,2,3,4,5,6,7,8,9,10]</pre><p>And we’re done!</p><p><strong>Let’s do it in JavaScript!</strong></p><p>There are several bubble sort versions floating around out there but this is probably the most common one.</p><p><em>Step 1</em>: Define the function.</p><pre><strong>const bubbleSort = (array) =&gt; {<br>  // stuff will go in here<br>  return array;<br>}</strong></pre><p><em>Step 2</em>: Create a for loop to iterate through each item in the array:</p><pre>const bubbleSort = (array) =&gt; {<br><strong>  for (let i = 0; i &lt; array.length; i++) {<br>    // more stuff will go in here  <br>  }</strong><br>  return array;<br>}</pre><p><em>Step 3</em>: Add a nested for loop so we can compare each item against other items in the array:</p><pre>const bubbleSort = (array) =&gt; {<br>  for (let i = 0; i &lt; array.length; i++) {<strong><br>    for (let x = 0; x &lt; array.length - 1 - i; x++) {<br>      // even more stuff will go in here<br>    }<br></strong>  }<br>  return array;<br>}</pre><p>Notice the nested for loop is setup to iterate from index 0 to whatever the index of the outer for loop is minus one. Why? Well, we’ll get to that later. I just wanted you to notice that for now.</p><p><em>Step 4</em>: compare and swap:</p><pre>const bubbleSort = (array) =&gt; {<br>  for (let i = 0; i &lt; array.length; i++) {<br>    for (let x = 0; x &lt; array.length - 1 - i; x++) {<br><strong>      if (array[x] &gt; array[x + 1]) {<br>        [array[x], array[x + 1]] = [array[x + 1], array[x]];<br>      }</strong><br>    }<br>  }<br>  return array;<br>}</pre><p>And that’s it! We’re done!</p><p>So let’s say we call the above function like so:</p><pre>bubbleSort([10,9,8,7,6,5,4,3,2,1])</pre><p>The inner for loop checks to see if array[x] is greater than array[x + 1]— that is if 10 is greater than 9. Since it is, we swap them using <strong>ES6’s destructuring syntax</strong>. We then continue iterating until 10 gets pushed all the way to the right:</p><pre>[9,8,7,6,5,4,3,2,10]</pre><p>So this function is accomplishing what we talked about earlier. Hooray! But what happens after the inner for loop reaches its termination point (array.length — 1 — i)? Well, the outer for loop continues iterating and whereas array.length — 1 — i resolved to array.length — 1 — 0 in the first outer iteration, on the second it resolves to array.length — 1 — 1. Why? Well if you’ve been paying attention, you’ll know we already asked this ‘why’. Now we’re going to answer it.</p><p>Each time the inner for loop iterates, it pushes the largest elements all the way to the right. So after the first loop, we know for certain that the last element in array is the largest element because that element has been either directly or indirectly compared against every other element. Because we know this, there’s no reason to go on comparing other elements against it when the outer for loop does subsequent iterations. So for the sake of efficiency, we concern ourselves with only the part of the list we don’t know about. As a result, at the end of each iteration of the outer for loop, the array used for comparison effectively get’s smaller and smaller:</p><pre>[9,10,8,7,6,5,4,3,2,1]<br>[9,8,10,7,6,5,4,3,2,1]<br>[9,8,7,10,6,5,4,3,2,1]<br>[9,8,7,6,10,5,4,3,2,1]<br>[9,8,7,6,5,10,4,3,2,1]<br>[9,8,7,6,5,4,10,3,2,1]<br>[9,8,7,6,5,4,3,10,2,1]<br>[9,8,7,6,5,4,3,2,10,1]<br>[9,8,7,6,5,4,3,2,1,10]<br>[8,9,7,6,5,4,3,2,1]<br>[8,7,9,6,5,4,3,2,1]<br>[8,7,6,9,5,4,3,2,1]<br>[8,7,6,5,9,4,3,2,1]<br>[8,7,6,5,4,9,3,2,1]<br>[8,7,6,5,4,3,9,2,1]<br>[8,7,6,5,4,3,2,9,1]<br>[8,7,6,5,4,3,2,1,9]<br>[7,8,6,5,4,3,2,1]<br>[7,6,8,5,4,3,2,1]<br>[7,6,5,8,4,3,2,1]<br>[7,6,5,4,8,3,2,1]<br>[7,6,5,4,3,8,2,1]<br>[7,6,5,4,3,2,8,1]<br>[7,6,5,4,3,2,1,8]<br>[6,7,5,4,3,2,1]<br>[6,5,7,4,3,2,1]<br>[6,5,4,7,3,2,1]<br>[6,5,4,3,7,2,1]<br>[6,5,4,3,2,7,1]<br>[6,5,4,3,2,1,7]<br>[5,6,4,3,2,1]<br>[5,4,6,3,2,1]<br>[5,4,3,6,2,1]<br>[5,4,3,2,6,1]<br>[5,4,3,2,1,6]<br>[4,5,3,2,1]<br>[4,3,5,2,1]<br>[4,3,2,5,1]<br>[4,3,2,1,5]<br>[3,4,2,1]<br>[3,2,4,1]<br>[3,2,1,4]<br>[2,3,1]<br>[2,1,3]<br>[1,2]</pre><p>While the ordered part of the array grows larger and larger:</p><pre>[]<br>[]<br>[]<br>[]<br>[]<br>[]<br>[]<br>[]<br>[]<br>[10]<br>[10]<br>[10]<br>[10]<br>[10]<br>[10]<br>[10]<br>[10]<br>[9,10]<br>[9,10]<br>[9,10]<br>[9,10]<br>[9,10]<br>[9,10]<br>[9,10]<br>[8,9,10]<br>[8,9,10]<br>[8,9,10]<br>[8,9,10]<br>[8,9,10]<br>[8,9,10]<br>[7,8,9,10]<br>[7,8,9,10]<br>[7,8,9,10]<br>[7,8,9,10]<br>[7,8,9,10]<br>[6,7,8,9,10]<br>[6,7,8,9,10]<br>[6,7,8,9,10]<br>[6,7,8,9,10]<br>[5,6,7,8,9,10]<br>[5,6,7,8,9,10]<br>[5,6,7,8,9,10]<br>[4,5,6,7,8,9,10]<br>[4,5,6,7,8,9,10]<br>[3,4,5,6,7,8,9,10]<br>[1,2,3,4,5,6,7,8,9,10]</pre><p>There’s one more thing we can do to make this more efficient. We can detect whether or not disorder was found at all at any point after each time the inner for loop terminates. If no disorder was found, we can exit the outer for loop early!</p><p>How do we do this? I’m glad you asked. Here’s how:</p><pre>const bubbleSort = (array) =&gt; {<br>  <strong>let isOrdered;</strong><br>  for (let i = 0; i &lt; array.length; i++) {<br>    <strong>isOrdered = true;</strong><br>    for (let x = 0; x &lt; array.length - 1 - i; x++) {<br>      if (array[x] &gt; array[x + 1]) {<br>        [array[x], array[x + 1]] = [array[x + 1], array[x]];<br>        <strong>isOrdered = false;</strong><br>      }<br>    }<br>    <strong>if (isOrdered) break;</strong><br>  }<br>  return array;<br>}</pre><p>As you can see we added a flag: isOrdered. The flag gets set to true at the start of each iteration of the outer for loop and gets set to false if a swap is needed. This way a mostly ordered array like this one…</p><pre>[1,2,3,4,5,6,7,8,10,9]</pre><p>… will only require a total of 17 iterations to order it instead of 45! 9 inner iterations during the outer loops first iteration and 8 inner iterations during the outer loops second iteration. Because order is achieved in the first outer iteration, it gets detected by the second outer iteration and breaks before we enter a third outer iteration.</p><p><strong>Solution</strong></p><p>So I already gave the solution, but here it is again in color!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/649935770360f4aee593c39d3a951837/href">https://medium.com/media/649935770360f4aee593c39d3a951837/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=401140ad111c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: Pairwise]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-pairwise-e4b74c42e20a?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/e4b74c42e20a</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Sun, 25 Nov 2018 17:39:24 GMT</pubDate>
            <atom:updated>2018-11-25T17:49:04.844Z</atom:updated>
            <content:encoded><![CDATA[<p>My latest <a href="https://learn.freecodecamp.org/coding-interview-prep/algorithms/pairwise">freeCodeCamp</a> problem reads as follows:</p><blockquote>Given an array arr, find element pairs whose sum equal the second argument argand return the sum of their indices.</blockquote><blockquote>You may use multiple pairs that have the same numeric elements but different indices. Each pair should use the lowest possible available indices. Once an element has been used it cannot be reused to pair with another element.</blockquote><p><strong>Let’s take this one phrase at a time:</strong></p><blockquote><em>Given an array arr, find element pairs whose sum equal the second argument arg…</em></blockquote><p>So all it’s asking is to find all possible “pairs” (sets of two) that when added together equal arg (whatever that may be). Simple enough.</p><blockquote><em>… and return the sum of their indices.</em></blockquote><p>Once we find a pair that adds up to arg it wants us to add their indices together. What does this mean? Well, in JavaScript (and most other languages), the position of each element in an array (index or indices when we’re talking about more than one index) is 0 based. What does this mean? Well, all it means is rather than starting at 1 when referring to the position of an element in an array, we start with 0. So if we have an array of elements [1,2,3,4], their indices would correspond to each position like this:</p><pre>indices =&gt; 0 1 2 3 <br>array   =&gt;[1,2,3,4]</pre><p>So if arg happens to be 5 we’d know intuitively that 1 and 4 add up to 5. So using the above example ([1,2,3,4]), the elements at index 0 and 3 can be added together to equal 5. Huh? Yeah, it’s a little confusing if you don’t take some time to think about it for a second. The element at index 0 is 1. The element at index 3 is 4. So 1 + 4 = 5 and arg is set to 5 so this would be considered a pair that adds up to arg.</p><p>Taking it one step farther, we’re asked to add the indices of the matching pairs together. So if we add 0 and 3 together (0 + 3), we’d get 3. Pretty simple, right? Let’s complicate it a little more.</p><blockquote><em>You may use multiple pairs that have the same numeric elements but different indices.</em></blockquote><p>So if arr is [1,1,4,4] and arg is 5, we’re allowed to create the same pair twice ([1,4]) using the indices at index 0 and 2 as well as the indices at index 1 and 3.</p><blockquote><em>Each pair should use the lowest possible available indices.</em></blockquote><p>So if arr is [0,0,0,5] and arg is 5, we’re only allowed to create the pair using the 0 at index 0. We can’t use the 0 at index 1 or 2 because it asks us to use the lowest possible index.</p><blockquote><em>Once an element has been used it cannot be reused to pair with another element.</em></blockquote><p>So if arr is [1,0,1,5] and arg is 6, we’re only allowed to create ONE pair of [1,5] because we’re only allowed to use the5 once.</p><p><strong>Putting it all together</strong></p><p>Here’s what needs to happen to solve the original problem:</p><ol><li>Check to be sure arr is an array of numbers and arg is a number.</li><li>Create a variable (indicesSum) to keep track of the sum of indices. Set it to 0 since there are zero matches as of yet.</li><li>Loop through arr and subtract each element from arg to get the number that would be needed to add up to arg.</li><li>Search the rest of the list for elements that match that number taking care to not match on the current element or elements that have already been match. Also take care to match on the first occurrence of an element so we’re satisfying the requirement that the lowest possible indices are matched in the case elements that contain the same value.</li><li>If a match if found, add the current index and the match index to indicesSum.</li><li>Once we’ve finished looping through arr, return indicesSum.</li></ol><p><strong>Solution</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bd6224a14a64dfea5c6151c8edbd6e59/href">https://medium.com/media/bd6224a14a64dfea5c6151c8edbd6e59/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e4b74c42e20a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: No Repeats Please]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-no-repeats-please-173c3abb29fc?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/173c3abb29fc</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[recursion]]></category>
            <category><![CDATA[permutations]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Sat, 24 Nov 2018 04:40:57 GMT</pubDate>
            <atom:updated>2018-11-28T05:10:43.837Z</atom:updated>
            <content:encoded><![CDATA[<p>This <a href="https://learn.freecodecamp.org/coding-interview-prep/algorithms/no-repeats-please">freeCodeCamp</a> challenge reads as follows:</p><blockquote>Return the number of total permutations of the provided string that don’t have repeated consecutive letters. Assume that all characters in the provided string are each unique.</blockquote><blockquote>For example, aab should return 2 because it has 6 total permutations (aab, aab, aba, aba, baa, baa), but only 2 of them (aba and aba) don&#39;t have the same letter (in this case a) repeating.</blockquote><p>A few questions come up when reading this challenge.</p><ol><li>What is a permutation?</li><li>How do I get a list of all possible permutations?</li></ol><p><strong>What are permutations?</strong></p><p>A permutation is one possible ordering of a set. When someone asks for the permutations of a set, normally they’re referring to all possible orderings of a set. So for example, if you’re asked to give the permutations of abc, the answer would be:</p><pre>abc<br>acb<br>bac<br>bca<br>cab<br>cba</pre><p>Fun fact: the total number of permutations of a set can be determined by getting the factorial (<em>!n</em>) of number of items in the set (I go over factorials in detail in <a href="https://medium.com/@tdnelson/javascript-algorithms-factorial">this post</a>). Permutations, like factorial, grow exponentially as the number of items in the set increase. A set with 10 items would have well over 3 million possible permutations!</p><p><strong>Getting a list of permutations</strong></p><p>The easiest way to approach this is to think about each item in the set in isolation from the rest of the items in the set. So when asked to get the permutations of abc, you think:</p><pre>aPerms = a + total combination of rest of items in set<br>bPerms = b + total combination of rest of items in set<br>cPerms = c + total combination of rest of items in set</pre><pre>totalPermutations = aPerms + bPerms + cPerms</pre><p>Spelled out, this would look like:</p><pre>aPerm = &quot;a&quot; + &quot;bc&quot; || &quot;cb&quot;<br>bPerm = &quot;b&quot; + &quot;ac&quot; || &quot;ca&quot;<br>cPerm = &quot;c&quot; + &quot;ab&quot; || &quot;ba&quot;</pre><p>By doing this you can see (in this case) it’s pretty simple. When you remove a from abc you’re left with bc and we know intuitively that bc has only two possible orderings (bc and cb). So all possible orders where the list starts with a is only:</p><pre>abc<br>acb</pre><p>Follow the same pattern with the other items in the set and you get all possible orderings:</p><pre>abc<br>acb<br>bac<br>bca<br>cab<br>cba</pre><p>An observation: we notice that each item can only occupy the first position in the list two times — that is the factorial of one less than the number of items in the set (<em>!2</em>). If the set was abcd we would expect a to occupy the first position exactly 6 times because <em>!3</em> is <em>6</em>. If the list was abcde, a would be in first position <em>24 </em>times. If it was abcdef, that number would be <em>120</em>!</p><p><strong>What if the number of items is greater than 3?</strong></p><p>Well, we learn above that we can break it down to a point where it’s possible to figure it out intuitively. What’s stopping us from continuing with this pattern for more complicated sets?</p><p>Say we have a set with four items: abcd. The same logic as before applies to the scenario as well:</p><pre>aPerm = ((&quot;bc&quot; || &quot;cb&quot;) + &quot;d&quot;) || (&quot;dc&quot; || &quot;cd&quot; + &quot;b&quot;) || (&quot;bd&quot; || &quot;db&quot;+ &quot;c&quot;)<br>aPerm = [abcd, acbd, adcb, acdb, abdc, adbc]</pre><p><strong>How do we do this in JavaScript?</strong></p><p>If you attempt to do this in JavaScript without an algorithm, you’ll quickly get discouraged. You can do it (sort of) with &#39;abc&#39;:</p><pre>const bc = [&#39;bc&#39;, &#39;cb&#39;];<br>const ac = [&#39;ac&#39;, &#39;ca&#39;];<br>const ab = [&#39;ab&#39;, &#39;ba&#39;];</pre><pre>const aPerms = [];</pre><pre>bc.forEach(rest =&gt; {<br>  aPerms.push(&#39;a&#39; + rest);<br>});</pre><pre>const bPerms = [];</pre><pre>ac.forEach(rest =&gt; {<br>  aPerms.push(&#39;b&#39; + rest);<br>});</pre><pre>const cPerms = [];</pre><pre>ab.forEach(rest =&gt; {<br>  aPerms.push(&#39;c&#39; + rest);<br>});</pre><pre>const totalPerms = [...aPerms, ...bPerms, ...cPerms];</pre><pre>console.log(totalPerms) // `[&quot;abc&quot;, &quot;acb&quot;, &quot;bac&quot;, &quot;bca&quot;, &quot;cab&quot;, &quot;cba&quot;]`</pre><p>Once the number of items in the set grows beyond 3, things really start to get out of hand:</p><pre>const bcd = [&#39;bcd&#39;, &#39;bdc&#39;, &#39;cbd&#39;, &#39;cdb&#39;, &#39;dbc&#39;, &#39;dcb&#39;];<br>const acd = [&#39;acd&#39;, &#39;adc&#39;, &#39;cad&#39;, &#39;cda&#39;, &#39;dac&#39;, &#39;dca&#39; ];<br>const abd = [&#39;abd&#39;, &#39;adb&#39;, &#39;bad&#39;, &#39;bda&#39;, &#39;dab&#39;, &#39;dba&#39;];<br>const abc = [&#39;abc&#39;, &#39;acb&#39;, &#39;bac&#39;, &#39;bca&#39;, &#39;cab&#39;, &#39;cba&#39;];</pre><pre>const aPerms = [];</pre><pre>bcd.forEach(rest =&gt; {<br>  aPerms.push(&#39;a&#39; + rest);<br>});</pre><pre>const bPerms = [];</pre><pre>acd.forEach(rest =&gt; {<br>  aPerms.push(&#39;b&#39; + rest);<br>});</pre><pre>const cPerms = [];</pre><pre>abd.forEach(rest =&gt; {<br>  aPerms.push(&#39;c&#39; + rest);<br>});</pre><pre>const dPerms = [];</pre><pre>abc.forEach(rest =&gt; {<br>  aPerms.push(&#39;d&#39; + rest);<br>});</pre><pre>const totalPerms = [...aPerms, ...bPerms, ...cPerms, ...dPerms]; </pre><pre>console.log(totalPerms) // returns `[&quot;abcd&quot;, &quot;abdc&quot;, &quot;acbd&quot;, &quot;acdb&quot;, &quot;adbc&quot;, &quot;adcb&quot;, &quot;bacd&quot;, &quot;badc&quot;, &quot;bcad&quot;, &quot;bcda&quot;, &quot;bdac&quot;, &quot;bdca&quot;, &quot;cabd&quot;, &quot;cadb&quot;, &quot;cbad&quot;, &quot;cbda&quot;, &quot;cdab&quot;, &quot;cdba&quot;, &quot;dabc&quot;, &quot;dacb&quot;, &quot;dbac&quot;, &quot;dbca&quot;, &quot;dcab&quot;, &quot;dcba&quot;]`</pre><p><strong>How do we do this using a function?</strong></p><p><em>Enter </em><strong><em>recursion</em></strong><em>…</em></p><p>Recursion, simply put, is when a function calls itself (I talk about recursion in great detail <a href="https://medium.com/@tdnelson/javascript-algorithms-factorial-8aad841e883d#83d0">in my post about factorial</a>). <a href="https://medium.com/@zfrisch/understanding-recursion-in-javascript-992e96449e03">This post</a> also explains recursion really well but to boil it down, I’ll just borrow the example from it:</p><pre>function countDown(n) {<br>  console.log(n);<br>  if (n &gt;= 1) countDown(n-1);<br>}</pre><pre>countDown(10);</pre><p>So what’s happening here? Let’s walk through it. countDown(10) is called and it immediately encounters console.log(n) so it logs out 10. Then it hits the conditional statement asking whether n is greater than 1. It is! So we continue and call countDown() again, but this time we subtract 1 from 10 to get 9. Rinse and repeat until we get to 0. And that’s how recursion works. Pretty simple, right?</p><p>So how can we use this to achieve our objective. Before I can answer that I need to get something off my chest: I was not able to figure out how to write a permutations function in JavaScript on my own. Gasp! Yeah, I know. It’s embarrassing to have to admit to it but try as I may, it was just too complicated for me to figure out (being that math is not exactly my strong suit). However when I <a href="https://initjs.org/all-permutations-of-a-set-f1be174c79f8">discovered a solution</a>, I was well equipped to understand what was going on because I happened to know a thing or two about recursion. Here’s what I found:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c565cd1f9db1c9cd487e5d520d4d2047/href">https://medium.com/media/c565cd1f9db1c9cd487e5d520d4d2047/href</a></iframe><p>What’s going on here? Well, when getAllPermutations is called it first checks to see if string is only 1 character long. If that’s the case, no need to do additional work. Just put it in an array and return it. If it’s longer than one character we enter a for loop and get the first character from the string and assign it to a variable called firstChar. We then get the remaining characters and assign them to another variable called charsLeft.</p><p>This is where things get a little weird. Using the charsLeft, we call getAllPermutations again (recursion). That call continues to call itself until it gets to a single character which gets caught by if (string.length === 1). This gets returned and added to whichever nested recursion function it happens to be in all the way up the line until you get to the original for loop where it is finally added to the original firstChar once for each permutation in innerPermutations. Finally the loop continues on to the next character where it starts the process all over again. Whew! That’s a lot of recursion.</p><p><strong>Putting it all together</strong></p><p>Here’s what needs to happen to solve the original problem:</p><p>The original problem is asking for total permutations but with a slight twist. Instead of returning all permutations, it wants you to throw out any permutation that have two of the same characters side-by-side. So basically we’re just going to run the same permutations function we talked about earlier and then run the results through another loop that will filter out any permutations with repeating characters. Here’s a basic outline:</p><ol><li>Validate the input (must be a string and cannot be an empty string).</li><li>Get all the permutations (the specifics of how we did this are discussed above and code was modified using example found <a href="https://gist.github.com/mitrakmt/91f770699b0ba5639435be7a1a103461#file-permutations-js">here</a>).</li><li>Define a method (hasRepeat) that simply returns true or false if a string contains repeated characters.</li><li>Loop through all the permutations and call hasRepeat with each. If it returns false, add it to a new array.</li><li>Finally, count the new array and return the count.</li></ol><p><strong>Solution</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/018d61a223bee2ba52aebfddb2742eb9/href">https://medium.com/media/018d61a223bee2ba52aebfddb2742eb9/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=173c3abb29fc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: Inventory Update]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-inventory-update-13b5c2227cc6?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/13b5c2227cc6</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[matrix]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Fri, 23 Nov 2018 05:32:06 GMT</pubDate>
            <atom:updated>2018-11-23T17:07:51.621Z</atom:updated>
            <content:encoded><![CDATA[<p>Continuing my conquest of the <a href="https://learn.freecodecamp.org/coding-interview-prep/algorithms/inventory-update">FreeCodeCamp</a> algorithms series… my latest problem: <a href="https://learn.freecodecamp.org/coding-interview-prep/algorithms/inventory-update">updating a 2D array with data from another 2D array</a>.</p><p><strong>What is a 2D array?</strong></p><p>A two dimensional array (also known as a matrix) is an array of arrays. Each of the inner arrays contain the same number of elements. Each index of the inner array corresponds to a name much like each column in a table corresponds to a name. Still confused? Good. Here’s a diagram:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*L5t2sEL6eN6jr5xg7fAIFg.png" /><figcaption>Inventory in table form</figcaption></figure><p>Chances are you have no problem understanding the table above. Tables arrange things in rows and columns. The column header <em>names </em>everything in the corresponding column. Each row represents a single item and contain attributes describing that item. Those attributes are arranged into the column that corresponds to their name. You’ll notice that columns always contain the same type of element. For example, “Quantity” contains only numbers and “Item” contains only strings. This is an important constraint in 2D arrays and, in fact, it is a requirement.</p><p>Here’s what this would look like as a 2D array:</p><pre>const curInv = [<br>  [21, &#39;Bowling Ball&#39;],<br>  [2, &#39;Dirty Sock&#39;],<br>  [1, &#39;Hair Pin&#39;],<br>  [5, &#39;Microphone&#39;]<br>];</pre><p>Not that much different than a table, right? However, you’ll notice there isn’t anything telling you what each “column” means. It’s assumed you already know what each “column” means and your code is configured elsewhere to deal with it.</p><p>A few other things to notice:</p><ol><li>Each item in the outer array must be an array.</li><li>Each inner array must contain the same number of items.</li><li>The index of each inner array (column) must be the of the same type.</li></ol><p><strong>Putting it all together</strong></p><p>So to break it down, here are the procedures that must happen:</p><ol><li>Validate the two 2D arrays based on the above criteria.</li><li>Loop through the array containing the new data and determine whether each item exists in the inventory array.</li><li>If it does, update the quantity column.</li><li>If it doesn’t, create a new array and add it to the inventory array.</li><li>Sort the array alphabetically.</li></ol><p><strong>Solution</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5c390e514c6a1f001934c8165afeeb16/href">https://medium.com/media/5c390e514c6a1f001934c8165afeeb16/href</a></iframe><p>If you use this data…</p><pre>const curInv = [<br>  [21, &#39;Bowling Ball&#39;],<br>  [2, &#39;Dirty Sock&#39;],<br>  [1, &#39;Hair Pin&#39;],<br>  [5, &#39;Microphone&#39;]<br>];</pre><pre>const newInv = [<br>  [2, &#39;Hair Pin&#39;],<br>  [3, &#39;Half-Eaten Apple&#39;],<br>  [67, &#39;Bowling Ball&#39;],<br>  [7, &#39;Toothpaste&#39;]<br>];</pre><p>and run it though the update function…</p><pre>updateInventory(curInv, newInv)</pre><p>the result should be…</p><pre>[ <br>[ 88, &#39;Bowling Ball&#39; ],<br>[ 2, &#39;Dirty Sock&#39; ],<br>[ 3, &#39;Hair Pin&#39; ],<br>[ 3, &#39;Half-Eaten Apple&#39; ],<br>[ 5, &#39;Microphone&#39; ],<br>[ 7, &#39;Toothpaste&#39; ]<br>]</pre><p><strong>Let’s talk more about objects</strong></p><p>updateInventory doesn’t even need to return anything if you pass a predefined array as the first parameter. Why? Arrays are object and objects behave differently than value types when you pass them to functions. When you pass a value type (number or string), it <em>copies that value</em>. When you pass an object, it <em>copies the memory address to that object</em> but the object itself does not get copied. For example:</p><pre>let mynum = 1;<br>const fun = (num) =&gt; {num += 1;};<br>fun(mynum);<br>console.log(mynum) //returns `1`</pre><p>As you can see above, mynum is not affected when it gets passed into fun() because mynum is a value type. However if you were dealing with objects, it would be a different story:</p><pre>const arr = [&#39;hello&#39;];<br>const updateArray = (o) =&gt; {o[0] += &#39; world&#39;;};<br>updateArray(arr)<br>console.log(arr[0]) // returns `&#39;hello world&#39;`</pre><p>Since arr is an object, we’re coping the memory address to the arr when we pass it to the updateArray(). The object itself does not get copied so updateArray() ends up updating the original object and not simply a copy of the object.</p><p>So to bring this home, in updateInventory() we could omit return arr1; and curInv would still be updated. <strong><em>More importantly, if you did assign the result of </em></strong>updateInventory()<strong><em> to a new variable, you might be tempted to think it’s somehow different than </em></strong>curInv<strong><em> when in fact it is not.</em></strong> The new variable would point to the same spot in memory as curInv and you might end up confusing yourself if you expected to keep curInv untouched.</p><p>If you really wanted that to preserve curInv, I suggest you make a copy of it before you run it through updateInventory(). There are a number of ways you can do that but the quick and dirty way to do is is to convert it to a string then convert it back to an object:</p><pre>const CLONE = (obj) =&gt; {<br>  return JSON.parse(JSON.stringify(obj));<br>};</pre><pre>const clonedCurInv = CLONE(curInv);</pre><p>There are more eloquent (and probably more efficient) ways to do it but I’ve found that this works well in most cases.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=13b5c2227cc6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: Factorial]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-factorial-8aad841e883d?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/8aad841e883d</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Wed, 21 Nov 2018 23:28:34 GMT</pubDate>
            <atom:updated>2018-12-10T21:45:09.579Z</atom:updated>
            <content:encoded><![CDATA[<p>During a recent job interview, I was asked to write on a white board the necessary procedures to get the factorial of a number. My first question was, “What’s a factorial?”</p><p><strong>What’s a factorial?</strong></p><p>According to <a href="https://en.wikipedia.org/wiki/Factorial">Wikipedia</a>:</p><blockquote>In <a href="https://en.wikipedia.org/wiki/Mathematics">mathematics</a>, the <strong>factorial</strong> of a <a href="https://en.wikipedia.org/wiki/Non-negative_integer">non-negative integer</a> <em>n</em>, denoted by <em>n</em>!, is the <a href="https://en.wikipedia.org/wiki/Product_(mathematics)">product</a> of all positive <a href="https://en.wikipedia.org/wiki/Integer">integers</a> less than or equal to <em>n.</em></blockquote><p><strong>Huh!?</strong></p><p>Exactly! Yeah, it doesn’t make sense when you try to explain it using words. An example is needed:</p><p>So say we provide the number 4. This is what would happen:</p><pre>4 * (4 - 1) = 12<br>12 * (3 - 1) = 24<br>24 * (2 - 1) = 24</pre><p>So as you can see, you’re just taking the number and multiplying it by itself minus one then multiplying the result by the next lowest number until the original number finally becomes one. The last multiplication isn’t actually needed because we know anything multiplied by one is always one. I only included it to make it more clear what’s going on.</p><p>As you can see, as the input number gets larger, the result grows exponentially:</p><pre>5 * (5 - 1) = 20<br>20 * (4 - 1) = 60<br>60 * (3 - 1) = 120<br>120 * (2 - 1) = 120</pre><p>Once you get to the double digits the result balloons to over three million!</p><pre>10 * (10 - 1) = 90<br>90 * (9 - 1) = 720<br>720 * (8 - 1) = 5,040<br>5,040 * (7 - 1) = 30,240<br>30,240 * (6 - 1) = 151,200<br>151,200 * (5 - 1) = 604,800<br>604,800 * (4 - 1) = 1,814,400<br>1,814,400 * (3 - 1) = 3,628,800<br>3,628,800 * (2 - 1) = 3,628,800</pre><p><strong>Putting it all together</strong></p><p>Here’s what needs to happen to solve this:</p><ol><li>Make sure the input is a number.</li><li>If it’s zero, return 1 (since apparently the factorial of 0 is always 1).</li><li>Define a working variable and seed it with the input number.</li><li>Iterate while decrement the number until we get to 1 (we can exit early when we get to 1 because 1 multiplied by anything is always 1)</li></ol><p><strong>Solution</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/df760c7c29667ca16d5a8a58780cca0f/href">https://medium.com/media/df760c7c29667ca16d5a8a58780cca0f/href</a></iframe><p>Unfortunately, in JavaScript you can’t reliably get the factorial of anything larger than 18 because JavaScript number type specification only work between -9,007,199,254,740,991 and 9,007,199,254,740,991.</p><p><strong>Extra credit! Do it with recursion!</strong></p><p>In my <a href="https://medium.com/@tdnelson/javascript-algorithms-no-repeats-please-173c3abb29fc#deac">post about permutations</a>, I talked a lot about recursion because recursion is probably the best way to create a list of all possible orderings of a list. Often recursion can be used in place of a loop because instead of looping you just have the function call itself again using the result.</p><p>So here’s how you do factorial recursively!</p><pre>const factorial = (num) =&gt; {<br>  if (num === 0) return 1;<br>  return num * factorial(num - 1);<br>}</pre><p>Yep! That’s all there is to it. But how can this be, you ask? Well, that is a very good question. Recursion is difficult to intuit so we’ll need to break it down a bit.</p><p>So say we’re trying to get the factorial of 10. This is what’s happening in practice:</p><pre>const factorialTEN = () =&gt; {<br>  const ten = 10;<br>  const nineFunc = (nine) =&gt; {<br>    const eightFunc = (eight) =&gt; {<br>      const sevenFunc = (seven) =&gt; {<br>        const sixFunc = (six) =&gt; {<br>          const fiveFunc = (five) =&gt; {<br>            const fourFunc = (four) =&gt; {<br>              const threeFunc = (three) =&gt; {<br>                const twoFunc = (two) =&gt; {<br>                  const oneFunc = (one) =&gt; {<br>                    return one;<br>                  }<br>                  return two * oneFunc(two - 1);<br>                }<br>                return three * twoFunc(three - 1);<br>              }<br>              return four * threeFunc(four - 1);<br>            }<br>            return five * fourFunc(five - 1);<br>          }<br>          return six * fiveFunc(six - 1);<br>        }<br>        return seven * sixFunc(seven - 1);<br>      }<br>      return eight * sevenFunc(eight - 1);<br>    }<br>    return nine * eightFunc(nine - 1);<br>  }<br>  return ten * nineFunc(ten - 1);<br>}</pre><p>factorialTEN calls nineFunc which calls eightFunc which calls sevenFunc which calls sixFunc which calls fiveFunc which calls fourFunc which calls threeFunc which calls twoFunc which calls oneFunc. And rather than calling another function, oneFunc returns 1 which triggers everything to multiply like so:</p><pre>10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BFaO5x5q-9e0vkq-pBK7aQ.gif" /><figcaption>Cascading function calls</figcaption></figure><p>Why doesn’t the multiplication happen before all the cascading function calls? Well, the reason has to do with <em>order of operations</em>. The way code works is what’s inside the parentheses gets executed first. So in the case of factorialTEN we have ten sets of nested parentheses to bubble through before any multiplication can happen.</p><p>So there you have it. I did factorial recursively and I showed you what was going on.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8aad841e883d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JavaScript Algorithms: Symmetric Difference]]></title>
            <link>https://medium.com/@tdnelson/javascript-algorithms-symmetric-difference-b40f258e793f?source=rss-9c4f0e75ff0------2</link>
            <guid isPermaLink="false">https://medium.com/p/b40f258e793f</guid>
            <category><![CDATA[es6]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Tim Nelson]]></dc:creator>
            <pubDate>Wed, 21 Nov 2018 22:20:16 GMT</pubDate>
            <atom:updated>2018-11-28T16:48:32.187Z</atom:updated>
            <content:encoded><![CDATA[<p>I decided to start a series where I tackle basic algorithms head on. I’m getting my prompts from <a href="https://learn.freecodecamp.org/coding-interview-prep/algorithms/find-the-symmetric-difference/">freeCodeCamp</a>’s interview prep section. Each post will detail how I approached solving the code prompt.</p><p><strong>Where to start:</strong></p><p>The first step in creating an algorithm might seem pretty obvious but really it’s not: <strong>You must understand what problem you’re trying to solve. </strong>Case in point: when I first started working on <a href="https://learn.freecodecamp.org/coding-interview-prep/algorithms/find-the-symmetric-difference/">Symmetric Difference,</a> I thought I understood it so I launched into writing code right away. I thought all it meant was “find the elements that are unique to each array”. Unfortunately this was fundamentally incorrect.</p><p><strong>So what is Symmetric Difference?</strong></p><p>Well, to answer this I need to first explain where I went wrong. I read the first sentence of the <a href="https://learn.freecodecamp.org/coding-interview-prep/algorithms/find-the-symmetric-difference/">instructions at freeCodeCamp</a>:</p><blockquote>Create a function that takes two or more arrays and returns an array of the symmetric difference (△or ⊕) of the provided arrays.</blockquote><p>I thought I understood what it was. Given two or more arrays, return an array containing only unique elements — elements only found in one of the arrays. When providing only two arrays, this is correct. However, when providing more than two arrays, the rules change dramatically. To be honest, I found the instructions to be a little misleading because it seems to assume I already understood symmetric difference. Unfortunately, it had been a long time since I had taken an algebra class and I didn’t really remember Sets let alone Symmetric Difference. Here’s the missing information in the form of a very simple video with cool visuals:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FPxffSUQRkG4%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DPxffSUQRkG4&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FPxffSUQRkG4%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/fb8ceade8f64a80cd8ebb83cb5c171e4/href">https://medium.com/media/fb8ceade8f64a80cd8ebb83cb5c171e4/href</a></iframe><p><strong>Putting it all together</strong></p><p>So to break it down, here are the procedures that must happen:</p><ol><li>Validate the parameters (they all must be arrays).</li><li>Remove any duplicate items from each parameter.</li><li>If only one parameter is provided, return that parameter (with duplicates removed).</li><li>If more than one parameter is provided seed the unique variable using the first parameter then iterate over the remaining parameters comparing them against unique and replacing unique with the result.</li><li>Return unique sorted from smallest to largest.</li></ol><p><strong>Tools we can use</strong></p><p>ES6 gives us Set. A Set is a collection in which every item is unique. If you try to add an item that’s already in the Set, it has no effect. People coming from other languages (and mathematics) are very familiar with Setso it’s nice to finally have this tool in JavaScript.</p><p><strong>And here’s the solution…</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/363303e2f7922db85fcbdbab0f373540/href">https://medium.com/media/363303e2f7922db85fcbdbab0f373540/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b40f258e793f" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>