Quick Sort 計算機アルゴリズム特論 :2017 年度只木進一

Size: px

Start display at page:

Download "Quick Sort 計算機アルゴリズム特論 :2017 年度只木進一"

ありさなかじゅく
5 years ago
Views:

1 Quick Sort 計算機アルゴリズム特論 :2017 年度只木進一

2 2 基本的考え方リスト ( あるいは配列 )SS の中のある要素 xx(pivot) を選択 xx より小さい要素からなる部分リスト SS 1 xx より大きい要素からなる部分リスト SS 2 xx は SS 1 または SS 2 に含まれる長さが 1 になるまで繰り返す pivot xx の選び方として中央の要素を選択すると効率が良い

3 3 三つの可能性 pivot を中央の要素とした場合 pivot の両側の入れ替えるべき要素数が同じ場合 : 例 1 pivot の位置より左側にある移動すべき要素が右側のそれより多い場合 : 例 2 pivot の位置より左側にある移動すべき要素が右側のそれより少ない場合 : 例 3

4 4 左端からxx ii xxとなる要素を探す右端からxx jj xxとなる要素を探す xx ii とxx jj を入れ替える ii < jjである限り繰り返す SS 1 = xx kk 0 kk < ii SS 2 = {xx kk ii kk < SS

5 5 例 1 基準値左端から基準値以上となる最初の要素 (32) の位置 ii 右端から基準値以下となる最初の要素 () の位置 jj 二つの要素を入れ替える ii 45 ii jj 位置 iiから基準値以上となる最初の要素 (45) の位置 ii 位置 jjから基準値以下となる最初の要素 () の位置 jj 二つの要素を入れ替える jj 32

6 6 ii jj 位置 ii から基準値以上となる最初の要素 () の位置 ii 位置 jj から基準値以下となる最初の要素 () の位置 jj ii jj となったので ii で分割基準値より小さい基準値以上

7 7 例 2 基準値 25 ii 左端から基準値以上となる最初の要素 (25) の位置 ii 右端から基準値以下となる最初の要素 () の位置 jj 二つの要素を入れ替える ii jj 位置 iiから基準値以上となる最初の要素 (32) の位置 ii 位置 jjから基準値以下となる最初の要素 (23) の位置 jj 二つの要素を入れ替える jj 25

8 ii jj 位置 iiから基準値以上となる最初の要素 (45) の位置 ii 位置 jjから基準値以下となる最初の要素 () の位置 jj 二つの要素を入れ替える jj ii 位置 ii から基準値以上となる最初の要素 (45) の位置 ii 位置 jj から基準値以下となる最初の要素 () の位置 jj ii jj となったので ii で分割基準値以下基準値より大きい

9 9 例 3 基準値 12 左端から基準値以上となる最初の要素 () の位置 ii 右端から基準値以下となる最初の要素 (20) の位置 jj 二つの要素を入れ替える 12 ii 20 ii jj 位置 iiから基準値以上となる最初の要素 () の位置 ii 位置 jjから基準値以下となる最初の要素 () の位置 jj 二つの要素を入れ替える 20 jj

10 jj ii 位置 ii から基準値以上となる最初の要素 () の位置 ii 位置 jj から基準値以下となる最初の要素 () の位置 jj ii jj となったので ii で分割基準値より小さい基準値以上

11 public T[] dosort() { sortsub(0, data.length); return data; protected void sortsub(int begin, int end) { if (end <= begin + 1) { return; int boundary = partition(begin, end); sortsub(begin, boundary); sortsub(boundary, end);

12 12 protected int partition(int begin, int end) { int fromleft = begin - 1; int fromright = end; int m = (begin + end) / 2; T v = data[m]; for (;;) { while (less(data[++fromleft], v)); while (less(v, data[--fromright])) { if (fromright == begin) { break; if (fromleft >= fromright) {break; exch(fromleft, fromright); return fromleft;

13 13 注 :increment/decrement 演算子 bb = aa + +; aa を bb へ代入後インクリメント bb =+ +aa; aa をインクリメント後 bb へ代入 while (less(data[++fromleft], v)); v より小さくない要素を見つけるまで fromleft をインクリメント

14 14 計算量一回の partition 操作で要素の比較は nn 回 partitioning は概ね log 2 nn 回全体で nnlog 2 nn 回の比較要素を swap するために作業領域を必要としない

15 比較回数

16 16 入替回数

17 17 pivot の選択を最後の要素にした場合基準値 12 ii 左端から基準値以上となる最初の要素 () の位置 ii 右端から基準値以下となる最初の要素 (20) の位置 jj 二つの要素を入れ替える 20 jj ii jj 位置 ii から基準値以上となる最初の要素 () の位置 ii 位置 jj から基準値以下となる最初の要素 () の位置 jj 二つの要素を入れ替える

18 12 20 位置 ii から基準値以上となる最初の要素 () の位置 ii 位置 jj から基準値以下となる最初の要素 () の位置 jj ii jj となったので ii で分割 jj ii 12 20

20 QuickSort.java package sort; import java.io.ioexception; import java.util.function.binaryoperator; import static sort.abstractsort.testrun; /** * tadaki <T> */ public class QuickSort<T extends Comparable<T>> extends AbstractSort<T> { //pivot の選び方 public static enum PivotType { Middle, First, Last, Random; public static final boolean debug = false; //pivot を選ぶ関数のデフォルト private BinaryOperator<Integer> getpivot = (begin, end) -> (begin + end) / 2; public QuickSort(T[] data) { super(data); public QuickSort() { /** * pivot を変更する * pivottype */ public void setpivottype(pivottype pivottype) { switch (pivottype) { case First:// 最初の要素 getpivot = (begin, end) -> begin; break; case Last:// 最後の要素 getpivot = (begin, end) -> end - 1; break; case Random:// ランダム getpivot = (begin, end) -> (int) ((end - begin) * Math.random()) + begin; break; 1/3 ページ

21 QuickSort.java default:// 中央の要素 getpivot = (begin, end) -> (begin + end) / 2; public T[] dosort() { sortsub(0, data.length); return data; protected void sortsub(int begin, int end) { if (end <= begin + 1) { return; int boundary = partition(begin, end); sortsub(begin, boundary); sortsub(boundary, end); /** * pivot の値での分割 * begin 配列の開始位置 end 終了位置 : 対象の外側であることに注意分割の位置 */ protected int partition(int begin, int end) { int fromleft = begin - 1; int fromright = end; int m = getpivot.apply(begin, end); T v = data[m]; if (debug) { System.out.print("partition (" + begin + "," + end + ") "); System.out.println("with pivot " + v + " at " + m); for (;;) { while (less(data[++fromleft], v)); while (less(v, data[--fromright])) { if (fromright == begin) { break; if (fromleft >= fromright) { break; 2/3 ページ

22 QuickSort.java if (debug) { System.out.println(data2Str() + ":swap(" + fromleft + "," + fromright + ")"); exch(fromleft, fromright); if (debug) { System.out.println("end paritioning with " + data2str()); return fromleft; /** * 配列の文字列化 * */ private String data2str() { StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < data.length - 1; i++) { sb.append(data[i]).append(","); sb.append(data[data.length - 1]).append("]"); return sb.tostring(); /** args the command line arguments java.io.ioexception */ static public void main(string args[]) throws IOException { if (QuickSort.debug) { Integer[] data = {,, 12,,,,,,,, 20; QuickSort<Integer> qs = new QuickSort<>(data); qs.dosort(); else { int numdata = 1000; Data[] data = Data.createData(numData); testrun(new QuickSort<>(data)); 3/3 ページ

目的泡立ち法を例に Comparableインターフェイスの実装抽象クラスの利用型パラメタの利用比較入替の回数を計測

目的泡立ち法を例に Comparableインターフェイスの実装抽象クラスの利用型パラメタの利用比較入替の回数を計測泡立ち法とその実装計算機アルゴリズム特論 :2017 年度只木進一目的泡立ち法を例に Comparableインターフェイスの実装抽象クラスの利用型パラメタの利用比較入替の回数を計測 Comparable インターフェイスクラスインスタンスが比較可能であることを示す Int compareto() メソッドを実装 Integer Double String などには実装済み public

Quick Sort 計算機アルゴリズム特論 :2017 年度 只木進一

Quick Sort 計算機アルゴリズム特論 :2017 年度只木進一