29:null 2a:["$","title",null,{"children":"March 24 & 26 (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":"0d151e53ebb176dc","slug":"march-24-26-grad-algorithms","title":"March 24 & 26 (Grad Algorithms)","thumbnail":"598a2776f99e35ab3d3dba917ec6931bb729e93d61d6c0c3e209b737218dd49c","access_level":"public","create_time":"$D2020-03-21T16:41:42.265Z","update_time":"$D2020-04-14T16:31:59.335Z","view_time":null,"first_public_time":"$D2020-03-24T20:19:26.037Z","has_unpublished_edits":null,"fork":{"id":"af49e0dda0c055d4","slug":"march-17-grad-algorithms","title":"March 17 (Grad Algorithms)","owner":{"id":"66151b62b45d9fca","login":"credmond","name":"Charles Redmond"}},"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":1542,"publish_version":1542,"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":9,"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 24 & 26 (Grad Algorithms)","cells":[{"id":0,"value":"html`

March 24 & 26 (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":1204,"value":"html`

To continue the visualization of the merge, I brought over our two arrays, along with their sliders.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1167,"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":1169,"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":1171,"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":1173,"value":"viewof t = slider({min:1, max:10,step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1513,"value":"html`

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

Exercise 1

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

Can you create a function, called \"entries\", that will accept as parameters an ordinary array, an svg element, a color, and an (x,y) position, and then display a visualization of the array, using the Entry class? Make a v1, display it, then call the function to display array a, like below:

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1242,"value":"entries = (element,array,x,y,fill) => {\n var data = []\n for(var i = 0; i < array.length; i++){\n data.push(new Entry({element:element,x:30*i+x,y:y,fill:fill,datumFill:\"white\",datum:array[i]}))\n }\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1246,"value":"v1 = {\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":1256,"value":"v1.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1250,"value":"entries(v1.element,a,10,10,\"tomato\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1517,"value":"html`

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

Exercise 2

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

Can you now call the function twice to display array b, like below?

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1267,"value":"v2 = {\n s\n t\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":1270,"value":"v2.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1276,"value":"entries(v2.element,a,10,50,\"tomato\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1277,"value":"entries(v2.element,b,30*a.length+10,50,\"cornflowerblue\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1518,"value":"html`

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

Exercise 3

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

Can you write a revised merge function that will display a visualization of the merge of two ordered arrays? As parameters, it should take an x and a y (for position), and element to attach to, and two arrays of entries from the Entry class.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1309,"value":"merge = (element,a,b,x,y) => {\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].datum < b[j].datum){\n c.push(new Entry({element:element,x:30*k+x,y:y,fill:a[i].fill,datumFill:\"white\",datum:a[i].datum}))\n i++\n k++\n }else{\n c.push(new Entry({element:element,x:30*k+x,y:y,fill:b[j].fill,datumFill:\"white\",datum:b[j].datum}))\n j++\n k++\n }\n }\n\n while(i < a.length ){\n c.push(new Entry({element:element,x:30*k+x,y:y,fill:a[i].fill,datumFill:\"white\",datum:a[i].datum}))\n i++\n k++\n }\n\n while(j < b.length ){\n c.push(new Entry({element:element,x:30*k+x,y:y,fill:b[j].fill,datumFill:\"white\",datum:b[j].datum}))\n j++\n k++\n }\n return c \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1318,"value":"v3 = {\n s\n t\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":1322,"value":"v3.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1327,"value":"aEntries = entries(v3.element,a,10,50,\"tomato\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1330,"value":"bEntries = entries(v3.element,b,30*a.length+10,50,\"cornflowerblue\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1336,"value":"merge(v3.element,aEntries,bEntries,10,10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1520,"value":"html`

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

Exercise 4

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

Can you modify the merge function so that the merge proceeds one entry at a time, like so: (just call the function merge2)

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1349,"value":"merge2 = async (element,a,b,x,y,duration) => {\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].datum < b[j].datum){\n c.push(new Entry({element:element,x:a[i].x,y:a[i].y,fill:a[i].fill,datumFill:\"white\",datum:a[i].datum}))\n i++\n k++\n }else{\n c.push(new Entry({element:element,x:b[j].x,y:b[j].y,fill:b[j].fill,datumFill:\"white\",datum:b[j].datum}))\n j++\n k++\n }\n }\n\n while(i < a.length ){\n c.push(new Entry({element:element,x:a[i].x,y:a[i].y,fill:a[i].fill,datumFill:\"white\",datum:a[i].datum}))\n i++\n k++\n }\n\n while(j < b.length ){\n c.push(new Entry({element:element,x:b[j].x,y:b[j].y,fill:b[j].fill,datumFill:\"white\",datum:b[j].datum}))\n j++\n k++\n }\n for(var k=0;k`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1386,"value":"html`

Exercise 5

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1502,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1504,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1506,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1508,"value":"html`\n\n\n`\n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1511,"value":"html`\n\n\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1389,"value":"html`

(Don't try this until viewing the video. There are new concepts here.) Finally, make it so that the sort does not happen until a button is clicked.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1391,"value":"v5 = {\n mergeArrays\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":1395,"value":"v5.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1409,"value":"viewof bt = button({value:\"merge\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1398,"value":"aEntries3 = entries(v5.element,a,10,50,\"tomato\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1400,"value":"bEntries3 = entries(v5.element,b,30*a.length+10,50,\"cornflowerblue\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1434,"value":"mutable mergeArrays = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1435,"value":"{\n s\n t\n mutable mergeArrays = 0\n return \"mergeArrays to 0\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1439,"value":"{\n bt\n mutable mergeArrays = 1\n return \"mergeArrays to 1\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1416,"value":"{\n if(mutable mergeArrays == 1){\n merge2(v5.element,aEntries3,bEntries3,10,10,300) \n }\n return \"merge\"\n}","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"