29:null 2a:["$","title",null,{"children":"March 17 (Grad Algorithms) | Charles Redmond | Observable"}] 2f:T4f7,class Entry{ constructor(props){ Object.keys(props).forEach((key)=>{this[key] = props[key]}) this.outer = this.element.append("g").attr("transform",`translate(${this.x},${this.y})`) this.inner = this.outer.append("g") this.square = this.inner.append("rect") .attr("width",30) .attr("height",30) .attr("stroke","black") .attr("fill",this.fill) this.text = this.inner.append("text") .text(this.datum) .attr("font-size",20) .attr("text-anchor","middle") .attr("x",15) .attr("y",22) .attr("fill",this.datumFill) } setFill(fill,duration){ this.fill = fill return this.square.transition().duration(duration).attr("fill",this.fill) } setDatum(datum){ this.datum = datum this.text.text(this.datum) } setDatumFill(datumFill,duration){ this.datumFill = datumFill return this.text.transition().duration(duration).attr("fill",this.datumFill) } setX(x,duration,ease){ this.x = x return this.outer.transition().duration(duration).ease(ease).attr("transform",`translate(${this.x},${this.y})`) } setY(y,duration,ease){ this.y = y return this.outer.transition().duration(duration).ease(ease).attr("transform",`translate(${this.x},${this.y})`) } }30:[] 2d:{"id":"af49e0dda0c055d4","slug":"march-17-grad-algorithms","title":"March 17 (Grad Algorithms)","thumbnail":"95a59b35695170f65ee139b3d745259570e64a2acff6c30cde0a9f82b5b66261","access_level":"public","create_time":"$D2020-03-16T18:55:17.460Z","update_time":"$D2020-03-17T22:01:52.708Z","view_time":null,"first_public_time":"$D2020-03-17T22:39:38.940Z","has_unpublished_edits":null,"fork":true,"stars":1,"starred":false,"owner":{"type":"team","id":"66151b62b45d9fca","login":"credmond","name":"Charles Redmond","avatar_url":"https://avatars-next.observableusercontent.com/50425ed9f407a7b47d1c471a09963f335e0652ab9acc237869e2d7949fb04a77","tier":"starter_2024"},"version":1112,"publish_version":1112,"role":null,"authored":false,"authors":[{"type":"individual","id":"37a987477e8b6db3","login":"credmond","name":"Charles Redmond","avatar_url":"https://avatars-next.observableusercontent.com/50425ed9f407a7b47d1c471a09963f335e0652ab9acc237869e2d7949fb04a77","tier":null}],"members":[{"type":"individual","id":"37a987477e8b6db3","login":"credmond","name":"Charles Redmond","avatar_url":"https://avatars-next.observableusercontent.com/50425ed9f407a7b47d1c471a09963f335e0652ab9acc237869e2d7949fb04a77","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":12,"collection":{"id":"a0b64515e1b8d7b3","slug":"data-structures-and-algorithms","title":"Data Structures and Algorithms","owner":{"id":"66151b62b45d9fca","login":"credmond","name":"Charles Redmond"}},"type":"notebook","body":{"title":"March 17 (Grad Algorithms)","cells":[{"id":0,"value":"html`

March 17 (Grad Algorithms)

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":836,"value":"html`

Merging Two Arrays

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":854,"value":"html`

Our next task is to understand the merge sort algorithm. Before we can do that, we have to know how to merge two sorted arrays. That's what we will take up today. I will first show you how to merge two sorted arrays, without programming any visualization. After that, we'll tackle the visualization. I'm going to set everything up as a series of exercises. Try them first without looking at the code.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1065,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":863,"value":"a = {\n var data = []\n for(var i = 0; i < s; i++){\n data.push(Math.floor(Math.random()*100))\n }\n data = data.sort((x,y) => x - y)\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":867,"value":"viewof s = slider({min:1, max:10,step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":865,"value":"b = {\n var data = []\n for(var i = 0; i < t; i++){\n data.push(Math.floor(Math.random()*100))\n }\n data = data.sort((x,y) => x - y)\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":868,"value":"viewof t = slider({min:2, max:10,step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":840,"value":"html`

Exercise 1

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":858,"value":"html`

Generate two sorted data sets of integers between 0 and 99. Call them a and b. Give each a slider so that the user can generate between 1 and 10 entries.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":879,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":885,"value":"html`

Exercise 2

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1072,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1074,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":882,"value":"html`

Above, I describe beginning to merge the arrays a and b, without the \"leftovers\". Do that below.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":888,"value":"{\n var c = []\n var i = 0\n var j = 0\n var k = 0\n \n while(i < a.length && j < b.length){\n if(a[i] < b[j]){\n c.push(a[i])\n i++\n k++\n }else{\n c.push(b[j])\n j++\n k++\n }\n }\n return c\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":894,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":897,"value":"html`

Exercise 3

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1077,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1079,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":901,"value":"html`

Again, with the hints from the video, add the \"leftovers\".

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":905,"value":"{\n var c = []\n var i = 0\n var j = 0\n var k = 0\n \n while(i < a.length && j < b.length){\n if(a[i] < b[j]){\n c.push(a[i])\n i++\n k++\n }else{\n c.push(b[j])\n j++\n k++\n }\n }\n \n while(i < a.length ){\n c.push(a[i])\n i++\n k++\n }\n \n while(j < b.length ){\n c.push(b[j])\n j++\n k++\n }\n return c\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":908,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":912,"value":"html`

Exercise 4

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1087,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":916,"value":"html`

Turn your code above into a function that accepts two ordered arrays and merges them.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":919,"value":"merge = (a,b) => {\n \n var c = []\n var i = 0\n var j = 0\n var k = 0\n\n while(i < a.length && j < b.length){\n if(a[i] < b[j]){\n c.push(a[i])\n i++\n k++\n }else{\n c.push(b[j])\n j++\n k++\n }\n }\n\n while(i < a.length ){\n c.push(a[i])\n i++\n k++\n }\n\n while(j < b.length ){\n c.push(b[j])\n j++\n k++\n }\n return c \n }\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1040,"value":"merge(a,b)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":926,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1089,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":924,"value":"html`

Excellent! You now know how to merge two sorted arrays. Let's now work on the visualization. My approach here is going to be a little different, so I'll give plenty of warm up exercises.

First, however, I want to show you a slightly different way of rendering the SVG canvas. The reason I am doing this is that I would like to have the svg variable available outside the code, to the rest of the notebook.

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":934,"value":"v = {\n var svg = d3.select(DOM.svg(900,90)).attr(\"style\",\"background:white;border:1px solid black\")\n \n yield {element:svg,display:svg.node()} \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":936,"value":"html`

Not that I am yielding BOTH svg and svg.node(). It is svg.node() that will give us the display, as follows:

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":939,"value":"v.display","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":946,"value":"html`

I can now use v.element, which is the svg variable, anywhere in the notebook.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":949,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":930,"value":"html`

Exercise 5

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1091,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":959,"value":"html`

We need to get back into the practice of using the classes we've written. For this lesson, I am only going to use the Entry class. Here is an easy exercise: simply create an entry with datum 4. Note that above I used the variable v (for visualization). Each time we add a visualization, we'll use variables like v1, v2, v3, etc.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":962,"value":"v1 = {\n var svg = d3.select(DOM.svg(900,90)).attr(\"style\",\"background:white;border:1px solid black\")\n new Entry({element:svg,x:10,y:10,fill:\"white\",datumFill:\"black\",datum:4})\n yield {element:svg,display:svg.node()} \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":965,"value":"v1.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":972,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":975,"value":"html`

Exercise 6

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1093,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":978,"value":"html`

We don't yet have a method in our Entry class that allows us to change the datum. Go ahead and provide one. Then write a program that displays an entry of 4 that changes to 10 after a second. You cannot transition text, so you will have to figure out some other way to display 4 for a second before it changes to 10.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":982,"value":"v2 = {\n var svg = d3.select(DOM.svg(900,90)).attr(\"style\",\"background:white;border:1px solid black\")\n var entry = new Entry({element:svg,x:10,y:10,fill:\"white\",datumFill:\"black\",datum:4})\n yield {element:svg,display:svg.node()}\n \n await svg.transition().duration(2000).attr(\"style\",\"background:white;border:1px solid black\").end()\n entry.setDatum(10)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":985,"value":"v2.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":993,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":998,"value":"html`

Exercise 7

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1095,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1002,"value":"html`

Can you make an array of Entry objects, in a cell separate from the visualization cell, where the datum correspond to the array a above? The entries should automatically show up in the visualization. Put a reference to the variable s above in the visualization cell, so that the cell will be re-rendered when the slider is moved.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1010,"value":"v3 = {\n s\n var svg = d3.select(DOM.svg(900,90)).attr(\"style\",\"background:white;border:1px solid black\")\n\n yield {element:svg,display:svg.node()} \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1013,"value":"v3.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1007,"value":"{\n var data = []\n for(var i = 0; i < s; i++){\n data.push(new Entry({element:v3.element,x:30*i+10,y:10,fill:\"tomato\",datumFill:\"white\",datum:a[i]}))\n }\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1029,"value":"html`

Enough for tonight!

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"md`\n---\n## Libraries\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"import {slider,button,select,text,radio,checkbox,number} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":831,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2e:"$2d:body"