-
Notifications
You must be signed in to change notification settings - Fork 3
/
bubble.html
188 lines (172 loc) · 6.2 KB
/
bubble.html
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
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<!-- Bootstrap core CSS -->
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" integrity="sha384-1q8mTJOASx8j1Au+a5WDVnPi2lkFfwwEAa8hDDdjZlpLegxhjVME1fgjWPGmkzs7" crossorigin="anonymous">
<!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
<link href="ie10-viewport-bug-workaround.css" rel="stylesheet">
<!-- Custom styles for this template -->
<link href="scrolling-nav.css" rel="stylesheet">
<link href="https://bootswatch.com/flatly/bootstrap.min.css" rel="stylesheet">
<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
</head>
<body id="page-top" data-target=".navbar-fixed-top">
<nav class="navbar navbar-inverse navbar-fixed-top top-nav-collapse">
<div class="container">
<div class="navbar-header page-scroll">
<button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar" aria-expanded="false" aria-controls="navbar">
<span class="sr-only">Toggle navigation</span>
</button>
<a class="navbar-brand page-scroll" href="index.html">Quine8</a>
<a class="navbar-brand page-scroll" href="pong.html">Previous</a>
<a class="navbar-brand page-scroll" href="divisor.html">Next</a>
</div>
</div>
</nav>
<section style="margin-top: 5em; max-width: 50em;">
<h1>Sorting and Arrays with Q8</h1>
<p>To introduce a little more complexity and explore some of the cooler features of Q8, we are going
to write a simple sort. Bubblesort! It may be slow, but it's easy to understand, and easy enough to implement.</p>
<h3>Bubblesort</h3>
<a href="https://en.wikipedia.org/wiki/Bubble_sort">
<div class="img_container">
<img class="img_link" style="width: 30%;" src="https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif">
</div>
</a>
<p>In bubblesort, each element is compared with its neighbor and swapped if necessary. Unfortunately, it can't always sort
the whole array in one pass. It must keep running until all of the elements have slowly made their way to their correct
positions. Worst-case, the elements are sorted, but in the opposite direction of the desired sort, it takes the length of the array, n, times the
the number of passes necessary to fix it, in this case, equal to the length of the array, n. That leaves the runtime at
a miserable worst-case of n<sup>2</sup>. With a larger array, this can get really ridiculous.</p>
<pre><code class="language-none">Main Loop - With Swap: 36 tiles
Main Loop - Without Swap: 31 tiles
Main Loop - Average: 33.5 tiles
Restart Loop: 24 tiles
n, our array length for this example is 5
Main Loop gets called once per element, so n times per sort iteration
Restart Loop gets called once per array walk, so average of n/2 times
Main Loop average * n * Restart Loop * (n/2) = ~10,050 tiles
Main Loop worst-case * n * Restart Loop * n = ~21,600 tiles
Main Loop best-case * n * Restart Loop * 1 = ~3,720 tiles (Loop is already sorted)</code></pre>
<p>Assuming each tile takes 1 second, best case runs in 1 hour, 2 minutes, and worst case runs in 6 hours.
n<sup>2</sup> time is not ideal. Bubblesort is more useful as a teaching tool than as a sort to use
for practical applications.</p>
</section>
<section>
<div class="multi_code_container">
<div class="c_and_img">
<div>
<h3>C-like Program</h3>
<pre><code class="language-c; line-numbers">int len = 5;
int array[len] = {5, 4, 3, 2, 1};
bool swapped = true;
while (swapped) {
swapped = false;
for (int i = 0; i < len - 1; i++) {
int j = i + 1;
if (array[j] > array[i]) {
swap(array, i, j);
swapped = true;
}
}
}</code></pre>
</div>
<div>
<h3>Bytecode Program</h3>
<a href="q8.html#AwRgRiwExlwKwGNIDZF3MBjQEN5aGiIDMIAHCIgGbUi5xFPNFVbxhZWRToITAUsYAE5CSMvhbSZsufKaYK3UABZ+WEgNWwQKEAFMA7FiMDyw8D11QQJfql1TxpKHXzUFX7z9/yC6vYYfkyquMC4kCHRMbFx8bEkiEA==">
<img class="img_link" style="width: 90%; margin-left: 1.5em;" src="bubble.gif">
</a>
</div>
</div>
<div>
<h3>Assembly Program</h3>
<pre><code class="language-none; line-numbers">; Copy the starting indices and array length for later
>0
start:
LOAD A c_i ; index: i
LOAD B c_j ; index + 1: j
STORE A i ; use as initial i
STORE B j ; use as initial j
LOAD A c_len ; len - 1
STORE A len ; use as initial len
JMP main_loop ; goto main loop
>16
is_sorted:
LOAD A has_swapped ; check if the swapped bool changed
ISZERO A
JZ exit ; goto exit
JMP restart_loop ; goto restart loop
>32
restart_loop:
LOAD A len ; grab len - 1
STORE A c_len ; use as new remaining distance
LOAD A i ; grab initial i
LOAD B j ; grab initial j
STORE A c_i ; use as new i
STORE B c_j ; use as new j
SET A 0 ; swapped = false
STORE A has_swapped ; use as new swapped
JMP main_loop ; goto main loop
>80
main_loop:
LOAD A c_len ; grab remaining distance to end of list
ISZERO A ; Are we all the way through the list?
JZ is_sorted ; goto is sorted?
DEC A ; remaining distance--
STORE A c_len ; store new distance
LOADI A c_i ; load i
LOADI B c_j ; load j
CMP A B ; compare i and j
JG swap_val ; goto swap values if necessary
>95
store_reg:
STOREI A 177 ; store A at grid[i]
STOREI B 178 ; store B at grid[j]
LOAD A c_i ; load i
LOAD B c_j ; load j
INC A ; i++
INC B ; j++
STORE A c_i ; update i
STORE B c_j ; update j
JMP main_loop ; goto main loop
>112
swap_val:
STORE A has_swapped ; swapped = true
SWAP A B
JMP store_reg ; goto store registers
; 255 - EXIT
>255
exit:
HALT
; DATA
>160
$5
$4
$3
$2
$1
>176
c_len: $4
c_i: $160
c_j: $161
>192
len: $0
i: $0
j: $0
has_swapped: $0
</code></pre>
</div>
</div>
</section>
<link rel="stylesheet" href="prism.css">
<link href="tutorial_style.css" rel="stylesheet">
<script src="prism.js"></script>
</body>
<footer style="margin-top: 4em; padding-bottom: 4em; background-color: #555"></footer>
</html>