Skip to content

Commit a6e6e85

Browse files
KaaraOpCodeKaaraOpCode
committed
unit 24-26-29-1
1 parent f192d7e commit a6e6e85

File tree

3 files changed

+220
-4
lines changed

3 files changed

+220
-4
lines changed

‎drakon/quicksort.drakon‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
{
2+
"items": {
3+
"1": {
4+
"type": "end"
5+
},
6+
"2": {
7+
"type": "branch",
8+
"branchId": 0,
9+
"one": "1",
10+
"content": ""
11+
}
12+
},
13+
"type": "drakon"
14+
}

‎unit_twenty_nine.ipynb‎

Lines changed: 118 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,12 +8,112 @@
88
"Quick Sort"
99
]
1010
},
11+
{
12+
"cell_type": "markdown",
13+
"metadata": {},
14+
"source": [
15+
"Quick sort with pivot as first index"
16+
]
17+
},
1118
{
1219
"cell_type": "code",
13-
"execution_count": null,
20+
"execution_count": 35,
1421
"metadata": {},
15-
"outputs": [],
16-
"source": []
22+
"outputs": [
23+
{
24+
"name": "stdout",
25+
"output_type": "stream",
26+
"text": [
27+
"[15, 10, 12, 20, 25, 13, 22]\n",
28+
"[15, 10, 12, 13, 25, 20, 22]\n",
29+
"[13, 10, 12, 15, 25, 20, 22]\n",
30+
"[12, 10, 13, 15, 25, 20, 22]\n",
31+
"[10, 12, 13, 15, 25, 20, 22]\n",
32+
"[10, 12, 13, 15, 22, 20, 25]\n",
33+
"[10, 12, 13, 15, 20, 22, 25]\n"
34+
]
35+
}
36+
],
37+
"source": [
38+
"def quicksort1(S, low, high):\n",
39+
" if low < high:\n",
40+
" pivotpoint = partition1(S, low, high)\n",
41+
" quicksort1(S, low, pivotpoint - 1)\n",
42+
" quicksort1(S, pivotpoint + 1, high)\n",
43+
"\n",
44+
"def partition1(S, low, high):\n",
45+
" pivot = S[low]\n",
46+
" left, right = low + 1, high\n",
47+
" while left <= right:\n",
48+
" print(S)\n",
49+
" while left <= right and S[left] <= pivot:\n",
50+
" left += 1\n",
51+
" while left <= right and S[right] >= pivot:\n",
52+
" right -= 1\n",
53+
" if left < right:\n",
54+
" S[left], S[right] = S[right], S[left]\n",
55+
" S[low], S[right] = S[right], S[low]\n",
56+
" return right\n",
57+
"\n",
58+
"S = [15, 10, 12, 20, 25, 13, 22]\n",
59+
"quicksort1(S, 0, len(S) - 1)\n",
60+
"print(S)\n"
61+
]
62+
},
63+
{
64+
"cell_type": "markdown",
65+
"metadata": {},
66+
"source": [
67+
"Quiz sort with randomized pivot"
68+
]
69+
},
70+
{
71+
"cell_type": "code",
72+
"execution_count": 32,
73+
"metadata": {},
74+
"outputs": [
75+
{
76+
"name": "stdout",
77+
"output_type": "stream",
78+
"text": [
79+
"[25, 22, 20, 15, 13, 12, 10] 0 6 pivot = 25\n",
80+
"[10, 22, 20, 15, 13, 12, 25] 0 5 pivot = 10\n",
81+
"[10, 22, 20, 15, 13, 12, 25] 1 5 pivot = 22\n",
82+
"[10, 12, 20, 15, 13, 22, 25] 1 4 pivot = 12\n",
83+
"[10, 12, 20, 15, 13, 22, 25] 2 4 pivot = 20\n",
84+
"[10, 12, 13, 15, 20, 22, 25] 2 3 pivot = 13\n",
85+
"[10, 12, 13, 15, 20, 22, 25]\n"
86+
]
87+
}
88+
],
89+
"source": [
90+
"from random import randint\n",
91+
"\n",
92+
"def partition2(S, low, high):\n",
93+
" rand = randint(low, high)\n",
94+
" S[low], S[rand], S[rand], S[low]\n",
95+
" pivot, left, right = S[low], low, high\n",
96+
" print(S, left, right, \"pivot = \", pivot)\n",
97+
" while left < right:\n",
98+
" while left < high and S[left] <= pivot:\n",
99+
" left += 1\n",
100+
" while right > low and pivot <= S[right]:\n",
101+
" right -= 1\n",
102+
" if left < right:\n",
103+
" S[left], S[right] = S[right], S[right]\n",
104+
" S[low], S[right] = S[right], S[low]\n",
105+
" return right\n",
106+
"\n",
107+
"def quicksort2(S, low, high):\n",
108+
" if low < high:\n",
109+
" pivotpoint = partition2(S, low, high)\n",
110+
" quicksort2(S, low, pivotpoint - 1)\n",
111+
" quicksort2(S, pivotpoint + 1, high)\n",
112+
" \n",
113+
"S = [25, 22, 20, 15, 13, 12, 10]\n",
114+
"quicksort2(S, 0, len(S) - 1)\n",
115+
"print(S)\n"
116+
]
17117
},
18118
{
19119
"cell_type": "code",
@@ -24,8 +124,22 @@
24124
}
25125
],
26126
"metadata": {
127+
"kernelspec": {
128+
"display_name": "Python 3",
129+
"language": "python",
130+
"name": "python3"
131+
},
27132
"language_info": {
28-
"name": "python"
133+
"codemirror_mode": {
134+
"name": "ipython",
135+
"version": 3
136+
},
137+
"file_extension": ".py",
138+
"mimetype": "text/x-python",
139+
"name": "python",
140+
"nbconvert_exporter": "python",
141+
"pygments_lexer": "ipython3",
142+
"version": "3.12.3"
29143
}
30144
},
31145
"nbformat": 4,

