ソートアルゴリズムの可聴化
Sorting Algorithm Animationsなどのサイトでは、ソートアルゴリズムの可視化の例を見ることができる。今回は可視化に倣ってソートアルゴリズムを可聴化した。聴覚化すると、情報を分かりやすく提示するという方向から外れるけど。
ソートする対象は50から90までの整数をランダムに並べた列。可聴化の方法は、整数をMIDIノート番号とみなして、ソートアルゴリズムが各時点でポイントしている位置にある、MIDIノート番号の音高の音を鳴らすようにした。ChucKのプログラムはいつもより長くなったから最後に載せる。
録音したもの。元の整数列は全部同じで、サイズ（整数の数）は30。
バブルソート 
選択ソート
挿入ソート
シェルソート
クイックソート
マージソート
ヒープソート
拡張としては、
が考えられる。あとは、可視化も加えて動作中に楽譜を表示しても面白いかも。
「続きを読む」以降が、ChucKのプログラム（＋比較グラフ）。
30 => int N;
int data[N];
.1::second => dur T;
TriOsc s => ADSR e => JCRev r => dac;
e.set(.2*T, .4*T, 0, 0*T);
.2 => e.gain;
.1 => r.mix;
fun void noteOn(int note) {
Std.mtof(note) => s.freq;
1 => e.keyOn;
T => now;
}
fun void init() {
//9 => Std.srand;
for (int i; i < N; i++) {
Std.rand2(50, 90) => data[i];
}
}
fun void swap(int i, int j) {
data[i] => int t;
data[j] => data[i];
t => data[j];
}
init();
// ここで可聴化したいソートアルゴリズムを呼ぶ
// なんたらSort();
// 以降が各ソートアルゴリズムの実装
/*** バブルソート ***/
fun void bubbleSort() {
for (int i; i < N-1; i++) {
for (N-1 => int j; j > i; j--) {
noteOn(data[j]);
if (data[j] < data[j-1]) {
swap(j, j-1);
}
}
}
}
/*** 選択ソート ***/
fun void selectionSort() {
int min;
for (int i; i < N-1; i++) {
i => min;
for (i+1 => int j; j < N; j++) {
noteOn(data[j]);
if (data[j] < data[min]) {
j => min;
}
}
swap(i, min);
}
}
/*** 挿入ソート ***/
fun void insertionSort() {
int t, j;
for (1 => int i; i < N; i++) {
for (i => j; j > 0 && data[j] < data[j-1]; j--) {
noteOn(data[j]);
swap(j, j-1);
}
}
}
/*** シェルソート ***/
fun void shellSort() {
int h, j, t;
for (1 => h; h < N; h*3+1 => h);
while (h > 0) {
h/3 => h;
for (h => int i; i < N; i++) {
for (i => j; j >= h && data[j] < data[j-h]; h -=> j) {
noteOn(data[j]);
swap(j, j-h);
}
}
}
}
/*** クイックソート ***/
fun void qsort(int left, int right) {
left => int i;
right => int j;
data[(left+right)/2] => int pivot;
while (true) {
while (data[i] < pivot) {
noteOn(data[i]);
i++;
}
while (data[j] > pivot) {
noteOn(data[j]);
j--;
}
if (i >= j) break;
swap(i, j);
i++;
j--;
}
if (left < i-1) qsort(left, i-1);
if (j+1 < right) qsort(j+1, right);
}
fun void quickSort() {
qsort(0, N-1);
}
/*** マージソート ***/
fun void merge(int left, int mid, int right, int tmp[]) {
for (left => int i; i <= right; i++) {
noteOn(data[i]);
data[i] => tmp[i];
}
left => int l;
mid+1 => int r;
int k;
for (left => k; l <= mid && r <= right; k++) {
if (tmp[l] <= tmp[r]) {
tmp[l] => data[k];
l++;
} else {
tmp[r] => data[k];
r++;
}
noteOn(data[k]);
}
for (; l <= mid; l++) {
tmp[l] => data[k];
noteOn(data[k]);
k++;
}
}
fun void msort(int left, int right, int tmp[]) {
if (left >= right) return;
(left+right)/2 => int m;
msort(left, m, tmp);
msort(m+1, right, tmp);
merge(left, m, right, tmp);
}
fun void mergeSort() {
int tmp[N];
msort(0, N-1, tmp);
}
/*** ヒープソート ***/
fun void makeHeap(int i, int n) {
i*2+1 => int l;
l+1 => int r;
int max;
if (l >= n) return;
noteOn(data[i]);
(r < n && data[l] < data[r]) ? r : l => max;
if (data[i] < data[max]) {
swap(i, max);
makeHeap(max, n);
}
}
fun void heapSort() {
for ((N-2)/2 => int i; i >= 0; i--) {
makeHeap(i, N);
}
for (N-1 => int i; i > 1; i--) {
swap(0, i);
makeHeap(0, i-1);
}
}
比較グラフ。横軸が整数列のサイズ、縦軸がnoteOnを呼んで音を鳴らした回数（各10回分の平均値）。
