アルゴリズムb 第5回


クイックソート

C.A.R. Hoare が 1962年に発表。 内部整列で最高速の $O(n \log n)$ 。 「安定なソート」ではない。

クイックソートのアイディア
[1] n個の要素を持つ配列 a[0], a[1], ..., a[n-1] について
    適当なxを(pivot、枢軸として)選び出して、最終位置 a[v] に移動する。
[2] xと同じか大きい要素を v[i] (i > v) に、
    xより小さい要素を v[j] (j < v) に、
    移動する(集める)。←これを『分割(partitioning)』という。
[3] a[v]の左側と右側それぞれに対して[1][2]の操作を再帰的に繰り返す。

p.316, Fig 14.1 「クイックソートの考え方」参照。

この考え方をアルゴリズムとして(プログラムに似た)表現をしたのが p.317, List 14.1 「クイックソートの考え方」。

分割統治法 (divide and conquer) ... 大きな問題を複数の小さな問題に分割した上でそれぞれを各個撃破する方法

分割のアルゴリズム

「注目している領域を2つに分割する方法」を述べているのが p.317 の 14.1.2 「分割のアルゴリズム」です。

分割のアルゴリズム
[1] 着目している領域を a[s], a[s+1], ..., a[e] とする。
[2] a[e]を「枢軸」として最終的な位置に置くことを考える。すなわち 
        a[e] よりも小さな要素は a[e]よりも左に、
        a[e] と同じか大きな要素は a[e]よりも右に、
    置きたい。
  [2-1] i = s, j = e-1 とおく。
  [2-2] a[i]がa[e]よりも小さい間 iを1増やす。(そのa[i]は移動する必要がないので)
  [2-3] a[j]がa[e]よりも大きい間 jを1減らす。(そのa[j]は移動する必要がないので)
  [2-4] a[i]とa[j]を交換する。i を1増やし、j を1減らす。
  [2-5] iとjがぶつかるまで[2-2]〜[2-4]を繰り返す。
  [2-6] この段階ではa[i]はa[e]と等しいか大きくなっているのでa[i]とa[e]を交換
        すればa[e]は正しい位置に配置されたことになる。

「分割」の具体例は p.318 Fig.14.2 に示されていますので、 この図を順番に見ておきましょう。

クイックソートのプログラム

クイックソートのアルゴリズムをそのまま再帰的に表現したのが p.321 List14.2 です。





QuickSort.javaの実行例
$ javac QuickSort.java   
$ java QuickSort   
データの個数を入力して下さい  8   
5 2 9 8 1 3 7 4   
1 2 3 4 5 7 8 9 
$ java QuickSort -d   
データの個数を入力して下さい  8   
5 2 9 8 1 3 7 4   
partition l=0, r=7
check i=0,j=5,pivot=4
change i=0,j=5
check i=2,j=4,pivot=4
change i=2,j=4
check i=3,j=3,pivot=4
l=0, r=7,v=3: 3 2 1 4 9 5 7 8 
partition l=0, r=2
check i=0,j=0,pivot=1
l=0, r=2,v=0: 1 2 3 4 9 5 7 8 
partition l=1, r=2
check i=2,j=1,pivot=3
l=1, r=2,v=2: 1 2 3 4 9 5 7 8 
partition l=4, r=7
check i=4,j=6,pivot=8
change i=4,j=6
check i=6,j=6,pivot=8
l=4, r=7,v=6: 1 2 3 4 7 5 8 9 
partition l=4, r=5
check i=4,j=4,pivot=5
l=4, r=5,v=4: 1 2 3 4 5 7 8 9 
1 2 3 4 5 7 8 9 
$ java QuickSort -d   
データの個数を入力して下さい  8   
1 2 3 4 5 6 7 8   
partition l=0, r=7
check i=7,j=6,pivot=8
l=0, r=7,v=7: 1 2 3 4 5 6 7 8 
partition l=0, r=6
check i=6,j=5,pivot=7
l=0, r=6,v=6: 1 2 3 4 5 6 7 8 
partition l=0, r=5
check i=5,j=4,pivot=6
l=0, r=5,v=5: 1 2 3 4 5 6 7 8 
partition l=0, r=4
check i=4,j=3,pivot=5
l=0, r=4,v=4: 1 2 3 4 5 6 7 8 
partition l=0, r=3
check i=3,j=2,pivot=4
l=0, r=3,v=3: 1 2 3 4 5 6 7 8 
partition l=0, r=2
check i=2,j=1,pivot=3
l=0, r=2,v=2: 1 2 3 4 5 6 7 8 
partition l=0, r=1
check i=1,j=0,pivot=2
l=0, r=1,v=1: 1 2 3 4 5 6 7 8 
1 2 3 4 5 6 7 8 
$ java QuickSort -d   
データの個数を入力して下さい  8   
8 7 6 5 4 3 2 1   
partition l=0, r=7
check i=0,j=0,pivot=1
l=0, r=7,v=0: 1 7 6 5 4 3 2 8 
partition l=1, r=7
check i=7,j=6,pivot=8
l=1, r=7,v=7: 1 7 6 5 4 3 2 8 
partition l=1, r=6
check i=1,j=1,pivot=2
l=1, r=6,v=1: 1 2 6 5 4 3 7 8 
partition l=2, r=6
check i=6,j=5,pivot=7
l=2, r=6,v=6: 1 2 6 5 4 3 7 8 
partition l=2, r=5
check i=2,j=2,pivot=3
l=2, r=5,v=2: 1 2 3 5 4 6 7 8 
partition l=3, r=5
check i=5,j=4,pivot=6
l=3, r=5,v=5: 1 2 3 5 4 6 7 8 
partition l=3, r=4
check i=3,j=3,pivot=4
l=3, r=4,v=3: 1 2 3 4 5 6 7 8 
1 2 3 4 5 6 7 8 

