Skip to content

Instantly share code, notes, and snippets.

@logston

logston/Unordered Insertion Sort.ipynb

Last active September 2, 2023 19:05
Show Gist options
  • Save logston/25ab4821c6d190e8751dac6b95af2042 to your computer and use it in GitHub Desktop.
Save logston/25ab4821c6d190e8751dac6b95af2042 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
Unordered Insertion Sort.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"id": "1772ac34-53e9-4017-8c68-22d9171ec90d",
"metadata": {},
"outputs": [],
"source": [
"class InsertionSort:\n",
" def __init__(self):\n",
" self.ops = 0\n",
"\n",
" def sort(self, a: list):\n",
" \"\"\"\n",
" Pulled from: \n",
" Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., and Stein, Clifford. \n",
" Introduction to Algorithms, Fourth Edition. Cambridge: MIT Press, 2022. \n",
" \"\"\"\n",
" if not len(a):\n",
" return []\n",
" \n",
" for i in range(1, len(a)):\n",
" key = a[i]\n",
" j = i - 1\n",
" # Move down the line to make some space.\n",
" while j >= 0 and a[j] > key:\n",
"\n",
" self.ops += 1 # Track major op (moving data)\n",
" a[j + 1] = a[j]\n",
" j -= 1\n",
" \n",
" self.ops += 1 # Track major op (moving data)\n",
" a[j + 1] = key\n",
" \n",
" return a"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "396c9519-b7cd-4de7-a453-66773a23ea26",
"metadata": {},
"outputs": [],
"source": [
"# Spot checks\n",
"assert InsertionSort().sort([]) == []\n",
"assert InsertionSort().sort([1]) == [1]\n",
"assert InsertionSort().sort([1, 2, 3]) == [1, 2, 3]\n",
"assert InsertionSort().sort(list(reversed(range(10)))) == list(range(10))\n",
"\n",
"isort = InsertionSort()\n",
"isort.sort([]) \n",
"assert isort.ops == 0\n",
"\n",
"isort = InsertionSort()\n",
"isort.sort([1, 2, 3]) \n",
"assert isort.ops == 2, isort.ops\n",
"\n",
"isort = InsertionSort()\n",
"isort.sort([3, 2, 1]) \n",
"assert isort.ops == 5, isort.ops\n",
"\n",
"isort = InsertionSort()\n",
"isort.sort(list(reversed(range(10))))\n",
"assert isort.ops == 54, isort.ops"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "7c0c8abc-4587-4242-b64f-32b6d016c6a4",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{5: [4, 3, 2, 1, 0],\n",
" 4: [4, 3, 2, 1, 0],\n",
" 3: [4, 3, 2, 0, 1],\n",
" 2: [4, 3, 0, 1, 2],\n",
" 1: [4, 0, 1, 2, 3],\n",
" 0: [0, 1, 2, 3, 4]}"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def build_unordered_lists(size: int):\n",
" \"\"\"\n",
" This incarnation seems to have a bug. Will try random instead. See cell below.\n",
" \"\"\"\n",
" lists = {}\n",
" for x in range(size + 1):\n",
" a = list(range(size))\n",
" a = list(reversed(a[x:])) + a[:x]\n",
" lists[size - x] = a\n",
" return lists\n",
"\n",
"build_unordered_lists(5)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "11749b90-ead1-4b93-bb45-d83a9596541b",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{5: [1, 4, 3, 2, 0],\n",
" 4: [0, 2, 4, 1, 3],\n",
" 3: [0, 1, 2, 3, 4],\n",
" 2: [0, 1, 2, 3, 4],\n",
" 1: [0, 1, 2, 3, 4],\n",
" 0: [0, 1, 2, 3, 4]}"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import random\n",
"\n",
"def build_unordered_lists(size: int):\n",
" lists = {}\n",
" for x in range(size + 1):\n",
" a = list(range(x))\n",
" b = list(range(x, size))\n",
" random.shuffle(b)\n",
" # Not a perfect way to build unordered lists but it will do. \n",
" # Not perfect because disorder is always at the back of list. \n",
" # Disorder should be spread evenly throughout the list.\n",
" lists[size - x] = a + b\n",
" return lists\n",
"\n",
"build_unordered_lists(5)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "1f651569-52ae-4fa0-80e8-31263b6860eb",
"metadata": {},
"outputs": [],
"source": [
"def generate_data():\n",
" lists = build_unordered_lists(100)\n",
" data = {}\n",
" for unordered_count, list_ in lists.items():\n",
" isort = InsertionSort()\n",
" isort.sort(list_)\n",
" data[unordered_count] = isort.ops\n",
"\n",
" return data\n",
"\n",
"ops_by_unordered_count = generate_data()"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "b7c11133-8009-455c-8407-aac9662be1f9",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<style>\n",
" .bk-notebook-logo {\n",
" display: block;\n",
" width: 20px;\n",
" height: 20px;\n",
" background-image: url(data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAAUCAYAAACNiR0NAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAABx0RVh0U29mdHdhcmUAQWRvYmUgRmlyZXdvcmtzIENTNui8sowAAAOkSURBVDiNjZRtaJVlGMd/1/08zzln5zjP1LWcU9N0NkN8m2CYjpgQYQXqSs0I84OLIC0hkEKoPtiH3gmKoiJDU7QpLgoLjLIQCpEsNJ1vqUOdO7ppbuec5+V+rj4ctwzd8IIbbi6u+8f1539dt3A78eXC7QizUF7gyV1fD1Yqg4JWz84yffhm0qkFqBogB9rM8tZdtwVsPUhWhGcFJngGeWrPzHm5oaMmkfEg1usvLFyc8jLRqDOMru7AyC8saQr7GG7f5fvDeH7Ej8CM66nIF+8yngt6HWaKh7k49Soy9nXurCi1o3qUbS3zWfrYeQDTB/Qj6kX6Ybhw4B+bOYoLKCC9H3Nu/leUTZ1JdRWkkn2ldcCamzrcf47KKXdAJllSlxAOkRgyHsGC/zRday5Qld9DyoM4/q/rUoy/CXh3jzOu3bHUVZeU+DEn8FInkPBFlu3+nW3Nw0mk6vCDiWg8CeJaxEwuHS3+z5RgY+YBR6V1Z1nxSOfoaPa4LASWxxdNp+VWTk7+4vzaou8v8PN+xo+KY2xsw6une2frhw05CTYOmQvsEhjhWjn0bmXPjpE1+kplmmkP3suftwTubK9Vq22qKmrBhpY4jvd5afdRA3wGjFAgcnTK2s4hY0/GPNIb0nErGMCRxWOOX64Z8RAC4oCXdklmEvcL8o0BfkNK4lUg9HTl+oPlQxdNo3Mg4Nv175e/1LDGzZen30MEjRUtmXSfiTVu1kK8W4txyV6BMKlbgk3lMwYCiusNy9fVfvvwMxv8Ynl6vxoByANLTWplvuj/nF9m2+PDtt1eiHPBr1oIfhCChQMBw6Aw0UulqTKZdfVvfG7VcfIqLG9bcldL/+pdWTLxLUy8Qq38heUIjh4XlzZxzQm19lLFlr8vdQ97rjZVOLf8nclzckbcD4wxXMidpX30sFd37Fv/GtwwhzhxGVAprjbg0gCAEeIgwCZyTV2Z1REEW8O4py0wsjeloKoMr6iCY6dP92H6Vw/oTyICIthibxjm/DfN9lVz8IqtqKYLUXfoKVMVQVVJOElGjrnnUt9T9wbgp8AyYKaGlqingHZU/uG2NTZSVqwHQTWkx9hxjkpWDaCg6Ckj5qebgBVbT3V3NNXMSiWSDdGV3hrtzla7J+duwPOToIg42ChPQOQjspnSlp1V+Gjdged7+8UN5CRAV7a5EdFNwCjEaBR27b3W890TE7g24NAP/mMDXRWrGoFPQI9ls/MWO2dWFAar/xcOIImbbpA3zgAAAABJRU5ErkJggg==);\n",
" }\n",
" </style>\n",
" <div>\n",
" <a href=\"https://bokeh.org\" target=\"_blank\" class=\"bk-notebook-logo\"></a>\n",
" <span id=\"a6872749-c66e-41d3-bec5-ea0966045eca\">Loading BokehJS ...</span>\n",
" </div>\n"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/javascript": [
"(function(root) {\n",
" function now() {\n",
" return new Date();\n",
" }\n",
"\n",
" const force = true;\n",
"\n",
" if (typeof root._bokeh_onload_callbacks === \"undefined\" || force === true) {\n",
" root._bokeh_onload_callbacks = [];\n",
" root._bokeh_is_loading = undefined;\n",
" }\n",
"\n",
"const JS_MIME_TYPE = 'application/javascript';\n",
" const HTML_MIME_TYPE = 'text/html';\n",
" const EXEC_MIME_TYPE = 'application/vnd.bokehjs_exec.v0+json';\n",
" const CLASS_NAME = 'output_bokeh rendered_html';\n",
"\n",
" /**\n",
" * Render data to the DOM node\n",
" */\n",
" function render(props, node) {\n",
" const script = document.createElement(\"script\");\n",
" node.appendChild(script);\n",
" }\n",
"\n",
" /**\n",
" * Handle when an output is cleared or removed\n",
" */\n",
" function handleClearOutput(event, handle) {\n",
" const cell = handle.cell;\n",
"\n",
" const id = cell.output_area._bokeh_element_id;\n",
" const server_id = cell.output_area._bokeh_server_id;\n",
" // Clean up Bokeh references\n",
" if (id != null && id in Bokeh.index) {\n",
" Bokeh.index[id].model.document.clear();\n",
" delete Bokeh.index[id];\n",
" }\n",
"\n",
" if (server_id !== undefined) {\n",
" // Clean up Bokeh references\n",
" const cmd_clean = \"from bokeh.io.state import curstate; print(curstate().uuid_to_server['\" + server_id + \"'].get_sessions()[0].document.roots[0]._id)\";\n",
" cell.notebook.kernel.execute(cmd_clean, {\n",
" iopub: {\n",
" output: function(msg) {\n",
" const id = msg.content.text.trim();\n",
" if (id in Bokeh.index) {\n",
" Bokeh.index[id].model.document.clear();\n",
" delete Bokeh.index[id];\n",
" }\n",
" }\n",
" }\n",
" });\n",
" // Destroy server and session\n",
" const cmd_destroy = \"import bokeh.io.notebook as ion; ion.destroy_server('\" + server_id + \"')\";\n",
" cell.notebook.kernel.execute(cmd_destroy);\n",
" }\n",
" }\n",
"\n",
" /**\n",
" * Handle when a new output is added\n",
" */\n",
" function handleAddOutput(event, handle) {\n",
" const output_area = handle.output_area;\n",
" const output = handle.output;\n",
"\n",
" // limit handleAddOutput to display_data with EXEC_MIME_TYPE content only\n",
" if ((output.output_type != \"display_data\") || (!Object.prototype.hasOwnProperty.call(output.data, EXEC_MIME_TYPE))) {\n",
" return\n",
" }\n",
"\n",
" const toinsert = output_area.element.find(\".\" + CLASS_NAME.split(' ')[0]);\n",
"\n",
" if (output.metadata[EXEC_MIME_TYPE][\"id\"] !== undefined) {\n",
" toinsert[toinsert.length - 1].firstChild.textContent = output.data[JS_MIME_TYPE];\n",
" // store reference to embed id on output_area\n",
" output_area._bokeh_element_id = output.metadata[EXEC_MIME_TYPE][\"id\"];\n",
" }\n",
" if (output.metadata[EXEC_MIME_TYPE][\"server_id\"] !== undefined) {\n",
" const bk_div = document.createElement(\"div\");\n",
" bk_div.innerHTML = output.data[HTML_MIME_TYPE];\n",
" const script_attrs = bk_div.children[0].attributes;\n",
" for (let i = 0; i < script_attrs.length; i++) {\n",
" toinsert[toinsert.length - 1].firstChild.setAttribute(script_attrs[i].name, script_attrs[i].value);\n",
" toinsert[toinsert.length - 1].firstChild.textContent = bk_div.children[0].textContent\n",
" }\n",
" // store reference to server id on output_area\n",
" output_area._bokeh_server_id = output.metadata[EXEC_MIME_TYPE][\"server_id\"];\n",
" }\n",
" }\n",
"\n",
" function register_renderer(events, OutputArea) {\n",
"\n",
" function append_mime(data, metadata, element) {\n",
" // create a DOM node to render to\n",
" const toinsert = this.create_output_subarea(\n",
" metadata,\n",
" CLASS_NAME,\n",
" EXEC_MIME_TYPE\n",
" );\n",
" this.keyboard_manager.register_events(toinsert);\n",
" // Render to node\n",
" const props = {data: data, metadata: metadata[EXEC_MIME_TYPE]};\n",
" render(props, toinsert[toinsert.length - 1]);\n",
" element.append(toinsert);\n",
" return toinsert\n",
" }\n",
"\n",
" /* Handle when an output is cleared or removed */\n",
" events.on('clear_output.CodeCell', handleClearOutput);\n",
" events.on('delete.Cell', handleClearOutput);\n",
"\n",
" /* Handle when a new output is added */\n",
" events.on('output_added.OutputArea', handleAddOutput);\n",
"\n",
" /**\n",
" * Register the mime type and append_mime function with output_area\n",
" */\n",
" OutputArea.prototype.register_mime_type(EXEC_MIME_TYPE, append_mime, {\n",
" /* Is output safe? */\n",
" safe: true,\n",
" /* Index of renderer in `output_area.display_order` */\n",
" index: 0\n",
" });\n",
" }\n",
"\n",
" // register the mime type if in Jupyter Notebook environment and previously unregistered\n",
" if (root.Jupyter !== undefined) {\n",
" const events = require('base/js/events');\n",
" const OutputArea = require('notebook/js/outputarea').OutputArea;\n",
"\n",
" if (OutputArea.prototype.mime_types().indexOf(EXEC_MIME_TYPE) == -1) {\n",
" register_renderer(events, OutputArea);\n",
" }\n",
" }\n",
" if (typeof (root._bokeh_timeout) === \"undefined\" || force === true) {\n",
" root._bokeh_timeout = Date.now() + 5000;\n",
" root._bokeh_failed_load = false;\n",
" }\n",
"\n",
" const NB_LOAD_WARNING = {'data': {'text/html':\n",
" \"<div style='background-color: #fdd'>\\n\"+\n",
" \"<p>\\n\"+\n",
" \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
" \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
" \"</p>\\n\"+\n",
" \"<ul>\\n\"+\n",
" \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
" \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
" \"</ul>\\n\"+\n",
" \"<code>\\n\"+\n",
" \"from bokeh.resources import INLINE\\n\"+\n",
" \"output_notebook(resources=INLINE)\\n\"+\n",
" \"</code>\\n\"+\n",
" \"</div>\"}};\n",
"\n",
" function display_loaded() {\n",
" const el = document.getElementById(\"a6872749-c66e-41d3-bec5-ea0966045eca\");\n",
" if (el != null) {\n",
" el.textContent = \"BokehJS is loading...\";\n",
" }\n",
" if (root.Bokeh !== undefined) {\n",
" if (el != null) {\n",
" el.textContent = \"BokehJS \" + root.Bokeh.version + \" successfully loaded.\";\n",
" }\n",
" } else if (Date.now() < root._bokeh_timeout) {\n",
" setTimeout(display_loaded, 100)\n",
" }\n",
" }\n",
"\n",
" function run_callbacks() {\n",
" try {\n",
" root._bokeh_onload_callbacks.forEach(function(callback) {\n",
" if (callback != null)\n",
" callback();\n",
" });\n",
" } finally {\n",
" delete root._bokeh_onload_callbacks\n",
" }\n",
" console.debug(\"Bokeh: all callbacks have finished\");\n",
" }\n",
"\n",
" function load_libs(css_urls, js_urls, callback) {\n",
" if (css_urls == null) css_urls = [];\n",
" if (js_urls == null) js_urls = [];\n",
"\n",
" root._bokeh_onload_callbacks.push(callback);\n",
" if (root._bokeh_is_loading > 0) {\n",
" console.debug(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
" return null;\n",
" }\n",
" if (js_urls == null || js_urls.length === 0) {\n",
" run_callbacks();\n",
" return null;\n",
" }\n",
" console.debug(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
" root._bokeh_is_loading = css_urls.length + js_urls.length;\n",
"\n",
" function on_load() {\n",
" root._bokeh_is_loading--;\n",
" if (root._bokeh_is_loading === 0) {\n",
" console.debug(\"Bokeh: all BokehJS libraries/stylesheets loaded\");\n",
" run_callbacks()\n",
" }\n",
" }\n",
"\n",
" function on_error(url) {\n",
" console.error(\"failed to load \" + url);\n",
" }\n",
"\n",
" for (let i = 0; i < css_urls.length; i++) {\n",
" const url = css_urls[i];\n",
" const element = document.createElement(\"link\");\n",
" element.onload = on_load;\n",
" element.onerror = on_error.bind(null, url);\n",
" element.rel = \"stylesheet\";\n",
" element.type = \"text/css\";\n",
" element.href = url;\n",
" console.debug(\"Bokeh: injecting link tag for BokehJS stylesheet: \", url);\n",
" document.body.appendChild(element);\n",
" }\n",
"\n",
" for (let i = 0; i < js_urls.length; i++) {\n",
" const url = js_urls[i];\n",
" const element = document.createElement('script');\n",
" element.onload = on_load;\n",
" element.onerror = on_error.bind(null, url);\n",
" element.async = false;\n",
" element.src = url;\n",
" console.debug(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
" document.head.appendChild(element);\n",
" }\n",
" };\n",
"\n",
" function inject_raw_css(css) {\n",
" const element = document.createElement(\"style\");\n",
" element.appendChild(document.createTextNode(css));\n",
" document.body.appendChild(element);\n",
" }\n",
"\n",
" const js_urls = [\"https://cdn.bokeh.org/bokeh/release/bokeh-3.2.1.min.js\", \"https://cdn.bokeh.org/bokeh/release/bokeh-gl-3.2.1.min.js\", \"https://cdn.bokeh.org/bokeh/release/bokeh-widgets-3.2.1.min.js\", \"https://cdn.bokeh.org/bokeh/release/bokeh-tables-3.2.1.min.js\", \"https://cdn.bokeh.org/bokeh/release/bokeh-mathjax-3.2.1.min.js\"];\n",
" const css_urls = [];\n",
"\n",
" const inline_js = [ function(Bokeh) {\n",
" Bokeh.set_log_level(\"info\");\n",
" },\n",
"function(Bokeh) {\n",
" }\n",
" ];\n",
"\n",
" function run_inline_js() {\n",
" if (root.Bokeh !== undefined || force === true) {\n",
" for (let i = 0; i < inline_js.length; i++) {\n",
" inline_js[i].call(root, root.Bokeh);\n",
" }\n",
"if (force === true) {\n",
" display_loaded();\n",
" }} else if (Date.now() < root._bokeh_timeout) {\n",
" setTimeout(run_inline_js, 100);\n",
" } else if (!root._bokeh_failed_load) {\n",
" console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
" root._bokeh_failed_load = true;\n",
" } else if (force !== true) {\n",
" const cell = $(document.getElementById(\"a6872749-c66e-41d3-bec5-ea0966045eca\")).parents('.cell').data().cell;\n",
" cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
" }\n",
" }\n",
"\n",
" if (root._bokeh_is_loading === 0) {\n",
" console.debug(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
" run_inline_js();\n",
" } else {\n",
" load_libs(css_urls, js_urls, function() {\n",
" console.debug(\"Bokeh: BokehJS plotting callback run at\", now());\n",
" run_inline_js();\n",
" });\n",
" }\n",
"}(window));"
],
"application/vnd.bokehjs_load.v0+json": "(function(root) {\n function now() {\n return new Date();\n }\n\n const force = true;\n\n if (typeof root._bokeh_onload_callbacks === \"undefined\" || force === true) {\n root._bokeh_onload_callbacks = [];\n root._bokeh_is_loading = undefined;\n }\n\n\n if (typeof (root._bokeh_timeout) === \"undefined\" || force === true) {\n root._bokeh_timeout = Date.now() + 5000;\n root._bokeh_failed_load = false;\n }\n\n const NB_LOAD_WARNING = {'data': {'text/html':\n \"<div style='background-color: #fdd'>\\n\"+\n \"<p>\\n\"+\n \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n \"</p>\\n\"+\n \"<ul>\\n\"+\n \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n \"<li>use INLINE resources instead, as so:</li>\\n\"+\n \"</ul>\\n\"+\n \"<code>\\n\"+\n \"from bokeh.resources import INLINE\\n\"+\n \"output_notebook(resources=INLINE)\\n\"+\n \"</code>\\n\"+\n \"</div>\"}};\n\n function display_loaded() {\n const el = document.getElementById(\"a6872749-c66e-41d3-bec5-ea0966045eca\");\n if (el != null) {\n el.textContent = \"BokehJS is loading...\";\n }\n if (root.Bokeh !== undefined) {\n if (el != null) {\n el.textContent = \"BokehJS \" + root.Bokeh.version + \" successfully loaded.\";\n }\n } else if (Date.now() < root._bokeh_timeout) {\n setTimeout(display_loaded, 100)\n }\n }\n\n function run_callbacks() {\n try {\n root._bokeh_onload_callbacks.forEach(function(callback) {\n if (callback != null)\n callback();\n });\n } finally {\n delete root._bokeh_onload_callbacks\n }\n console.debug(\"Bokeh: all callbacks have finished\");\n }\n\n function load_libs(css_urls, js_urls, callback) {\n if (css_urls == null) css_urls = [];\n if (js_urls == null) js_urls = [];\n\n root._bokeh_onload_callbacks.push(callback);\n if (root._bokeh_is_loading > 0) {\n console.debug(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n return null;\n }\n if (js_urls == null || js_urls.length === 0) {\n run_callbacks();\n return null;\n }\n console.debug(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n root._bokeh_is_loading = css_urls.length + js_urls.length;\n\n function on_load() {\n root._bokeh_is_loading--;\n if (root._bokeh_is_loading === 0) {\n console.debug(\"Bokeh: all BokehJS libraries/stylesheets loaded\");\n run_callbacks()\n }\n }\n\n function on_error(url) {\n console.error(\"failed to load \" + url);\n }\n\n for (let i = 0; i < css_urls.length; i++) {\n const url = css_urls[i];\n const element = document.createElement(\"link\");\n element.onload = on_load;\n element.onerror = on_error.bind(null, url);\n element.rel = \"stylesheet\";\n element.type = \"text/css\";\n element.href = url;\n console.debug(\"Bokeh: injecting link tag for BokehJS stylesheet: \", url);\n document.body.appendChild(element);\n }\n\n for (let i = 0; i < js_urls.length; i++) {\n const url = js_urls[i];\n const element = document.createElement('script');\n element.onload = on_load;\n element.onerror = on_error.bind(null, url);\n element.async = false;\n element.src = url;\n console.debug(\"Bokeh: injecting script tag for BokehJS library: \", url);\n document.head.appendChild(element);\n }\n };\n\n function inject_raw_css(css) {\n const element = document.createElement(\"style\");\n element.appendChild(document.createTextNode(css));\n document.body.appendChild(element);\n }\n\n const js_urls = [\"https://cdn.bokeh.org/bokeh/release/bokeh-3.2.1.min.js\", \"https://cdn.bokeh.org/bokeh/release/bokeh-gl-3.2.1.min.js\", \"https://cdn.bokeh.org/bokeh/release/bokeh-widgets-3.2.1.min.js\", \"https://cdn.bokeh.org/bokeh/release/bokeh-tables-3.2.1.min.js\", \"https://cdn.bokeh.org/bokeh/release/bokeh-mathjax-3.2.1.min.js\"];\n const css_urls = [];\n\n const inline_js = [ function(Bokeh) {\n Bokeh.set_log_level(\"info\");\n },\nfunction(Bokeh) {\n }\n ];\n\n function run_inline_js() {\n if (root.Bokeh !== undefined || force === true) {\n for (let i = 0; i < inline_js.length; i++) {\n inline_js[i].call(root, root.Bokeh);\n }\nif (force === true) {\n display_loaded();\n }} else if (Date.now() < root._bokeh_timeout) {\n setTimeout(run_inline_js, 100);\n } else if (!root._bokeh_failed_load) {\n console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n root._bokeh_failed_load = true;\n } else if (force !== true) {\n const cell = $(document.getElementById(\"a6872749-c66e-41d3-bec5-ea0966045eca\")).parents('.cell').data().cell;\n cell.output_area.append_execute_result(NB_LOAD_WARNING)\n }\n }\n\n if (root._bokeh_is_loading === 0) {\n console.debug(\"Bokeh: BokehJS loaded, going straight to plotting\");\n run_inline_js();\n } else {\n load_libs(css_urls, js_urls, function() {\n console.debug(\"Bokeh: BokehJS plotting callback run at\", now());\n run_inline_js();\n });\n }\n}(window));"
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"from bokeh.plotting import figure, show, output_notebook\n",
"\n",
"output_notebook()"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "9cf3ca5c-5c9c-44b9-944e-d80d8902902d",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
" <div id=\"b20cac36-88e8-4e1f-87e0-5290486fa10b\" data-root-id=\"p1001\" style=\"display: contents;\"></div>\n"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/javascript": [
"(function(root) {\n",
" function embed_document(root) {\n",
" const docs_json = {\"243ba36a-f855-4a8d-b999-49b2be6e247b\":{\"version\":\"3.2.1\",\"title\":\"Bokeh Application\",\"roots\":[{\"type\":\"object\",\"name\":\"Figure\",\"id\":\"p1001\",\"attributes\":{\"width\":900,\"x_range\":{\"type\":\"object\",\"name\":\"DataRange1d\",\"id\":\"p1002\"},\"y_range\":{\"type\":\"object\",\"name\":\"DataRange1d\",\"id\":\"p1003\"},\"x_scale\":{\"type\":\"object\",\"name\":\"LinearScale\",\"id\":\"p1011\"},\"y_scale\":{\"type\":\"object\",\"name\":\"LinearScale\",\"id\":\"p1012\"},\"title\":{\"type\":\"object\",\"name\":\"Title\",\"id\":\"p1004\",\"attributes\":{\"text\":\"Unordered Insertion Sort\"}},\"renderers\":[{\"type\":\"object\",\"name\":\"GlyphRenderer\",\"id\":\"p1036\",\"attributes\":{\"data_source\":{\"type\":\"object\",\"name\":\"ColumnDataSource\",\"id\":\"p1030\",\"attributes\":{\"selected\":{\"type\":\"object\",\"name\":\"Selection\",\"id\":\"p1031\",\"attributes\":{\"indices\":[],\"line_indices\":[]}},\"selection_policy\":{\"type\":\"object\",\"name\":\"UnionRenderers\",\"id\":\"p1032\"},\"data\":{\"type\":\"map\",\"entries\":[[\"x\",[100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]],[\"y\",[2700,2486,2419,2549,2560,2078,2219,2089,2397,2060,2101,2078,1894,1901,2037,1804,1764,1825,1859,1550,1569,1472,1557,1563,1477,1493,1436,1310,1443,1428,1163,1457,1318,1111,1163,1140,986,1066,894,939,751,878,897,849,906,915,735,762,890,709,769,678,630,669,612,536,578,519,516,509,414,511,387,455,459,398,392,316,317,275,299,261,264,315,259,251,227,240,211,226,185,187,165,154,143,155,153,153,126,132,112,107,121,112,105,104,103,99,100,99,99]]]}}},\"view\":{\"type\":\"object\",\"name\":\"CDSView\",\"id\":\"p1037\",\"attributes\":{\"filter\":{\"type\":\"object\",\"name\":\"AllIndices\",\"id\":\"p1038\"}}},\"glyph\":{\"type\":\"object\",\"name\":\"Line\",\"id\":\"p1033\",\"attributes\":{\"x\":{\"type\":\"field\",\"field\":\"x\"},\"y\":{\"type\":\"field\",\"field\":\"y\"},\"line_color\":\"#1f77b4\",\"line_width\":2}},\"nonselection_glyph\":{\"type\":\"object\",\"name\":\"Line\",\"id\":\"p1034\",\"attributes\":{\"x\":{\"type\":\"field\",\"field\":\"x\"},\"y\":{\"type\":\"field\",\"field\":\"y\"},\"line_color\":\"#1f77b4\",\"line_alpha\":0.1,\"line_width\":2}},\"muted_glyph\":{\"type\":\"object\",\"name\":\"Line\",\"id\":\"p1035\",\"attributes\":{\"x\":{\"type\":\"field\",\"field\":\"x\"},\"y\":{\"type\":\"field\",\"field\":\"y\"},\"line_color\":\"#1f77b4\",\"line_alpha\":0.2,\"line_width\":2}}}}],\"toolbar\":{\"type\":\"object\",\"name\":\"Toolbar\",\"id\":\"p1010\",\"attributes\":{\"tools\":[{\"type\":\"object\",\"name\":\"PanTool\",\"id\":\"p1023\"},{\"type\":\"object\",\"name\":\"WheelZoomTool\",\"id\":\"p1024\"},{\"type\":\"object\",\"name\":\"BoxZoomTool\",\"id\":\"p1025\",\"attributes\":{\"overlay\":{\"type\":\"object\",\"name\":\"BoxAnnotation\",\"id\":\"p1026\",\"attributes\":{\"syncable\":false,\"level\":\"overlay\",\"visible\":false,\"left_units\":\"canvas\",\"right_units\":\"canvas\",\"bottom_units\":\"canvas\",\"top_units\":\"canvas\",\"line_color\":\"black\",\"line_alpha\":1.0,\"line_width\":2,\"line_dash\":[4,4],\"fill_color\":\"lightgrey\",\"fill_alpha\":0.5}}}},{\"type\":\"object\",\"name\":\"SaveTool\",\"id\":\"p1027\"},{\"type\":\"object\",\"name\":\"ResetTool\",\"id\":\"p1028\"},{\"type\":\"object\",\"name\":\"HelpTool\",\"id\":\"p1029\"}]}},\"left\":[{\"type\":\"object\",\"name\":\"LinearAxis\",\"id\":\"p1018\",\"attributes\":{\"ticker\":{\"type\":\"object\",\"name\":\"BasicTicker\",\"id\":\"p1019\",\"attributes\":{\"mantissas\":[1,2,5]}},\"formatter\":{\"type\":\"object\",\"name\":\"BasicTickFormatter\",\"id\":\"p1020\"},\"axis_label\":\"Opertions To Sort\",\"major_label_policy\":{\"type\":\"object\",\"name\":\"AllLabels\",\"id\":\"p1021\"}}}],\"below\":[{\"type\":\"object\",\"name\":\"LinearAxis\",\"id\":\"p1013\",\"attributes\":{\"ticker\":{\"type\":\"object\",\"name\":\"BasicTicker\",\"id\":\"p1014\",\"attributes\":{\"mantissas\":[1,2,5]}},\"formatter\":{\"type\":\"object\",\"name\":\"BasicTickFormatter\",\"id\":\"p1015\"},\"axis_label\":\"Unorderedness\",\"major_label_policy\":{\"type\":\"object\",\"name\":\"AllLabels\",\"id\":\"p1016\"}}}],\"center\":[{\"type\":\"object\",\"name\":\"Grid\",\"id\":\"p1017\",\"attributes\":{\"axis\":{\"id\":\"p1013\"}}},{\"type\":\"object\",\"name\":\"Grid\",\"id\":\"p1022\",\"attributes\":{\"dimension\":1,\"axis\":{\"id\":\"p1018\"}}}]}}]}};\n",
" const render_items = [{\"docid\":\"243ba36a-f855-4a8d-b999-49b2be6e247b\",\"roots\":{\"p1001\":\"b20cac36-88e8-4e1f-87e0-5290486fa10b\"},\"root_ids\":[\"p1001\"]}];\n",
" root.Bokeh.embed.embed_items_notebook(docs_json, render_items);\n",
" }\n",
" if (root.Bokeh !== undefined) {\n",
" embed_document(root);\n",
" } else {\n",
" let attempts = 0;\n",
" const timer = setInterval(function(root) {\n",
" if (root.Bokeh !== undefined) {\n",
" clearInterval(timer);\n",
" embed_document(root);\n",
" } else {\n",
" attempts++;\n",
" if (attempts > 100) {\n",
" clearInterval(timer);\n",
" console.log(\"Bokeh: ERROR: Unable to run BokehJS code because BokehJS library is missing\");\n",
" }\n",
" }\n",
" }, 10, root)\n",
" }\n",
"})(window);"
],
"application/vnd.bokehjs_exec.v0+json": ""
},
"metadata": {
"application/vnd.bokehjs_exec.v0+json": {
"id": "p1001"
}
},
"output_type": "display_data"
}
],
"source": [
"p = figure(\n",
" title=\"Unordered Insertion Sort\",\n",
" x_axis_label='Unorderedness',\n",
" y_axis_label='Opertions To Sort',\n",
" width=900,\n",
")\n",
"\n",
"x = []\n",
"y = []\n",
"for c, ops in ops_by_unordered_count.items():\n",
" x.append(c)\n",
" y.append(ops)\n",
"\n",
"p.line(x, y, line_width=2,)\n",
"\n",
"show(p)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.4"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
@logston
Copy link
Author

logston commented Sep 2, 2023

bokeh_plot

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment