頭の体操がてらクイックソートを実装してみた。現時点ではchromeだとビルトインのArray.sortより速い。FireFoxだとArray.sortの方が約10倍速い。
クイックソート
まず一つめ。アルゴリズムはこの動画とほぼ同じで、軸要素は配列の中心にしている。破壊的な関数。
function quickSort(array) { (function sort(start, end) { //再帰出口; if(start >= end) { return; } var left = start; var right = end; var reference = array[Math.round((left + right) / 2)]; //左から値を見ていく; //最終的にleftとrightは同じindexになるか交差する; //交差した場合はleft > rightになる; while(left < right) { if(array[left] >= reference) { while(right > left) { if(array[right] <= reference) { var tmp = array[left]; array[left] = array[right]; array[right] = tmp; right--; break; } right--; } } left++; } if(array[right] > reference) { sort(start, right - 1); sort(right, end); }else if(array[right] < reference) { sort(start, right); sort(right + 1, end); }else { //array[right]がreferenceと同じ値の時の処理; sort(start, right - 1); sort(right + 1, end); } })(0, array.length - 1); return array; }
次に二つめ。アルゴリズムはこのサイトを参考にして書いた。一番左を軸要素にしている。破壊的な関数。
function quickSort2(array) { (function sort(start, end) { if(start >= end) { return; } var reference = array[start]; var left = start + 1; var right = end; while(left < right) { if(array[left] > reference) { while(right > left) { if(array[right] <= reference) { var tmp = array[left]; array[left] = array[right]; array[right] = tmp; right--; break; } right--; } } left++; } var center; if(array[right] > reference) { center = right - 1; }else { center = right; } array[start] = array[center]; array[center] = reference; sort(start, center - 1); sort(center + 1, end); })(0, array.length - 1); return array; }
速度はchromeだとquickSort2, quickSort, Array.sortの順で、FireFoxだとArray.sort, quickSort2, quickSortだった。
テストコード
以下がテストコード。引数にソートする配列の桁数を指定する。まずは10000あたりで比べてみると良さげ。
function quickSortTest(num) { var list = []; var list2 =[]; var list3 =[]; var i = 0; while(i < num) { var randomNum = Math.floor(Math.random() * num); list.push(randomNum); list2.push(randomNum); list3.push(randomNum); i++; } console.time('quickSort'); quickSort(list); console.timeEnd('quickSort'); console.time('quickSort2'); quickSort2(list2); console.timeEnd('quickSort2'); console.time('Array.sort'); list3.sort(function(a, b) { return a - b; }); console.timeEnd('Array.sort'); }
クイックソート以外にも、簡単なソートアルゴリズムを実装したので以下に載せる。
バブルソート
function bubbleSort(array) { for(var i = array.length; i > 0; i--) { for(var j = 0; j < i - 1; j++) { if(array[j] > array[j+1]) { var tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } } return array; }
function bubbleSort2(array) { for(var i = 0, len = array.length; i < len; i++) { for(var j = i + 1; j < len; j++) { if(array[i] > array[j]) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } } } return array; }
選択ソート
function selectionSort(array) { var box = []; for(var i = 0; i < array.length; i++) { box[0] = array[i]; box[1] = i; for(var j = i + 1; j < array.length; j++) { if(box[0] > array[j]) { box[0] = array[j]; box[1] = j; } } var tmp = array[i]; array[i] = box[0]; array[box[1]] = tmp; } return array; }
選択ソートは一々交換しないのでバブルソートより速い。