【アルゴリズム】【Ruby】ソートのいろいろ ～むちゃ遅いクイックソート

計算量って知ってる？
バブルソートって遅いよねっていうのは、
エクレアってデザートよねってくらいに常識かな。。ほんまに。

っていう師匠からの小言に対処すべく、
アルゴリズムを分かろう：その２、スタートです。

詳細はこちら

クイックソートとは

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

http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88

よし。実装してみよう

いけてないコード

実装してみたものの、ありえないくらい処理が遅い。
コードも複雑で、いけてない感ぷんぷん。

a = (0..10).to_a
a = a.sample(a.length)
p a
start_time = Time.now

def q_sort(a, pipot=nil)
    return a if a.size == 1
    if pipot == nil then
        pipot = a[a.size/2.ceil]
    end
    i = 0
    while i < a.size
        if a[i] >= pipot then
            j = a.size-1
            while j >= 0
                if a[j] <= pipot then
                    if i < j then
                        a[i], a[j] = a[j], a[i]
                        if i +1 == j then
                            a[0...i] = q_sort(a[0...i])
                            a[i...a.size] = q_sort(a[i...a.size])
                        else
                            q_sort(a[i+1 ... j-1], pipot)
                        end
                    else
                        a[0...i] = q_sort(a[0...i])
                        a[i...a.size] = q_sort(a[i...a.size])
                    end
                end
                j -= 1
            end
        end
        i += 1
    end
    a
end

q_sort(a)
end_time = Time.now
p a
p ("timeee " + (end_time - start_time).to_s + "s" )

■実行結果

[0, 10, 8, 1, 3, 9, 2, 4, 5, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"timeee 38.522204s"

やっば。まじやっば。。
10個のソートに３８秒って一体。。。

アルゴリズムって作った人の知性を如実に反映するね･･･

まあでも頑張ったので、師匠にコードを送ってみた。

ごめんなさい、このこーどを読む気がおきません。。。
てか、３８秒って遅すぎる

38秒が遅いって、そりゃ私でも分かるわ！
コードがイケてないのは私が1番知ってるわ！

って、師匠に怒るのは間違いです。
自分の知能の至らなさが本質なのです。

Wikiの答え

wiki のサンプルを見てRubyで実装してみる

a = (0..10).to_a
a = a.sample(a.length)
p a
start_time = Time.now

def q_sort(a, left, right)
  return a if left >= right
  
  pivot = a[((left + right).to_f/2.to_f).ceil]
  i = left
  j = right

  while true
    i += 1 while a[i] < pivot
    j -= 1 while a[j] > pivot
    
    break if (i >= j)
    a[i], a[j] = a[j], a[i]
    i += 1
    j -= 1
  end
  q_sort(a, left, i-1)
  q_sort(a, i, right)
  a
end

q_sort(a,0,a.size - 1)
end_time = Time.now

p a
p ("timeee " + (end_time - start_time).to_s + "s" )

■実行結果

[0, 5, 9, 2, 10, 1, 3, 4, 7, 8, 6]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"timeee 0.0s"

やばい！
３８秒⇒０秒に！

何がいけてなかったのか

自分のコードのどこがいけてなかったのか考察してみる

while文がいけてない

 while i < a.size
  if a[i] >= pipot then

これ、一文で書ける。ネストが浅くなる。

while  a[i] < pipot

while文は使いなれてない。ちゃんと慣れよう。。

メモリを使いまくってた

def q_sort(a, pipot=nil)
･･･
q_sort(a[i...a.size])
q_sort(a[i+1 ... j-1], pipot)

とか書いてた。
これって、配列を部分的に取り出すたび、
新しい配列を作成しているので、恐ろしくイケテない処理になってる。

クイックソート終わり。。
の前に
公式ガイド：制御構造をちゃんと理解する。