‎unit_twenty_ninee.ipynb‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
{
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {},
6+
"source": [
7+
"Pair Programming"
8+
]
9+
},
10+
{
11+
"cell_type": "code",
12+
"execution_count": 3,
13+
"metadata": {},
14+
"outputs": [
15+
{
16+
"name": "stdout",
17+
"output_type": "stream",
18+
"text": [
19+
"Merged into: [1, 2, 3, 3, 4, 5, 7, 9]\n"
20+
]
21+
}
22+
],
23+
"source": [
24+
"def merge_sort(lists):\n",
25+
" # Base case: if there's only one list, return it\n",
26+
" if len(lists) == 1:\n",
27+
" return lists[0]\n",
28+
" \n",
29+
" # Recursive case: split the list of lists into two halves and merge sort each half\n",
30+
" mid = len(lists) // 2\n",
31+
" left = merge_sort(lists[:mid])\n",
32+
" right = merge_sort(lists[mid:])\n",
33+
" \n",
34+
" # Merge the two sorted halves\n",
35+
" return merge(left, right)\n",
36+
"\n",
37+
"def merge(list1, list2):\n",
38+
" merged_list = []\n",
39+
" i = j = 0\n",
40+
" \n",
41+
" # Merge the two lists by comparing their elements\n",
42+
" while i < len(list1) and j < len(list2):\n",
43+
" if list1[i] < list2[j]:\n",
44+
" merged_list.append(list1[i])\n",
45+
" i += 1\n",
46+
" else:\n",
47+
" merged_list.append(list2[j])\n",
48+
" j += 1\n",
49+
" \n",
50+
" # Append any remaining elements from list1 or list2\n",
51+
" merged_list.extend(list1[i:])\n",
52+
" merged_list.extend(list2[j:])\n",
53+
" \n",
54+
" return merged_list\n",
55+
"\n",
56+
"N = int(input(\"Input the number of lists: \"))\n",
57+
"list_of_nums = []\n",
58+
"for i in range(N):\n",
59+
" nums = list(map(int, input(\"Input a list of numbers: \").split()))\n",
60+
" list_of_nums.append(nums)\n",
61+
"\n",
62+
"sorted_list = merge_sort(list_of_nums)\n",
63+
"print(\"Merged into:\", sorted_list)\n"
64+
]
65+
}
66+
],
67+
"metadata": {
68+
"kernelspec": {
69+
"display_name": "Python 3",
70+
"language": "python",
71+
"name": "python3"
72+
},
73+
"language_info": {
74+
"codemirror_mode": {
75+
"name": "ipython",
76+
"version": 3
77+
},
78+
"file_extension": ".py",
79+
"mimetype": "text/x-python",
80+
"name": "python",
81+
"nbconvert_exporter": "python",
82+
"pygments_lexer": "ipython3",
83+
"version": "3.12.3"
84+
}
85+
},
86+
"nbformat": 4,
87+
"nbformat_minor": 2
88+
}

0 commit comments

Comments
 (0)