[LastModified: 06/03/02 19:03:43]

JavaScriptで
クイックソート

JavaScriptでクイックソートを書いてみました。ん?それだけですよ?
数年前、初めてC言語で勉強したときにはなんだか難しく思いましたが
こうしてみると、ソートの中では一番簡単に書ける気がします。
アルゴリズムの勉強ってことなら、スクリプト言語でやればいいのになぁ。


ソート結果:

●遊び方(?)
スペース区切りで整数を並べます。
「sort !」ボタンを押すとソートします。

●注意点
数値以外は無視します。
小数点以下は切り捨てます。

●プログラム
検索でここに来る方が多いので、
プログラムの解説もしておこうかと。
良かったら参考にしてください。
//引数として配列を受ける
function qsort(a){
	//もし配列の長さが1以下ならそのまま返す
	if(a.length<=1)return a;
	//そうでなければ、
	else{
		//配列の最後の要素を取り出す(pivot)
		var p=a.pop();
		var s=[];
		var l=[];
		//配列の要素をひとつずつ取り出し
		for(i in a){
			//もしpivotよりも小さければ配列 s に入れる
			if(a[i]<p)
				s.push(a[i]);
			//そうでなければ配列 l に入れる
			else
				l.push(a[i]);
		}
		//配列 s を再帰的に関数qsortに渡す
		s=qsort(s);
		//ソートされた配列 s の最後にpivotを加える
		s.push(p);
		//配列 s に、配列 l を再帰的に関数qsortに渡して返す
		return s.concat(qsort(l));
	}
}