Aritalab:Lecture/Algorithm/Sorting - Revision history

Adm: /* Straight Radix Sort */

2012-05-14T02:16:47Z

‎Straight Radix Sort

2012-05-14T02:11:15Z

‎Radix Exchange Sort

2012-05-14T02:07:57Z

‎整数の整列アルゴリズム

2012-05-07T15:13:34Z

‎Counting Sort

2012-05-07T15:11:21Z

‎整数の整列アルゴリズム

2012-05-07T15:10:35Z

‎Heap Sort

2012-05-07T15:08:06Z

‎Bubble Sort

2011-06-02T08:05:36Z

2011-06-01T15:28:34Z

2010-10-20T02:10:32Z

‎Quick Sort

@@ Line 261: / Line 261: @@
 ===Straight Radix Sort===
-右側（小さい桁）からそろえていく場合を直接基数ソートといいます。直接基数ソートで　d 桁目を揃えるとき、 d-1 桁までは既に揃えてあるので順番を崩さないように並び替えるところがポイントです。各桁ごとに配列 tmp と配列 A の間で丸コピーしていますが、配列を交互に使えば省略可能です。
+右側（小さい桁）からそろえていく場合を直接基数ソートといいます。直接基数ソートで d 桁目を揃えるには、1回目のスキャンでその桁に出てくる各数字の回数を記録して、そのサイズの箱を用意しておきます。2回目のスキャンで各数字が出てきた順に箱に移動させていきます。このとき、 d-1 桁までは既に揃えてあるので順番を崩さないように並び替えるところがポイントです。各桁ごとに配列 tmp と配列 A の間で丸コピーしていますが、配列を交互に使えば省略可能です。
 <pre>

@@ Line 258: / Line 258: @@
 {  return (number >> b) & 0x1; }
 </pre>
-各桁について配列全体をスキャンするので、最悪計算量は桁数を b とすると O(n b) になります。
+各桁について配列全体をスキャンするので、最悪計算量は桁数を b とすると O(n b) になります。桁数が大きくなると（たとえば b = 32 ）、実用ではなくなります。複数桁をまとめて処理する方法もないので、次の Straight Radix Sort が便利です。
 ===Straight Radix Sort===

← Older revision		Revision as of 02:07, 14 May 2012
Line 227:		Line 227:

	桁の左側からそろえる場合と右側からそろえる場合でアルゴリズムが異なります。		桁の左側からそろえる場合と右側からそろえる場合でアルゴリズムが異なります。
		+
		+	===準備===
		+	* 2進数表現では右から b ( = 0, 1, 2 .. ) 番目のビットが 2<sup>b</sup> をあらわします
		+

	===Radix Exchange Sort===		===Radix Exchange Sort===

@@ Line 287: / Line 287: @@
 ===Counting Sort===
-ラディックスソートとは異なりますが、類似の手法として、分布数えソートを紹介します。
+ラディックス（基数）ソートとは異なりますが、類似の手法として、分布数えソートを紹介します。
-ソート対象が1からkまでとわかっていれば、各要素に対して、その要
+ソート対象の大きさが 1 から k までとわかっていれば、各要素に対し、その要素より小さい値が何個あるかを数えることで、その要素が何番目に来るべきかを線形時間で計算できます。
-素より小さい値が何個あるかを数えることで、その要素が何番目に来るべきかを線形時間で計算できます。
 <pre>

@@ Line 221: / Line 221: @@
 数字のソートであれば、線形時間アルゴリズムが多数知られています。
 数字の桁数が有限と仮定して、桁毎にそろえる手法を一般にRadix Sort (基数ソート) といいます。
-ただしソートできるのは整数値（浮動小数は無理）に限り、値の正負やバイト数をよく把握した上で適用しなくてはなりません。以下では
+ただしソートできるのは整数値に限り（浮動小数は無理）、値の正負やバイト数をよく把握した上で適用しなくてはなりません。以下では
 # 負の値が無い
 # 32ビット整数

@@ Line 216: / Line 216: @@
+}
 </pre>
-ヒープソートは再帰を使わず使用するメモリも少ないため、大きな集合のソートにも利用できます。速度はマージソートよりも少々遅くなります。最初のbuildHeapが　O(n log n) 時間。Heapify処理は高々 log n ステップで終了するので、最悪計算量は O(n log n) です。
+ヒープソートは再帰を使わず使用するメモリが少ないので、大きな集合のソートにも利用できます。速度はマージソートよりも少々遅くなります。最初のbuildHeapが　O(n log n) 時間。Heapify処理は高々 log n ステップで終了するので、最悪計算量は O(n log n) です。
 ==整数の整列アルゴリズム==

@@ Line 58: / Line 58: @@
 ===Bubble Sort===
-バブルソートはファイルを先頭からスキャンし、隣り合う数の大小が狂っていたら交換します。
+バブルソートはファイルを先頭からスキャンし、隣り合う数の大小が逆になっていたら交換します。
 <pre>
 static public void bubbleSort(int[] A)

@@ Line 126: / Line 126: @@
 </pre>
 平均計算量は O(n log n)、最悪計算量は O( n<sup>2</sup> ) になります。
-[[Aritalab:Lecture/Basic/Quicksort|平均計算量の解説]]も参考にしてください。
+[[Aritalab:Lecture/Algorithm/Quicksort|平均計算量の解説]]も参考にしてください。
 <references/>