File size: 5,211 Bytes
e2a4cd0 30d5137 c9da650 fa851a9 0d0870f c9da650 30d5137 e2a4cd0 910ecce e2a4cd0 c9da650 e2a4cd0 9401684 e2a4cd0 c9da650 e2a4cd0 910ecce e2a4cd0 9401684 e2a4cd0 0d0870f e2a4cd0 c9da650 e2a4cd0 c9da650 e2a4cd0 910ecce e2a4cd0 c9da650 e2a4cd0 c9da650 e2a4cd0 0d0870f e2a4cd0 0d0870f e2a4cd0 0d0870f e2a4cd0 0d0870f e2a4cd0 0d0870f e2a4cd0 c9da650 e2a4cd0 0d0870f e2a4cd0 c9da650 e2a4cd0 c9da650 e2a4cd0 c9da650 e2a4cd0 c9da650 e2a4cd0 c9da650 e2a4cd0 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 |
{
"cells": [
{
"cell_type": "raw",
"id": "f8c678c7-180b-418b-8f39-08b9f8a5aa32",
"metadata": {},
"source": [
"---\n",
"title: Visualising sorting of numbers in merge sort\n",
"description: using recursion\n",
"show-code: False\n",
"params: \n",
" texts:\n",
" input: text\n",
" label: Enter numbers to sort separated by comma\n",
" value: 5,2,19,3,100,6\n",
"---"
]
},
{
"cell_type": "code",
"execution_count": 63,
"id": "77d54c3d-3582-4398-be8c-346baba005e4",
"metadata": {},
"outputs": [],
"source": [
"import mercury as mr"
]
},
{
"cell_type": "code",
"execution_count": 66,
"id": "207ffa0d-f9fa-4753-966d-40ee128dedea",
"metadata": {},
"outputs": [],
"source": [
"#app = mr.App(title=\"Visualising sorting of numbers using recursion in merge sort\", description=\"using merge sort\")\n",
"texts = '5,2,19,3,100,6'"
]
},
{
"cell_type": "code",
"execution_count": 65,
"id": "afd50440-2a60-4e9e-a2dc-783a996ddef7",
"metadata": {},
"outputs": [],
"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": 67,
"id": "81f4c406-8b10-423b-947a-ab5c09cd21fe",
"metadata": {},
"outputs": [],
"source": [
"texts = (texts).split(',')\n",
"texts = [int(t) for t in texts]"
]
},
{
"cell_type": "code",
"execution_count": 68,
"id": "cb2bf025-f51b-4d1f-a2df-6848d9088e18",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"sorting [5, 2, 19, 3, 100, 6]\n",
" /\n",
" [5, 2, 19]\n",
" /\n",
" [5]\n",
" \\\n",
" [2, 19]\n",
" /\n",
" [2]\n",
" \\\n",
" [19]\n",
"merging [2] and [19]\n",
"merging [5] and [2, 19]\n",
" \\\n",
" [3, 100, 6]\n",
" /\n",
" [3]\n",
" \\\n",
" [100, 6]\n",
" /\n",
" [100]\n",
" \\\n",
" [6]\n",
"merging [100] and [6]\n",
"merging [3] and [6, 100]\n",
"merging [2, 5, 19] and [3, 6, 100]\n"
]
},
{
"data": {
"text/plain": [
"[2, 3, 5, 6, 19, 100]"
]
},
"execution_count": 68,
"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
}
|