Ruby クイックソート

クイックソートとは

他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではない。また数々の変種がある。 安定ソートではない。[wikipedia引用]

アルゴリズム

1. 適当な数（ピボットという）を選択する（この場合はデータの総数の中央値が望ましい）

2. ピボットより小さい数を前方、大きい数を後方に移動させる （分割）

3. 二分割された各々のデータを、それぞれソートする

実際にこれを実現するためのアルゴリズムは色々考えられるが、一例を挙げると以下のようなものがある。

1. ピボットとして一つ選びそれをPとする。

2. 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。

3. 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。

4. iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。

5. 2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。

[wikipedia引用]

実装

Ruby のソートメソッドは、クイックソートを使っている。

当然だが、今回はsortメソッドを使わない。

def med3(x, y, z)
    if x < y
        if y < z
            return y
        elsif z < x
            return x
        else
            return z
        end
    else
        if z < y
            return y
        elsif x < z
            return x
        else
            return z
        end
    end
end

# /* クイックソート
#  * a     : ソートする配列
#  * left  : ソートするデータの開始位置
#  * right : ソートするデータの終了位置
#  */
def quicksort(a, left, right)
    if left < right
        i, j = left, right
        pivot = med3(a[i], a[i + (j - i) / 2], a[j])
        while true
            while a[i] < pivot do
                i+=1
            end
            while pivot < a[j] do
                j-=1
            end
            break if i >= j
            tmp = a[i]
            a[i] = a[j]
            a[j] = tmp
            i+=1
            j-=1
        end
        quicksort(a, left, i - 1)
        quicksort(a, j + 1, right)
    end
end

arr=[3,25,5,2,24,5,1]
quicksort(arr, 0, arr.length-1)
p arr

<出力結果>

[1, 2, 3, 5, 5, 24, 25]

無事、ソートされているのが確認できました。

乱数を使ってテストするとこんな感じです

class QuickSort
    def initialize(n)
        @target = Array.new(n)
    end


    def main
        puts "準備中"


        @target.each_index do |i|
            @target[i] = rand(1000)
        end
        p @target


        puts "クイックソート開始"
        quickSort(@target, 0, N-1)
        puts " 終了"
        p @target
    end
    
    private
    def med3(x, y, z)
        if x < y
            if y < z
                return y
            elsif z < x
                return x
            else
                return z
            end
        else
            if z < y
                return y
            elsif x < z
                return x
            else
                return z
            end
        end
    end
    
    def quickSort(a, left, right)
        if left < right
            i, j = left, right
            pivot = med3(a[i], a[i + (j - i) / 2], a[j])
            while true
                while a[i] < pivot do
                    i+=1
                end
                while pivot < a[j] do
                    j-=1
                end
                break if i >= j
                tmp = a[i]
                a[i] = a[j]
                a[j] = tmp
                i+=1
                j-=1
            end
            quickSort(a, left, i - 1)
            quickSort(a, j + 1, right)
        end
    end
end


N = 10
quick = QuickSort.new(N)
quick.main

<実行結果>

乱数で準備中
[779, 386, 633, 866, 864, 252, 709, 890, 248, 980]
クイックソート開始
終了
[248, 252, 386, 633, 709, 779, 864, 866, 890, 980]

バッチリ！！以上！！！