29:null 2a:["$","title",null,{"children":"April 14 & 16(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":"268828c3e8e7364e","slug":"april-14-16-grad-algorithms","title":"April 14 & 16(Grad Algorithms)","thumbnail":"044f6f87a4c58a6406c072c60874e8d9224a4ac746481f9b44bfc4517a4f2f34","access_level":"public","create_time":"$D2020-04-13T13:53:29.238Z","update_time":"$D2020-04-14T15:27:54.883Z","view_time":null,"first_public_time":"$D2020-04-14T15:30:45.575Z","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":567,"publish_version":567,"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 14 & 16(Grad Algorithms)","cells":[{"id":0,"value":"html`

April 14 & 16(Grad Algorithms)

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

Partitioning An Array

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":515,"value":"html`Next up is the quick sort, but before that we have to learn how to partition an array around a pivot. To get started, once again generate an unsorted array.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"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":7,"value":"html`

Exercise 1

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":543,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":518,"value":"html`Visualize the array. Then begin to write a function called \"partition\". In this exercise, it should simply change the color of the last entry.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"data1 = entries(v1.element,data,10,40,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"pData1 = partition1(data1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"v1.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"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":335,"value":"partition1 = (data) => {\n var l = data.length \n data[l-1].setFill(\"goldenrod\",0)\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":311,"value":"html`

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

Exercise 2

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":545,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":522,"value":"html`Continue to develop the partition function. In this exercise, have it draw a verticle line at the beginning of the array.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":317,"value":"data2 = entries(v2.element,data,10,40,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":338,"value":"pData2 = partition2(v2.element,data2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":329,"value":"v2.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":325,"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":65,"value":"partition2 = (element,data) => {\n var l = data.length\n var pIndex = 0\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 return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":353,"value":"html`

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

Exercise 3

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":547,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":526,"value":"html`Make the partition function now highlight each entry in order, with a particular color. (I used cornflowerblue.) Don't highlight the last entry.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":359,"value":"data3 = entries(v3.element,data,10,40,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":371,"value":"pData3 = partition3(v3.element,data3,1000)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"v3.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":362,"value":"v3 = {\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":367,"value":"partition3 = async (element,data,duration) => {\n var l = data.length\n var pIndex = 0\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 data[i].setFill(\"grey\",duration).end()\n }\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":381,"value":"html`

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

Exercise 4

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":549,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":530,"value":"html`Write a \"swap\" function that will swap the positions of two given entries. Try it out.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":386,"value":"data4 = entries(v4.element,data,10,40,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":415,"value":"swap4(data4,3,7,1000,d3.easeLinear)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":391,"value":"v4.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":388,"value":"v4 = {\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":412,"value":"swap4 = 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 await data[index2].setY(40,duration,ease).end()\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":424,"value":"html`

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

Exercise 5

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":551,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":560,"value":"html`\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":533,"value":"html`Complete the partition function and pull everything together. I think I will have to use the video here to explain what should happen.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":447,"value":"data5 = entries(v5.element,data,10,40,\"grey\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":493,"value":"{\n if(mutable partitionArray == 1){\n partition5(v5.element,data5,duration,d3.easeLinear) \n }\n return \"partition\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":503,"value":"viewof speed = radio({options:[\"slow\",\"fast\"],value:\"slow\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":479,"value":"viewof b = button({value:\"partition\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":254,"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":436,"value":"v5.display","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":427,"value":"v5 = {\n speed\n partitionArray\n var svg = d3.select(DOM.svg(900,300)).attr(\"style\",\"background:white;border:1px solid white\")\n yield {element:svg,display:svg.node()} \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":443,"value":"partition5 = 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 swap5(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 swap5(data,pIndex,l-1,duration,ease)\n return data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":439,"value":"swap5 = 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":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":15,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"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":483,"value":"mutable partitionArray = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":485,"value":"{\n s\n mutable partitionArray = 0\n return \"partitionArray to 0\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"{\n b\n mutable partitionArray = 1\n return \"partitionArray to 1\"\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":508,"value":"duration = {\n if(speed == \"slow\"){var duration = 500}\n else{var duration = 150}\n return duration\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2e:"$2d:body"