プロフィール

島田圭二

Author:島田圭二
Follow shimanp on Twitter

カレンダー
10 | 2017/11 | 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -
読断と変見内検索
訪問ありがとうございます
最近のコメント
最近のトラックバック
関連リンク
カテゴリー
月別アーカイブ


スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


スポンサー広告 | 【--------(--) --:--:--】 | Trackback(-) | Comments(-)
アルゴリズム - クイックソート - 再帰編
数字などを並び替えするアルゴリズムにクイックソートがある。
とても効率的でソートアルゴリズムの中でもトップクラスに早いらしいけど、
完全に理解していなかったので、wikiを見ながら勉強してみた。

とりあえず、wiki通りにJAVAで書いてみた

public class QuickSort {

public static void main(String[] args) {
int[] a = {8,4,3,7,6,5,2,1};
QuickSort q = new QuickSort();
q.sort(a, 0, a.length - 1);
for (int k = 0, len = a.length; k < len; k++) {
System.out.print(k == 0 ? a[k] : "," + a[k]);
}
}

public void sort(int a[], int left, int right) {
if (left < right) {
int p = a[(left+right)/2]; //中央を軸とする
int l = left - 1;
int r = right + 1;
int t;
while (true) {
while (a[++l] < p); //軸より大きい値を左から探す
while (a[--r] > p); //軸より小さい値を右から探す
if (l >= r)break;
t = a[l]; //左と右の値を入れ替える。
a[l] = a[r];
a[r] = t;
}
sort(a, left, l - 1);
sort(a, r + 1, right);
}
}
}

wikiにも説明があるけど、自分なりに説明してみる。


①軸を決める
配列の中から、一つ適当に軸となる値を選ぶ。
プログラムで言うと
int p = a[(left+right)/2];

*軸は配列内の中央に位置しているものがベスト

②左から順に軸より大きい値を探す
プログラムで言うと
while (a[++l] < p);

の箇所whileで左から順に軸より大きい数を探し、あったら、ループ終了。

③右から順に軸より小さい値を探す
プログラムで言うと
while (a[--r] > p);

の箇所whileで右から順に軸より小さい数を探し、あったら、ループ終了。

④値入れ替え
②で見つけた値と③で見つけた値の位置を入れ替える。
プログラムで言うと
t = a[l];      
a[l] = a[r];
a[r] = t;

この入れ替えを繰り返すことで、左側は軸より小さい値となり
右側は軸より大きい値となる。

ただし、lの値がrの値以上となるとループを抜ける
プログラムで言うと
if (l >= r)break;


⑤左側の部分を再帰的にソート
軸より小さな左側の部分を再帰的にソートする
プログラムで言うと
sort(a, left, l - 1);


⑥右側の部分を再帰的にソート
軸より大きな右側の部分を再帰的にソートする
プログラムで言うと
sort(a, r + 1, right);


具体的な流れ


初期データ:{8,4,3,7,6,5,2,1}
1.軸を決める
一番始めの軸は、(0+7)/2=3.5→intなので3
で配列は0から始まるので、3の要素は「7」となる。
よって軸は「7」となる
8,4,3,7,6,5,2,1


2.左から順に軸より大きい値を探す
   8,4,3,7,6,5,2,1
→ l

8が軸の7より大きい

3.右から順に軸より小さい値を探す
  8,4,3,7,6,5,2,1
r ←

1が7より小さい

4.値入れ替え
lの値(0)はrの値(7)より小さいので、
2で見つけた8と3で見つけた1を入れ替える
1,4,3,7,6,5,2,8


5.再度左右から値を探し、入れ替え・・・を繰り返す。
lの値がrの値より小さいので、再度左から軸より大きい値、
右から軸より小さい値を探す。
  1,4,3,7,6,5,2,8
→ l
r ←

左から探した大きい値は7(軸と同じ)、
右から探した小さい値は2となる。

7と2を入れ替える
1,4,3,2,6,5,7,8


まだlの値がrの値より小さいので、再度左から軸より大きい値、
右から軸より小さい値を探す。
  1,4,3,2,6,5,7,8
→ l
r ←

左から探した大きい値は7(軸と同じ)、
右から探した小さい値は5となる。
しかし、lの値がrの値以上となってしまったため、ループは終了。

6.左側の部分を再帰的にクイックソート
左側の部分は[1,4,3,2,6,5]となる
プログラムで言うとleftからl-1ということになる。
leftは0でl-1は5となるので、0~5の配列要素が対象となる。

  左側部分  | 右側部分
1,4,3,2,6,5 | 7,8


で、左側の部分をまた1.に戻って、ソートを行う。

7.右側の部分を再帰的にクイックソート
右側の部分は[7,8]となる
プログラムで言うとr+1からrightということになる。
r+1は6でrightは7となるので、7~8の配列要素が対象となる。

  左側部分  | 右側部分
1,4,3,2,6,5 | 7,8


で、右側の部分をまた1.に戻って、ソートを行う。

以上説明終了。
てかクイックソートは説明が難しいな・・・
スポンサーサイト


アルゴリズム | 【2009-03-08(Sun) 15:59:32】 | Trackback:(0) | Comments:(0)
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。