ページ

2014/04/05

勉強:クイックソートとは？

クイックソートとは、データをソート（整列・並び替え）するアルゴリズムの一種です。

名前の通り「並び替えが早い」アルゴリズムです。
※全てにおいて早いわけではないそうです。

アルゴリズム

  1. 適当な数（ピボット:pivot）を選択する。（データ総数の中央値が望ましい）
  2. ピボットより小さい数を前方、大きい数を後方に移動させる（分割）
  3. 二分割されたデータをそれぞれソートする。

一例

  1. ピボットとして一つ選びそれをPとする。
  2. 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
  3. 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
  4. iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3ではjの一つ左から行う。
  5. 2に戻らなかった場合、iの左側を境界に分割を行って二つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が一以下の領域ができた場合、その領域は確定とする。

参考サイト様がとてもわかりやすかったので、自分なりにまとめてみました。
以下のような数列データがあるとします。

5 14 10 15 13 4 2 7 19 12

まず、この10個の要素の中からピボットを選択します。
中央値（(開始位置+終了位置)/2）をピボットとします。
このデータの場合は以下の様になります。
(0+9)/2=4（小数点切り捨て）
4番目の要素「13」をピボットとします。

5 14 10 15 13 4 2 7 19 12

データの先頭からピボット以上のデータを探します。
データの末尾からピボット以下のデータを探します。
その値があれば、その値同士を交換していきます。
そして、先頭と末尾の探索が交差するまでこの操作を続けます。

それでは先頭から探索します。

5 14 10 15 13 4 2 7 19 12

5は13以上ではないので次へ

5 14 10 15 13 4 2 7 19 12

14は13以上なので、交換する要素です。
次は末尾から探索します。

5 14 10 15 13 4 2 7 19 12

12は13以下なので、交換する要素です。
それでは交換しましょう。

5 12 10 15 13 4 2 7 19 14

交差するまでこの処理を続けます。

 5 12 10 15 13 4 2 7 19 14　10は13以上ではないので次へ
5 12 10 15 13 4 2 7 19 14　15は13以上なので、交換する要素です。
5 12 10 15 13 4 2 7 19 14　19は13以下ではないので次へ
5 12 10 15 13 4 2 7 19 14　7は13以下なので、交換する要素です。
5 12 10 7 13 4 2 15 19 14　交換

5 12 10 7 13 4 2 15 19 14　ピボットである13が交換要素になりました。
5 12 10 7 13 4 2 15 19 14　2は13以下なので、交換する要素です。
5 12 10 7 2 4 13 15 19 14　交換

5 12 10 7 2 4 13 15 19 14　13は13以上なので、交換する要素です。
5 12 10 7 2 4 13 15 19 14　13は13以下なので、交換する要素です。

13が交換する要素になりますが、先頭と末尾が交差したので処理を終了します。

ピボットを軸として左右に要素を分割します。

5 12 10 7 2 4 13 15 19 14

そして左右別々に再帰的にソートを行います。
これを繰り返して、整列すべきデータ数列が一つになるまで行えば、昇順にソートされます。
▼　左側から
　　5 12 10 7 2 4
　　Pivot = (0+5)/2 = 2
　　2番目の要素「10」をピボットとします。
　　5 12 10 7 2 4
　　
　　5 12 10 7 2 4　5は10以上ではないので次へ
　　5 12 10 7 2 4　12は10以上なので交換する要素
　　5 12 10 7 2 4　4は10以下なので交換する要素
　　5 4 10 7 2 12　交換
　　5 4 10 7 2 12　10は10以上なので交換する要素
　　5 4 10 7 2 12　2は10以下なので交換する要素
　　5 4 2 7 10 12　交換
　　5 4 2 7 10 12　交差したので終了
　　
　　5 4 2 7 10 12　分割
　　▼　左側から
　　　　5 4 2 7
　　　　Pivot = (0+3)/2 = 1
　　　　1番目の要素「4」をピボットとします。
　　　　5 4 2 7
　　　　
　　　　5 4 2 7　5は4以上
　　　　5 4 2 7　2は4以下
　　　　2 4 5 7　交換
　　　　2 4 5 7　交差したので終了
　　　　
　　　　2 4 5 7　分割
　　　　▼　左側
　　　　　　2　要素数1なので終了
　　　　▼　右側
　　　　　　5 7
　　　　　　Pivot = (0+1)/2 = 0
　　　　　　0番目の要素「5」をピボットとします。
　　　　　　5 7
　　　　　　5 7　交差したので終了

　　左側の探索が終了して「2 4 5 7」となりました。
　　▼　右側
　　　　12　要素数1なので終了
　　　　
　　　　左側の探索が終了して「2 4 5 7 10 12」となりました。
▼　右側
　　13がピボットの時の右側を探索

　　15 19 14
　　Pivot = (0+2)/2 = 1
　　1番目の要素「19」をピボットとします。
　　15 19 14
　　15 19 14　15は19以下なので次へ
　　15 19 14　19は19以上
　　15 19 14　14は19以下
　　15 14 19　交換
　　
　　15 14 19　分割　ピボットである19の右側には要素がないので右側は終了
　　▼　左側
　　　　15 14
　　　　Pivot = (0+1)/2 = 0
　　　　0番目の要素「15」をピボットとします。
　　　　15 14
　　　　15 14　15は15以上
　　　　15 14　14は15以下
　　　　14 15　交換　交差したので終了
　　　　
　　右側の探索が終了して「14 15 19」となりました。

左右すべての探索が終了しました。
結果「2 4 5 7 10 12 13 14 15 19」と昇順にソートされました。


Javaのプログラムは以下の様な形になりました。

public class quick_sort {
    static void quickSort(int[] a, int left, int right) {
        /*  クイックソート
         *  a       : 要素配列      p   :   ピボット(データ中央値)
         *  left    : 開始位置      i   :   左側の配列位置
         *  right   : 終了位置      j   :   右側の配列位置
         */
        int i=left, j=right, t, p=a[(i+j)/2];
        while(true) {
            while(a[i] < p) i++;    // ピボット以上の値を先頭から探索
            while(p < a[j]) j--;    // ピボット以下の値を末尾から探索
            if(i>=j)break;          // 探索位置i,jが交差したら終了
            t=a[i];a[i]=a[j];a[j]=t; // 左右の値を交換
            i++; j--;               // 探索位置を1つずらす
        }
        // 分割
        // 左側を再帰的にソート
        if(left < i-1){ quickSort(a, left, i-1); }
        // 右側を再帰的にソート
        if(j+1 < right){ quickSort(a, j+1, right); }
    }
    
 public static void main(String[] args) {
        int[] a = {8, 10, 4, 14, 7, 5, 2, 1, 11, 13};
        quickSort(a, 0, a.length-1);
        for(int i:a) {
            System.out.print(i+" ");
        }
        System.out.println();
 }
}

投稿者 時刻:
ラベル: ,

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)