{
"cells": [
{
"cell_type": "raw",
"id": "f8c678c7-180b-418b-8f39-08b9f8a5aa32",
"metadata": {},
"source": [
"---\n",
"title: Visualising sorting of numbers using recursion in merge sort\n",
"author: damdkago\n",
"description: first viz\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "77d54c3d-3582-4398-be8c-346baba005e4",
"metadata": {},
"outputs": [],
"source": [
"import mercury as mr"
]
},
{
"cell_type": "code",
"execution_count": 48,
"id": "207ffa0d-f9fa-4753-966d-40ee128dedea",
"metadata": {},
"outputs": [
{
"data": {
"application/mercury+json": "{\n \"widget\": \"App\",\n \"title\": \"Visualising sorting of numbers using recursion in merge sort\",\n \"description\": \"using merge sort\",\n \"show_code\": false,\n \"show_prompt\": false,\n \"output\": \"app\",\n \"schedule\": \"\",\n \"notify\": \"{}\",\n \"continuous_update\": true,\n \"static_notebook\": false,\n \"show_sidebar\": true,\n \"full_screen\": true,\n \"allow_download\": true,\n \"stop_on_error\": false,\n \"model_id\": \"mercury-app\",\n \"code_uid\": \"App.0.40.25.1-rande8866b82\"\n}",
"text/html": [
"Mercury Application
This output won't appear in the web app."
],
"text/plain": [
"mercury.App"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"app = mr.App(title=\"Visualising sorting of numbers using recursion in merge sort\", description=\"using merge sort\")"
]
},
{
"cell_type": "code",
"execution_count": 49,
"id": "afd50440-2a60-4e9e-a2dc-783a996ddef7",
"metadata": {},
"outputs": [
{
"data": {
"application/mercury+json": "{\n \"widget\": \"Text\",\n \"value\": \"5,2,19,3,6,10\",\n \"rows\": 1,\n \"label\": \"Enter numbers to sort separated by comma\",\n \"model_id\": \"b9aff4eac9ad48d9bc222888b0aea207\",\n \"code_uid\": \"Text.0.40.15.1.w-0-rand7083c11e\",\n \"url_key\": \"w-0\",\n \"disabled\": false,\n \"hidden\": false\n}",
"application/vnd.jupyter.widget-view+json": {
"model_id": "b9aff4eac9ad48d9bc222888b0aea207",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"mercury.Text"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"texts = [mr.Text(label=f\"Enter numbers to sort separated by comma\", value=f\"5,2,19,3,6,10\", url_key=f\"w-{0}\")]\n",
"#texts = []\n",
"#for i in range(5):\n",
"# texts += [mr.Text(label=f\"Widget {i}\", value=f\"{i}\", url_key=f\"w-{i}\")]"
]
},
{
"cell_type": "code",
"execution_count": 43,
"id": "81f4c406-8b10-423b-947a-ab5c09cd21fe",
"metadata": {},
"outputs": [],
"source": [
"#texts = [int(t.value) for t in texts]\n",
"texts = (texts[0].value).split(',')\n",
"texts = [int(t) for t in texts]"
]
},
{
"cell_type": "code",
"execution_count": 45,
"id": "cb2bf025-f51b-4d1f-a2df-6848d9088e18",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"sorting [2, 3, 5, 6, 10, 19]\n",
" /\n",
" [2, 3, 5]\n",
" /\n",
" [2]\n",
" \\\n",
" [3, 5]\n",
" /\n",
" [3]\n",
" \\\n",
" [5]\n",
"merging [3] and [5]\n",
"merging [2] and [3, 5]\n",
" \\\n",
" [6, 10, 19]\n",
" /\n",
" [6]\n",
" \\\n",
" [10, 19]\n",
" /\n",
" [10]\n",
" \\\n",
" [19]\n",
"merging [10] and [19]\n",
"merging [6] and [10, 19]\n",
"merging [2, 3, 5] and [6, 10, 19]\n"
]
},
{
"data": {
"text/plain": [
"[2, 3, 5, 6, 10, 19]"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# implement merge sort algo for sorting a list x using recursion\n",
"\n",
"# merge 2 lists and sort the values by taking min value for first element in both list\n",
"# and remove that element from the list which has min value\n",
"# because both lists already sorted, doing this way wil give combined 1 list which is sorted\n",
"def merge(left, right, x):\n",
" print('merging', left, 'and', right)\n",
" i = j = k = 0\n",
" while i < len(left) and j < len(right):\n",
" if left[i] < right[j]:\n",
" x[k] = left[i]\n",
" i = i + 1\n",
" else:\n",
" x[k] = right[j]\n",
" j = j + 1\n",
" k = k + 1\n",
"\n",
" while i < len(left):\n",
" x[k] = left[i]\n",
" i = i + 1\n",
" k = k + 1\n",
"\n",
" while j < len(right):\n",
" x[k] = right[j]\n",
" j = j + 1\n",
" k = k + 1\n",
"\n",
" return x\n",
"\n",
"# actual function that sorts list x that calls itself using recursion\n",
"def sortarray(x):\n",
"\n",
" # counter increment by 1 everytime function sortarray is called\n",
" # used for increasing spacing during printing of \\,/ and list\n",
" sortarray.counter +=1\n",
"\n",
" if len(x) > 1:\n",
" l = int(len(x)/2)\n",
" left = x[:l]\n",
" right = x[l:]\n",
"\n",
" # a / is printed when list is split to left half\n",
" print(' '* (sortarray.counter), '/')\n",
" print(' '* (sortarray.counter - 2), left)\n",
" sortarray(left)\n",
"\n",
" # a / is printed when list is split to right half\n",
" print(' '* (sortarray.counter + 5), '\\\\')\n",
" print(' '* (sortarray.counter + 5 - 1), right)\n",
" sortarray(right)\n",
"\n",
" merge(left, right, x)\n",
"\n",
" return x\n",
"\n",
"sortarray.counter = 0\n",
"print('sorting ', texts)\n",
"sortarray(texts)"
]
}
],
"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.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 5
}