アルゴリズム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) ... 大きな問題を複数の小さな問題に分割した上でそれぞれを各個撃破する方法

分割のアルゴリズム

「注目している領域を２つに分割する方法」を述べているのが 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 です。

$ 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 

クイックソートの計算量

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

この場合、計算量は $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が、 http://nw.tsuda.ac.jp/class/algoB/sortdata/ の下の 3種類のデータ

• rand800k.txt -- 800000個のデータがランダムに並んでいる
• inc800k.txt -- 800000個のデータが昇べきの順に並んでいる
• dec800k.txt -- 800000個のデータが降べきの順に並んでいる

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

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

Exception in thread "main" java.lang.StackOverflowError
	at QuickSort.quickSort(QuickSort.java:25)
	...

    -Xssスタックサイズ

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

[注意] 指定できるスタックサイズには上限があり、その最大値はシステムによって異なります。 たとえばあるバージョンの Mac (arm64) では 1024m までしか指定できないようです。

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

• Windows や Mac (arm64) の場合

標準出力(上記の場合はaというファイル)には

Error occurred during initialization of VM
java.lang.OutOfMemoryError: unable to create new native thread
        at java.lang.Thread.start0(Native Method)
        at java.lang.Thread.start(Thread.java:640)
        at java.lang.ref.Reference.<clinit>(Reference.java:145)

のようなエラーメッセージが出ている。 実行が終了したら、必ず

$ more /tmp/a

などとして出力ファイル(上記の場合は/tmp/a)の中身を 表示させて、正しく実行されたかどうかを確認する必要がある。
• Mac (intel) の場合

スタックを大きく取りすぎるとプログラムが異常終了するが、 このときtimeコマンドを使っていると画面にも標準出力にも 何も出力されていない。 timeコマンドなしで実行した場合は "Abort trap: 6" と表示される。 すなわち time コマンド無しでjavaだけで走らせてみる必要がある。

$ java -Xss3000m QuickSort < inc800k.txt
Abort trap: 6

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

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

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

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

$ time (java QuickSortLoop <rand800k.txt >a)   
ここに表示される経過時間(realの値)を答えなさい。
$ time (java QuickSortLoop <inc800k.txt >a)   
ここに表示される経過時間(realの値)を答えなさい。
$ time (java QuickSortLoop <dec800k.txt >a)   
ここに表示される経過時間(realの値)を答えなさい。

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

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で用いたrand800k.txt, inc800k.txt, dec800k.txt それぞれに対する計算時間を答えなさい。

$ time (java QuickSortPivot <rand800k.txt >/tmp/a)   
ここに表示される経過時間(realの値)を答えなさい。
$ time (java QuickSortPivot <inc800k.txt >/tmp/a)   
ここに表示される経過時間(realの値)を答えなさい。
$ time (java QuickSortPivot <dec800k.txt >/tmp/a)   
ここに表示される経過時間(realの値)を答えなさい。