クイックソート

まず一つめ。アルゴリズムはこの動画とほぼ同じで、軸要素は配列の中心にしている。破壊的な関数。

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;
}

選択ソートは一々交換しないのでバブルソートより速い。