29:null 2a:["$","title",null,{"children":"April 7 & 9(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":"143b23233de269f1","slug":"april-7-9-grad-algorithms","title":"April 7 & 9(Grad Algorithms)","thumbnail":"2c54290af3a388cd1ac5b2ceb83eae8052bfb39c2fc3cf58134c73847c17efd8","access_level":"public","create_time":"$D2020-04-07T12:54:35.807Z","update_time":"$D2020-04-14T23:18:35.360Z","view_time":null,"first_public_time":"$D2020-04-08T19:31:39.019Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"66151b62b45d9fca","login":"credmond","name":"Charles Redmond","avatar_url":"https://avatars-next.observableusercontent.com/50425ed9f407a7b47d1c471a09963f335e0652ab9acc237869e2d7949fb04a77","tier":"starter_2024"},"version":367,"publish_version":367,"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":"April 7 & 9(Grad Algorithms)","cells":[{"id":0,"value":"html`

April 7 & 9(Grad Algorithms)

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

Merge Sort

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

Exercise 1

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":340,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"html`In this exercise, let's just go over what you need to have in the Libraries section.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"html`

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

Exercise 2

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":342,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"html`Let's practice divide again. Generate an unordered data set as before, visualize it, and divide it.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"data = {\n var data = []\n for(var i = 0; i < s; i++){\n data.push(Math.floor(Math.random()*100))\n }\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"data2 = entries(v2.element,data,10,10,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"divide(v2.element,data2,10,50,\"tomato\",\"cornflowerblue\",1000)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"v2 = {\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":68,"value":"v2.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"html`

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

Exercise 3

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"html`Now let's practice merge again. Remember, we have to start with two sorted arrays. We could just call them left and right.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"left = {\n var data = []\n for(var i = 0; i < l; 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":95,"value":"viewof l = slider({min:1, max:10,step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"right = {\n var data = []\n for(var i = 0; i < r; 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":98,"value":"viewof r = slider({min:1, max:10,step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"html`Visualize them and merge them. Can you modify the merge function so that the blocks transition to the color of your choice as they merge up?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"left3 = entries(v3.element,left,10,50,\"tomato\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"right3 = entries(v3.element,right,30*left.length+10,50,\"cornflowerblue\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":124,"value":"merge(v3.element,left3,right3,10,10,1000,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":108,"value":"v3 = {\n l\n r\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":111,"value":"v3.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"html`

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

Exercise 4

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":346,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"html`Let's practice again the divide with recursion.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"v4 = {\n s\n var svg = d3.select(DOM.svg(900,250)).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":179,"value":"data4 = entries(v4.element,data,10,10,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":184,"value":"sort(v4.element,data4,10,50,\"tomato\",\"cornflowerblue\",400)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"v4.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":192,"value":"html`

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

Exercise 5

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":348,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":354,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":356,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"v5 = {\n speed\n sortArray\n var svg = d3.select(DOM.svg(900,250)).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":206,"value":"data5 = entries(v5.element,data,10,10,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":310,"value":"{\n if(mutable sortArray == 1){\n sort2(v5.element,data4,10,10,\"tomato\",\"cornflowerblue\",duration) \n }\n return \"sort\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"viewof s = slider({min:2, max:29,step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":331,"value":"viewof speed = radio({options:[\"slow\",\"fast\"],value:\"slow\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"v5.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":306,"value":"viewof b = button({value:\"sort\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"md`\n---\n## Libraries\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"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":33,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":73,"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":40,"value":"merge = async (element,a,b,x,y,duration,color) => {\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 {\n var middle = Math.floor(data.length/2)\n var left = []\n var right = []\n for(var i = 0; i < middle; i++){\n left.push(new Entry({element:element,x:data[i].x,y:data[i].y,fill:data[0].fill,datumFill:\"white\",datum:data[i].datum}))\n left[i].setY(y,duration,d3.easeLinear)\n left[i].setFill(\"tomato\",duration)\n }\n for(var i = middle; i < data.length; i++){\n right.push(new Entry({element:element,x:data[i].x,y:data[i].y,fill:data[0].fill,datumFill:\"white\",datum:data[i].datum}))\n right[i-middle].setY(y,duration,d3.easeLinear)\n right[i-middle].setFill(\"cornflowerblue\",duration)\n }\n var done = data[0].setDatumFill(\"white\",duration).delay(duration/2)\n return [left,right,done]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"sort = { \n var sort = async (element,data,x,y,leftColor,rightColor,duration) => {\n var halves = divide(element,data,x,y,leftColor,rightColor,duration)\n var left = halves[0]\n var right = halves[1]\n await halves[2].end()\n if(left.length > 1){\n sort(element,left,left[0].x,y+40,leftColor,rightColor,duration)\n }\n if(right.length > 1){\n sort(element,right,right[0].x,y+40,leftColor,rightColor,duration)\n }\n }\n return sort\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":"sort2 = { \n var sort2 = async (element,data,x,y,leftColor,rightColor,duration) => {\n var halves = divide(element,data,x,y+40,leftColor,rightColor,duration)\n var left = halves[0]\n var right = halves[1]\n await halves[2].end()\n if(data.length == 2){\n return merge(element,left,right,x,y,duration,data[0].fill)\n }else if(data.length == 3){\n var rightSorted = await sort2(element,right,right[0].x,y+40,\"tomato\",\"cornflowerblue\",duration)\n return merge(element,left,rightSorted,x,y,duration,data[0].fill) \n }else{\n var leftSorted = await sort2(element,left,left[0].x,y+40,\"tomato\",\"cornflowerblue\",duration)\n var rightSorted = await sort2(element,right,right[0].x,y+40,\"tomato\",\"cornflowerblue\",duration)\n return merge(element,leftSorted,rightSorted,x,y,duration,data[0].fill)\n }\n \n }\n return sort2\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":300,"value":"mutable sortArray = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":303,"value":"{\n s\n mutable sortArray = 0\n return \"sortArray to 0\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":304,"value":"{\n b\n mutable sortArray = 1\n return \"sortArray to 1\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":335,"value":"duration = {\n if(speed == \"slow\"){var duration = 1000}\n else{var duration = 150}\n return duration\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"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"