如何可視化「排序演算法」

簡評：國外有個開發者洗澡時總會產生一些奇奇妙妙的想法，比如他將排序演算法進行可視化，並用聲音來輔助體現 ~

這是排序演算法可視化後錄製的視頻，確實聽起來很整齊！

【Tone of Sorting?—?Quick Sort with 100 Elements】

我們不能把排序演算法寫成同步代碼，瀏覽器容易殺死這個進程。

非同步演算法

所以想到的解決方案是讓它們非同步。例如，冒泡排序可以像下面的代碼片段那樣實現：

function test(array, i, j) {n return array[i] - array[j];n}nfunction swap(array, i, j) {n var a = array[i];n var b = array[j];narray[i] = b;n array[j] = a;n}nfunction bubbleSort(callback, array) {n setTimeout(function step(i, j, length) {n if (test(array, j, j + 1) > 0) {n swap(array, j, j + 1);n }nif (j > length) {n window.setTimeout(step, 0, ++i, 0, n);n } else if (i < length) {n window.setTimeout(step, 0, i, ++j, n); n } else {n callback(array);n }n }, 0, 0, 0, array.length);n}n

這個方法有一個問題，它直接將迭代與主循環聯繫起來，因此每個區間執行多個步驟會變得更加繁瑣。

同步演算法

比較好的解決方案是使演算法同步。但由於主線程不能被殺死，我們可以通過將排序演算法移動到工作線程並將消息發送回主線程來解決此問題。

function test(array, i, j) {n self.postMessage([test, i, j]);nreturn array[i] - array[j];n}nfunction swap(array, i, j) {n self.postMessage([swap, i, j]);nvar temp = array[i];n array[i] = array[j];n array[j] = temp;n}nfunction bubbleSort(array) {n var length = array.length;n for (var i = 0; i < length; i++) {n var sorted = true;n for (var j = 0; j < (length - i) - 1; j++) {n if (test(a, j + 1, j) < 0) {n sorted = false;n swap(a, j, j + 1);n }n }nif (sorted) {n return;n }n }n}nself.onmessage = function(event) {n var fn = eval(event.data[0]);n fn(event.data[1], event.data[2]);n};n

然後通過使主線程將消息排隊，可以以任何順序或速率輕鬆地讀取它們。在請求動畫幀回調中播放音調，動畫文檔變得直截了當。

var queue = [];nvar worker = new Worker(quicksort.js);nworker.postMessage([quickSort, /* ... */]);nworker.onmessage = function(event) {n queue.push(event.data);n};nvar then = null;nrequestAnimationFrame(function tick(now) {n var delta = now - then;n if (delta < 1000) {n return window.requestAnimationFrame(tick, now);n }n n // ...n n then = now;n requestAnimationFrame(tick, now);n}, window);n

這是排序的目前的計算方式，但仍然有問題，會凍結選項卡。

此外，還有一種叫做「Bogo Sort」的有點特別的演算法，也叫做 Stupid Sort 或者 Monkey Sort，可以試試。

協同演算法

演算法可以根據需要進行部分評估。JavaScript 支持生成器的協同。

例如，冒泡排序變成了一個如下所示的生成器：

function test(array, i, j) {n return array[i] - array[j];n}nfunction swap(array, i, j) {n var temp = array[i];n array[i] = array[j];n array[j] = temp;n}nfunction* bubbleSort(array) {n var length = array.length;n for (var i = 0; i < length; i++) {n var sorted = true;n for (var j = 0; j < (length - i) - 1; j++) {n yield [test, j + 1, j];nif (test(a, j + 1, j) > 0) {n sorted = false;n swap(a, j, j + 1);nyield [swap, j, j + 1];n }n }nif (sorted) {n return;n }n }n}n

從非同步回調（如 requestAnimationFrame）中一次只調用幾個步驟意味著它是非同步的，因為它是按需生成的，所以像「Bogo Sort」這樣的演算法將起作用。

var array = new Array(100);nvar algorithm = bubbleSort(array);nrequestAnimationFrame(function tick(now) {n // ...n var step = algorithm.next();n // ...n}, window);n

試試看

你可以嘗試在這裡排序音調，還有一個 GitHub Repository。如果你正在尋找關於該主題的書籍，可以查閱「演算法簡介」。

原文鏈接：How I Visualized Sorting Algorithms and Brought Them to Life with Sound

推薦閱讀：Python 的數學仙境之旅

極光日報，極光開發者 的 Side Project，歡迎關注。

推薦閱讀：