29:null 2a:["$","title",null,{"children":"March 31 (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":"32a000ee3a40c3e6","slug":"march-31-grad-algorithms","title":"March 31 (Grad Algorithms)","thumbnail":"fd498aa5aabb7f15dc1952b8e7283ffa21cc6c8123c50d3970001104d93f045f","access_level":"public","create_time":"$D2020-03-30T14:46:28.095Z","update_time":"$D2020-03-31T15:08:13.749Z","view_time":null,"first_public_time":"$D2020-03-31T15:10:00.387Z","has_unpublished_edits":null,"fork":false,"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":457,"publish_version":457,"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":8,"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 31 (Grad Algorithms)","cells":[{"id":0,"value":"html`

March 31 (Grad Algorithms)

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

Dividing an Array

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

Exercise 1

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

Before we can actually do the merge sort, we have to practice on more thing, and that is how to divide an unordered array. It should be pretty straightforward. To start, generate a data set in the usual way, but don't order it. Connect it to a slider so you can generate anywhere from 2 to 20 entries.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"viewof s = slider({min:2, max:20,step:1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"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":277,"value":"html`

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

Exercise 2

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

Use the entries function from the last notebook to draw the array.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":287,"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":290,"value":"v2.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":293,"value":"data2 = entries(v2.element,data,10,10,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":297,"value":"html`

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

Exercise 3

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

Can you write a function called \"divide\" that will take an array of entries, like the grey ones above, and create two new arrays of entries? The first should be identical to the first half of the original, and the second should be identical to the second half of the original. Color the first half tomato and the second half cornflowerblue. Draw them underneath the original array.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":309,"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":312,"value":"v3.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":315,"value":"divide = (element,data,x,y,leftColor,rightColor) => {\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:x+30*i,y:y,fill:leftColor,datumFill:\"white\",datum:data[i].datum}))\n }\n for(var i = middle; i < data.length; i++){\n right.push(new Entry({element:element,x:x+30*i,y:y,fill:rightColor,datumFill:\"white\",datum:data[i].datum}))\n }\n return [left,right]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":320,"value":"data3 = entries(v3.element,data,10,10,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"divide(v3.element,data3,10,50,\"tomato\",\"cornflowerblue\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":335,"value":"html`

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

Exercise 4

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

Can you modify the divide function (just name it divide2) so that the left and right halves drop down gradually from the original array?

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":351,"value":"v4 = {\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":355,"value":"v4.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"divide2 = (element,data,x,y,leftColor,rightColor,duration) => {\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:\"grey\",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:\"grey\",datumFill:\"white\",datum:data[i].datum}))\n right[i-middle].setY(y,duration,d3.easeLinear)\n right[i-middle].setFill(\"cornflowerblue\",duration)\n }\n return [left,right]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":358,"value":"data4 = entries(v4.element,data,10,10,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":366,"value":"divide2(v4.element,data4,10,50,\"tomato\",\"cornflowerblue\",2000)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":378,"value":"html`

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

Exercise 5

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

Can you use a button to start the divide?

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":389,"value":"v5 = {\n divideArray\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":395,"value":"data5 = entries(v5.element,data,10,10,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":392,"value":"v5.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":399,"value":"viewof b = button({value:\"divide\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":402,"value":"mutable divideArray = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":403,"value":"{\n s\n mutable divideArray = 0\n return \"divideArray to 0\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":407,"value":"{\n b\n mutable divideArray = 1\n return \"divideArray to 1\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":412,"value":"{\n if(mutable divideArray == 1){\n divide2(v5.element,data5,10,50,\"tomato\",\"cornflowerblue\",1000) \n }\n return \"divide\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"md`\n---\n## Libraries\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"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":17,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"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"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2e:"$2d:body"