クイックソートの計算量

「整列済みのデータを与えると、クイックソートは最悪の計算量がかかってしまう」 ことに注意して下さい。 領域の長さが1個ずつ(枢軸の分)しか減らないからです。

この場合、計算量は $O(n^2)$ になりますし、 スタックも $O(n)$ 必要になってしまいます。

クイックソートの改善

再帰呼び出しを行う場合は、コンピュータのスタックがオーバーフロー (溢れること)を起こしてプログラムが異常終了することがあります。 「再帰呼び出し」のプログラムを、 自前のスタックを用意してプログラムとしては単なる 「繰り返し」で実装する ことで効率が改善することがあります。(課題5b)

また、「整列済みのデータに対して効率が悪い」ことへの対策として、 「$s$ から $e$ の範囲のデータ(ただし $s < e$ )を『分割』するときに『枢軸』をa[$e$]に決め打ちするのではなく、 a[$s$], a[$(s+e)/2$], a[$e$] という3個のデータの真中の値のデータを『枢軸』に選ぶ」 という方法があります(課題5c)。



アルゴリズムB 演習


作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。

提出した後は、正しく提出されていることを http://ynitta.com/class/algoB/local/handin/ で必ず確認しておいて下さい。

提出〆切は次回の講義の開始時刻です。


課題5a: QuickSortのプログラムを動かしてみよう

提出ファイルQuickSort.java
コメント欄:rand400k.txt〜dec400k.txtそれぞれに対する計算時間
提出先: 「宿題提出web:アルゴリズムB:課題5a」
http://ynitta.com/class/algoB/local/handin/up.php?id=kadai5a

QuickSort.javaが、 http://nw.tsuda.ac.jp/class/algoB/sortdata/ の下の 3種類のデータ

を処理するのに必要な時間をそれぞれ計測し、答えなさい。

ただし、スタックを2000Mバイトに広げても StackOverflowError が起きて 計算を最後まで実行することが不可能なデータに対しては 「計測不能」と答えて構わない。

[注意] 現在のjava実行系のデフォルトのスタックサイズは512Kバイト程度 (OSにより異なる)であるが、 QuickSortを実行中に再帰呼出しが深くなるとスタックが 足りなくなり、次のようなExceptionが発生する可能性がある。

Exception in thread "main" java.lang.StackOverflowError
	at QuickSort.quickSort(QuickSort.java:25)
	...
このような場合は、javaの実行時にスタックの大きさを指定するオプション
    -Xssスタックサイズ
でスタックサイズを指定して実行する。

[実行例]
たとえばスタックサイズを2000M Byteに広げて QuickSort を実行するには
    $ java -Xss2000m  QuickSort  <inc400k.txt  >/tmp/a
とする。この時間を計測するには
    $ time  ( java -Xss2000m  QuickSort  <inc400k.txt  >/tmp/a )
などと指定すればよい。

[注意] 現在皆さんが使っているシステム (m1 mac) 上の Java では 1024m までしか指定できないようです。

スタックとして大き過ぎる値を指定すると、一見エラーがなさそうに 直ちにプログラムが終了するが、この場合は正しく実行できていない。 エラーの確認方法はOSにより異なる。


課題5b: 再帰呼び出しをしないQuickSort

提出ファイルQuickSortLoop.java
コメント欄:rand400k.txt〜dec400k.txtそれぞれに対する計算時間
提出先: 「宿題提出web:アルゴリズムb:課題5b」
http://ynitta.com/class/algoB/local/handin/up.php?id=kadai5b

自前のスタックを用意することで、再帰呼び出しを使わない QuickSortLoop.javaを作成して下さい。

プログラムを作成した後は、必ず簡単なデータを試しに与えて 正しく動作することを確認すること。

課題5aで用いたrand400k.txt〜dec400k.txtそれぞれに対する計算時間を答えなさい。






QuickSortLoop.javaの実行例
$ time (java QuickSortLoop <rand400k.txt >a)   
ここに表示される経過時間(realの値)を答えなさい。
$ time (java QuickSortLoop <inc400k.txt >a)   
ここに表示される経過時間(realの値)を答えなさい。
$ time (java QuickSortLoop <dec400k.txt >a)   
ここに表示される経過時間(realの値)を答えなさい。

課題5c: Pivot用データを選ぶQuickSort

提出ファイルQuickSortPivot.java
コメント欄:rand400k.txt〜dec400k.txtそれぞれに対する計算時間
提出先: 「宿題提出web:アルゴリズムb:課題5c」
http://ynitta.com/class/algoB/local/handin/up.php?id=kadai5c

static int partition(int[]a, int l,int r) メソッドの先頭で、 処理するデータ数 (r - (l -1))が10より大きい場合には、 「配列aのインデックスが l, (l+r)/2, r である3箇所のデータのうち 最小のデータを a[l]に、最大のデータをa[(l+r)/2]に、真ん中の大きさのデータをa[r]に移動する 」 ように変更した QuickSortPivot.javaを作成して下さい。

プログラムを作成した後は、必ず簡単なデータを試しに与えて 正しく動作することを確認すること。

課題5aで用いたrand400k.txt〜dec400k.txtそれぞれに対する計算時間を答えなさい。




QuickSortPivot.javaの実行例
$ time (java QuickSortPivot <rand400k.txt >/tmp/a)   
ここに表示される経過時間(realの値)を答えなさい。
$ time (java QuickSortPivot <inc400k.txt >/tmp/a)   
ここに表示される経過時間(realの値)を答えなさい。
$ time (java QuickSortPivot <dec400k.txt >/tmp/a)   
ここに表示される経過時間(realの値)を答えなさい。