29:null 2a:["$","title",null,{"children":"April 21 and 23(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":"524f9911d25e63f2","slug":"april-21-and-23-grad-algorithms","title":"April 21 and 23(Grad Algorithms)","thumbnail":"4e2354ce40baf61a089314466fcd6e2992630ee09a8e00331a1b148a242084d0","access_level":"public","create_time":"$D2020-04-21T12:47:20.978Z","update_time":"$D2020-04-21T18:49:51.249Z","view_time":null,"first_public_time":"$D2020-04-21T18:49:57.285Z","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":181,"publish_version":181,"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":6,"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 21 and 23(Grad Algorithms)","cells":[{"id":0,"value":"html`

April 21 and 23(Grad Algorithms)

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

The Quick Sort

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

Exercise 1

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":170,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"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":49,"value":"data1 = entries(v1.element,data,10,40,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"pData1 = partition(v1.element,data1,100,d3.easeLinear)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"v1.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"v1 = {\n s\n var svg = d3.select(DOM.svg(900,250)).attr(\"style\",\"background:white;border:1px solid black\")\n yield {element:svg,display:svg.node()} \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"html`

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

Exercise 2

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":172,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"data2 = entries(v2.element,data,10,40,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"partitionFinal(v2.element,data2,500,d3.easeLinear,5,10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"v2.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"v2 = {\n s\n var svg = d3.select(DOM.svg(900,250)).attr(\"style\",\"background:white;border:1px solid black\")\n yield {element:svg,display:svg.node()} \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"html`

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

Exercise 3

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"data3 = entries(v3.element,data,10,40,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"{\n if(mutable sortArray == 1){\n sort(v3.element,data3,duration,d3.easeLinear,0,data3.length-1)\n }\n return \"sort\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":135,"value":"viewof speed = radio({options:[\"slow\",\"fast\"],value:\"slow\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"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":93,"value":"v3.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"viewof b = button({value:\"sort\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"v3 = {\n speed\n sortArray\n var svg = d3.select(DOM.svg(900,250)).attr(\"style\",\"background:white;border:1px solid black\")\n yield {element:svg,display:svg.node()} \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"md`\n---\n## Libraries\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"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":13,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"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":26,"value":"swap = async (data,index1,index2,duration,ease) => {\n var temp = data[index1]\n data[index1] = data[index2]\n data[index2] = temp\n \n var temp = data[index1].x\n data[index1].setY(10,duration,ease)\n await data[index2].setY(70,duration,ease).end()\n data[index1].setX(data[index2].x,duration,ease) \n await data[index2].setX(temp,duration,ease).end()\n data[index1].setY(40,duration,ease)\n return data[index2].setY(40,duration,ease).end()\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"partition = async (element,data,duration,ease) => {\n var l = data.length\n var pIndex = 0\n var pivot = data[l-1].datum\n data[l-1].setFill(\"goldenrod\",0)\n \n var line = element.append(\"line\")\n .attr(\"x1\",data[pIndex].x)\n .attr(\"y1\",10)\n .attr(\"x2\",data[pIndex].x)\n .attr(\"y2\",100)\n .attr(\"stroke\",\"black\")\n \n for(var i = 0;i < l-1; i++){\n await data[i].setFill(\"cornflowerblue\",duration).end()\n if(data[i].datum <= pivot){\n if(i != pIndex){\n await swap(data,pIndex,i,duration,ease)\n }\n line.transition().duration(duration).attr(\"x1\",data[pIndex+1].x).attr(\"x2\",data[pIndex+1].x).end()\n await data[pIndex].setFill(\"grey\",duration).end()\n pIndex++\n }else{\n await data[i].setFill(\"grey\",duration).end()\n }\n \n }\n await swap(data,pIndex,l-1,duration,ease)\n data[pIndex].setFill(\"green\",0)\n return pIndex\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"partitionFinal = async (element,data,duration,ease,low,high) => {\n var l = high - low + 1\n var pIndex = low\n var pivot = data[high].datum\n data[high].setFill(\"goldenrod\",0)\n \n var line = element.append(\"line\")\n .attr(\"x1\",data[pIndex].x)\n .attr(\"y1\",10)\n .attr(\"x2\",data[pIndex].x)\n .attr(\"y2\",100)\n .attr(\"stroke\",\"black\")\n \n for(var i = low;i < high; i++){\n await data[i].setFill(\"cornflowerblue\",duration).end()\n if(data[i].datum <= pivot){\n if(i != pIndex){\n await swap(data,pIndex,i,duration,ease)\n }\n line.transition().duration(duration).attr(\"x1\",data[pIndex+1].x).attr(\"x2\",data[pIndex+1].x).end()\n await data[pIndex].setFill(\"grey\",duration).end()\n pIndex++\n }else{\n await data[i].setFill(\"grey\",duration).end()\n }\n \n }\n await swap(data,pIndex,high,duration,ease)\n data[pIndex].setFill(\"green\",0)\n return pIndex\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"sort = {\n var sort = async (element,data,duration,ease,low,high) => {\n if(low < high){\n var pIndex = await partitionFinal(element,data,duration,ease,low,high)\n sort(element,data,duration,ease,low,pIndex - 1)\n sort(element,data,duration,ease,pIndex + 1,high)\n }else{\n data[low].setFill(\"green\",0)\n }\n }\n return sort\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"mutable sortArray = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"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":128,"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":133,"value":"duration = {\n if(speed == \"slow\"){var duration = 300}\n else{var duration = 50}\n return duration\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"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"