ICan'tBelieveItCanSort

2 files changed, 63 insertions, 0 deletions

diff --git a/content/posts/i-cant-believe-it-can-sort.md b/content/posts/i-cant-believe-it-can-sort.md
new file mode 100644
index 0000000..d86bbd1
--- /dev/null
+++ b/content/posts/i-cant-believe-it-can-sort.md
@@ -0,0 +1,27 @@
+---
+title: "ICan'tBelieveItCanSort!"
+date: 2024-11-04T12:20:49-05:00
+description: "Explaining a surprising sorting algorithm"
+type: "post"
+tags: ["algorithms"]
+---
+
+
+I recently learned a new sorting algorithm called the ICan'tBelieveItCanSort algorithm:
+
+```cpp
+for (int i = 0; i < n; i++)
+    for (int j = 0; j < n; j++)
+        if (A[i] < A[j])
+            swap(A[i], A[j]);
+```
+
+Wait what? The more I think about this, the more I think it shouldn't work. This sorts in increasing order?
+
+But it does actually work, and I think watching a visualization is the best way to convince yourself.
+
+{{< sort >}}
+
+I still can't believe it can sort! But this algorithm does have a certain aesthetic elegance so I definitely encourage you to use it in all your programs to troll the next person who reads your code!
+
+You can read more about this algorithm and a formal proof of it in [this arXiv paper](https://arxiv.org/abs/2110.01111).
diff --git a/layouts/shortcodes/sort.html b/layouts/shortcodes/sort.html
new file mode 100644
index 0000000..a748bd1
--- /dev/null
+++ b/layouts/shortcodes/sort.html
@@ -0,0 +1,36 @@
+<button onclick="run()">Run visualization</button>
+<pre id="visualization">
+</pre>
+<script>
+let running = false
+
+function render(n, A, i, j) {
+	let line1 = Array(n).fill(" ")
+	line1[j] = "j"
+	line1[i] = "i"
+	document.getElementById("visualization").innerHTML = line1.join(" ") + "\n" + A.join(" ")
+}
+
+async function run() {
+	if (running) return
+	running = true
+
+	let n = 10
+	let A = Array(n).fill().map(() => Math.floor(Math.random() * 10))
+	for (let i = 0; i < n; i++) {
+		for (let j = 0; j < n; j++) {
+			render(n, A, i, j)
+			await new Promise(resolve => setTimeout(resolve, 500))
+			if (A[i] < A[j]) {
+				let tmp = A[i]
+				A[i] = A[j]
+				A[j] = tmp
+				render(n, A, i, j)
+				await new Promise(resolve => setTimeout(resolve, 500))
+			}
+		}
+	}
+
+	running = false
+}
+</script>