2020/11/14

アルゴリズム3

Ruby

こんにちは、kazutoです。アルゴリズムシリーズ第3弾です。前回は、基本的なソートアルゴリズム、3つを実際にソースコードに置き換えていきました、今回は、応用的なソートアルゴリズム、4つを実際にソースコードに置き換えていきます。

ソートとは

ソートとは、データの集合を一定の規則に従って並べることです。日本語では、整列、並べ替え、という意味を持ちます。

具体的な例を挙げると

• 社員IDの主キーを基準に降順に並べる
• 配列の中に格納された数字を昇順に並べ替える
• ○年✖︎✖︎組の通信簿を名前順に並び替える

とかです。

要するにデータの並び順に規則性を持たせて、綺麗に並び替えるという事ですね。

マージソート

マージソートとは、整列されていないリストを2つのリストに分割して、それぞれを整列させた後、それらをマージして整列済みのひとつのリストを作る整列アルゴリズムです。文字だけの解説では理解できないと思うので、下記の動画を参照してみてください。

フローチャートを確認しよう

マージソートの特徴を抑えた所で、マージソートをフローチャートで表現をしていきましょう。

上記がマージソートのフローチャートです。「アルゴリズム2」で取り上げた、基本的なソートアルゴリズム と比較すると、とても複雑になりましたね。マージソートは、フローチャートでは、複雑に見えますが、ソースコードに置き換える事自体は、あまり難しくありません。

コードに置き換えよう

フローチャート を確認をした所で、実際にソースコードに置き換えていきましょう。

def merge_sort(array)
  count = array.length
  return if count <= 1
  center = count / 2

  left_data  =array.slice(0,center)
  right_data =array.slice(center,array.length-1)

  merge_sort(left_data)
  merge_sort(right_data)

  merge_data = []

  count1 = left_data.length
  count2 = right_data.length

  i = 0
  j = 0

  while i < count1 && j < count2
    value1 = left_data[i]
    value2 = right_data[j]
    if value1 <= value2
      merge_data.push(left_data[i])
      i+=1
    else
      merge_data.push(right_data[j])
      j+=1
    end
  end

  while i < count1
    merge_data<<left_data[i]
    i+=1
  end

  while j < count2
    merge_data<<right_data[j]
    j+= 1
  end

  k = 0
  while k < merge_data.length
    array[k] = merge_data[k]
    k += 1
  end
  p array
end
array =[2,3,45,5,1,3,5,21,12,23]
merge_sort(array)
puts array
#ソート前:[2, 3, 45, 5, 1, 3, 5, 21, 12, 23]
#ソート後:[1, 2, 3, 3, 5, 5, 12, 21, 23, 45]

それでは、解説していきます。

 count = array.length

まず、初めにcountという変数に配列の長さを格納します。この変数を定義をする事で、”array.length”と記述せずに、countと入力するだけで、配列の要素を取得できます。

return if count <= 1

変数countを定義した直下に、配列の要素数が1未満な場合と条件を提示をし、returnメソッドを用いて、強制終了をします。マージソートは、配列の要素を限界まで分割していき、そこから、要素の大小を比較してマージ(併合)をしてソートをしていきます。配列の要素数が1だった場合は、分割できないですよね？
したがって、配列の要素数が1未満な場合は、以降の処理を実行させずに強制終了をして矛盾を防ぎます。

center = count / 2
left_data  =array.slice(0,center)
right_data =array.slice(center,array.length-1)

配列の要素数が複数ある場合は、sliceメソッドを用いて、配列を2分割していきます。
変数left_dataには、中央値から下限値までの範囲の要素を格納、変数right_dataには、中央値から上限値までの範囲の要素を格納をします。

merge_sort(left_data)
merge_sort(right_data)

そして、分割して新たに作成した配列を引数にメソッド内で、同メソッドを呼び出します。同メソッドを呼び出す事で、連続して同じ処理を繰り返します。注意点として処理される順番は、最後に呼び出されたメソッドから順に実行されます。要するに要素数が少ない順からソート(マージ)をしていきます。

count1 = left_data.length
count2 = right_data.length

次に各配列の長さを取得をして変数に格納していきます。

i = 0
j = 0

ループ処理の準備を行います。今回は、変数iと変数jは、お互いに独立をしてループ処理を組み立てて、いきます。

while i < count1 && j < count2
    value1 = left_data[i]
    value2 = right_data[j]
    if value1 <= value2
      merge_data.push(left_data[i])
      i+=1
    else
      merge_data.push(right_data[j])
      j+=1
    end
  end

次に分割したデータをマージ（併合）していきます。

while i < count1 && j < count2
end

まず、while文の条件式を確認をしていきます。
条件内容を言語化すると、変数iの値が、count1より小さい限りで且つ変数jの値がcount2 より小さい限り繰り返すという内容になります。count1とcount2には、各配列の要素数が格納されています。したがって、どちらかの配列の要素の数だけ繰り返し処理が行われたら、ループ処理を抜けるという事になります。

value1 = left_data[i]
value2 = right_data[j]

次にリアルタイムの配列の要素数をそれぞれ変数に格納します。

if value1 <= value2
   merge_data.push(left_data[i])
   i+=1
else
   merge_data.push(right_data[j])
   j+=1
end

今回は、小さい数から順に並べていきたいので、value1 <= value2という条件の時に変数left_dataの要素をpushメソッドを用いて、変数merge_dateに入れて、条件に該当しない場合は、変数right_dataの要素をpushメソッドを用いて、変数merge_dateに入れます。その後、各変数の値を更新をします。

while i < count1 && j < count2
end

この一連の流れを行えば、ソートする事が可能ですが、while文の条件に変数iの値が、count1より小さい限りで且つ変数jの値がcount2 より小さい限り繰り返すという条件を提示をしている関係上、どちらかの変数は、配列の要素数より値が少ない状態でループ処理を抜けてしまい、全ての要素を変数marge_dataの中に格納できていない状態です。このままですと、ソートは、できている物の、要素数が足りない状況に陥ってしまいます。したがって、配列の要素数より値が少ない状態でループ処理を抜けた変数に対して再度、繰り返し処理を組みます。

 while i < count1
    merge_data<<left_data[i]
    i+=1
  end

  while j < count2
    merge_data<<right_data[j]
    j+= 1
  end

先ほどの解説の通り、再度、繰り返し処理を組みます。なお、if文と同様に条件に該当しなければ、無視されるので、起こり得る可能性を配慮した結果、上記の様に繰り返し処理を2つ組みました。この2つの繰り返し処理を組み込む事によって、端数を無くすことができます。

while i < count1
    merge_data<<left_data[i]
    i+=1
end

こちらは、変数iの値が配列の長さより小さい場合に処理が発火します。

 while j < count2
    merge_data<<right_data[j]
    j+= 1
  end

こちらは、変数jの値が配列の長さより小さい場合に処理が発火します。

k = 0
while k < merge_data.length
    array[k] = merge_data[k]
    k += 1
  end

最後に、変数merge_dataの要素を変数arrayに入れ直します。この作業を行う事で、マージしたデータ(配列)を引き継いだ状態で、連鎖的に配列操作(ソート)を行う事ができる様になります。

この一連の流れを繰り返す事で、マージソートを実現ができます。ポイントは、メソッドが呼び出される回数と処理を行う順番を把握をしておく事ですね。特に処理が行う順番がわからないと「何をしているかわからない状態」に陥ってしまいます。なので、どの順番で処理が実行されるかを抑えて、実装していきましょう。

以上で、マージソートの解説を終了します。マージソートは、分割=>併合の流れがわかれば、理解ができると思います。

クイックソート

クイックソートとは、ピボット(基準値)を決めて、それより大きい値のグループと小さい値のグループに分け、繰り返して並び替える整列アルゴリズムです。また、ソートアルゴリズムのなかで最も高速なアルゴリズムです。文字だけの解説では理解できないと思うので、下記の動画を参照してみてください。

フローチャートを確認しよう

クイックソートの特徴を抑えた所で、クイックソートをフローチャートで表現をしていきましょう。

上記がクイックソートのフローチャートです。

コードに置き換えよう

フローチャート を確認をした所で、実際にソースコードに置き換えていきましょう。

def get_random_arbitraty(min,max)
  rand(min..max)
end

def quick_sort(start_id,end_id,array)

  random = get_random_arbitraty(start_id,end_id)
  pivot = array[random]
  left  = start_id
  right = end_id

  puts "piyvot:#{pivot}"
  p array
  while true

    while array[left] < pivot
      left += 1
    end

    while pivot < array[right]
      right -= 1
    end

    if right <= left
      break
    else
      temp = array[right]
      array[right] = array[left]
      array[left] = temp
      left += 1
      right -= 1
    end
  end

  if start_id < left - 1
    quick_sort(start_id,left-1,array)
  end

  if right+1 < end_id
    quick_sort(right+1,end_id,array)
  end

end
array =[2,3,45,5,1,3,5,21,12,23]
quick_sort(0,array.length,array)
puts array
#ソート前:[2, 3, 45, 5, 1, 3, 5, 21, 12, 23]
#ソート後:[1, 2, 3, 3, 5, 5, 12, 21, 23, 45]

それでは、解説をしていきます。

def get_random_arbitraty(min,max)
  rand(min..max)
end
random = get_random_arbitraty(start_id,end_id)

まず初めに、get_random_arbitratyメソッドを呼び出して、乱数を生成をし、変数randomに格納します。変数random xを用いて、クイックソートの根幹を担うピボットを決めます。

 pivot = array[random]

次にピボットを生成をします。ピボットは、配列の中から適当な値を取得をして基準値にします。一見、ソートができなそうですが、フローチャート通り実装していけば、問題なくソートができます。

left  = start_id
right = end_id

配列操作する範囲を決めます。マージソートと同様、メソッドの中で同メソッドを呼び出す関係上、上記の2つの変数は、動的に値が変わっていきます。なので、必ずしも同じ値とは限らないので注意をしてください。

 while true
    while array[left] < pivot
      left += 1
    end

    while pivot < array[right]
      right -= 1
    end

    if right <= left
      break
    else
      temp = array[right]
      array[right] = array[left]
      array[left] = temp
      left += 1
      right -= 1
    end
  end

次に、実際にピボットを基準にして、右辺の値と左辺の値を入れ替える処理を実装をしていきましょう。

while true
end

今回は、trueな限り繰り返すという条件で繰り返し処理を組みました。 なお繰り返し処理を止める条件については、スコープ内で記述をしていくので気にしないでください。

 while array[left] < pivot
      left += 1
end

こちらは、配列の要素がピボット(基準値)より大きい限り繰り返すという条件をwhile文に設定しております。要するに、左から右に線形探索をしていき、ピボットより大きい値が見つかったら、ループを抜けるという事です。この様に条件を組んだ理由は、ピボットより左辺は、小さい数である事が望しいからです。今回のピボットソートでは、小さい数から順に並び替えていきます。したがって、ピボットより左辺が小さい数で並んでいる状態である事がクイックソートを実装する上で外せないポイントになります。

while pivot < array[right]
      right -= 1
 end

こちらは、配列の要素がピボット(基準値)より小さい限り繰り返すという条件をwhile文に設定しております。要するに、右から左に線形探索をしていき、ピボットより大きい値が見つかったら、ループを抜けるという事です。この様に条件を組んだ理由は、ピボットより右辺は、大きい数である事が望しいからです。今回のピボットソートでは、小さい数から順に並び替えていきます。したがって、ピボットより右辺が、大きい数で並んでいる状態である事がクイックソートを実装する上で外せないポイントになります。

上記、2つの繰り返し処理が止まるという事は、まだ、ソートができていない状態で矛盾が発生しています。したがって、矛盾を改善するために右辺と左辺の値を入れ替えていきましょう！！

if right <= left
      break
    else
      temp = array[right]
      array[right] = array[left]
      array[left] = temp
      left += 1
      right -= 1
    end

次に右辺と左辺を入れ替える処理について解説をしていきます。

if right <= left
   break
else   
end

こちらは、leftの値ががrighの値以上の場合と条件を提示をしています。条件に該当する場合は、breck文でループを抜けます。right <= leftの場合、つまり、右辺と左辺の関係が崩れている事が確認できます。このまま繰り返し処理を継続をしてしまいますと、せっかく、ピボットを軸にして並び替えた、配列をグチャグチャにしてしまいます。なので、上記の様な条件を組み、右辺と左辺の関係性が崩れる前にループ処理を止めます。

else   
      temp = array[right]
      array[right] = array[left]
      array[left] = temp
      left += 1
      right -= 1
end

条件に該当しない場合は、右辺と左辺の関係性が崩れていない状態ですが、

左辺 < pibot < 右辺

上記の様な関係を実現できていない状態とも考えられますので、右辺と左辺の値を入れ替える必要があります。

 temp = array[right]
 array[right] = array[left]
 array[left] = temp

こちらの記述で、右辺と左辺の値を入れ替ています。

 left += 1
 right -= 1
end

入れ替え終わったら、leftに1を足して、rightには-1を引きましょう。この記述を忘れると、無限ループに陥ってしまいますので、忘れずに記述をしてください。

if start_id < left - 1
    quick_sort(start_id,left-1,array)
  end

こちらは、start_idの値よりleftに1を引いた値の方が大きい場合と条件を提示をしています。start_idの値が、left-1を引いた値の方が大きい場合、つまり、要素が2つ以上あり、比較できる状態であれば、quick_sortメソッドを呼び出し、再度、処理を繰り返すという事です。

if right+1 < end_id
  quick_sort(right+1,end_id,array)
end

こちらも、同様です。end_idの値よりrightに1を足した値の方が小さい場合と条件を提示をしています。end_idの値が、rightに1を足した値の方が小さい場合、つまり、要素が2つ以上あり、比較できる状態であれば、quick_sortメソッドを呼び出し、再度、処理を繰り返すという事です。

少し複雑でわかりづらいと思うので、処理のアウトラインを解説をします。

まず、配列全体に対してquick_sortメソッドを呼び出し、ピボットを決めて、　

• 小さいグループ
• 大きいグループ

に分けます。その後、

• 小さいグループ
• 大きいグループ

に対して、再度、quick_sortメソッドを呼び出し、ピボットを決めていき、更にグループ分けをしていきます。この手順をグループ分けできなくなるまで繰り返していきます。最終的に、グループ分けができなくなった段階で処理は停止して、結果的にソートされた状態になるというロジックです。

以上で、クイックソートの解説は終了になります。クイックソートに関しては、問題を分割して考えていく、分割統治法という問題解決の手法を用いていけば、大枠は理解ができると思います。

※分割統治方とは
そのままでは、解決が難しい場合に用いられる問題解決手法。大きい問題を分割をして、小さい問題に切り離し、小さい問題を解決する事で、大きい問題を解決をしていく。

ヒープソート

ヒープソートとは、リストの並べ替えを二分ヒープ木を用いて行う整列アルゴリズムです。文字だけの解説では理解できないと思うので、下記の動画を参照してみてください。

フローチャートを確認しよう

ヒープソートの特徴を抑えた所で、ヒープソートをフローチャートで表現をしていきましょう。

コードに置き換えよう

フローチャート を確認をした所で、実際にソースコードに置き換えていきましょう。

def heap_sort(array)
  array_size = array.length
  i = (array_size-1)/2
  while i >= 0
    max_int(array,i,array_size-1)
    i-=1
  end
  temp = 0
  i = array_size-1
  while i > 0
    temp = array[0]
    array[0]=array[i]
    array[i] = temp
    max_int(array,0,i-1)
    i-=1
  end
end

def max_int(array,root,bottom)
  child = 2*root+1
  temp = array[root]
  while child <= bottom
    if child < bottom && array[child+1] > array[child]
      child += 1
    end
    if temp > array[child]
      break
    elsif temp <= array[child]
      array[(child-1)/2] = array[child]
      child = 2*child+1
    end
      array[(child-1)/2] = temp
  end
end

array =[2,3,45,5,1,3,5,21,12,23]
heap_sort(array)
puts array
#ソート前:[2, 3, 45, 5, 1, 3, 5, 21, 12, 23]
#ソート後:[1, 2, 3, 3, 5, 5, 12, 21, 23, 45]

それでは、解説をしていきます。

 array_size = array.length

まずは、配列の要素数を取得をして、変数array_sizeに格納をしていきましょう。

i = (array_size-1)/2

次に、変数iに配列の中央値を格納していきます。ヒープソートは、ヒープを構築してから条件に応じて並び替えていきます。まずは、array_size-1/2、つまり配列の最後の要素の親ノードからループ処理を組める様に準備をします。

なお、親ノードと子ノードの対応関係は下記の表の通り求める事ができます。

こちらの表の計算式はこれから実装していく上で活用していくので、必ず頭の中に入れておいてください。この計算式が抜けてしまうと、全く理解ができなく終わってしまうので。

while i >= 0
  max_int(array,i,array_size-1)
  i-=1
end

こちらは、変数iが０以上な限り繰り返すという条件を提示をしています。変数iの初期値は、配列の最後の要素の親ノードの添字です。したがって、一番、階層が低い親ノードから子ノードと比較をしていく事になります。i-=1という事からも、徐々に階層を上げて比較していく事がわかると思います。

def max_int(array,root,bottom)
  child = 2*root+1
  temp = array[root]
  while child <= bottom
    if child < bottom && array[child+1] > array[child]
      child += 1
    end
    if temp > array[child]
      break
    elsif temp <= array[child]
      array[(child-1)/2] = array[child]
      child = 2*child+1
    end
      array[(child-1)/2] = temp
  end
end

max_int(array,i,array_size-1)

次に一度、heapメソッドを離れ、max_intメソッドの中身を見ていきましょう。

child = 2*root+1

こちらの記述で、変数rootに対応する子ノードの添字を取得をしています。正確には左側の子ノードの添字です。このchildという変数を起点にして、並び替えていきます。

temp = array[root]

次に親ノードを「仮置き箱」に一時的に格納をしておきます。

while child <= bottom
    if child < bottom && array[child+1] > array[child]
      child += 1
    end
    if temp > array[child]
      break
    elsif temp <= array[child]
      array[(child-1)/2] = array[child]
      child = 2*child+1
    end
      array[(child-1)/2] = temp
 end

では、ヒープソートの根幹部分について解説をしていきます。

while child <= bottom
end

こちらは、配列の要素数が子ノードの添字以上な限り繰り返すという条件を提示をしています。子ノードの添字が配列の要素数より大きい数字になってしまいますと、以降の処理で、エラーが発生してしまいます。(比較演算子を用いて条件分岐をしているため)

if child < bottom && array[child+1] > array[child]
      child += 1
end

少し条件式が複雑に見えますね。言語化すると、配列の要素数が子ノードの添字より大きい且つ右側の子ノードが左側の子ノードより大きい場合という条件になります。つまり、何がしたいかというと、右側の子ノードと左側の子ノードの比較です。

右<左＜親

という関係にしたいので、上記の条件式を組みました。

 child += 1

条件に該当する場合は、つまり、右側の子ノードが左側の子ノードより大きい場合、変数childの値に1を足します。要するに変数childに格納されている値が左側の子ノードから右側の子ノードに変わった事を意味します。

if temp > array[child]
      break
elsif temp <= array[child]
      array[(child-1)/2] = array[child]
      child = 2*child+1
end

次に実際に親ノードと子ノードを入れ替える処理を解説をしていきます。

if temp > array[child]
   break
end

こちらは、親ノードが子ノードより大きい場合と条件を提示をしています。条件に該当する場合は、親子関係が成立をしている事を指すので、breck文を用いて、ループを抜けます。

elsif temp <= array[child]
      array[(child-1)/2] = array[child]
      child = 2*child+1
end

先ほど提示した条件に該当しない場合は、elsif文が読み込まれます。子ノードが親ノード以上な場合と条件を提示をしています。elsif文の条件に該当する場合は、親子関係が成立していない事を指すので、親ノードと子ノードを入れ替えていきます。

array[(child-1)/2] = array[child]

array[(child-1)/2]、つまり、親ノードを指します。したがって、親ノードに子ノードの値を代入をして上書きしています。

child = 2*child+1
end

2*child+1、つまり、変数child に対して、子ノードの子ノードを格納しています。この記述により、入れ替えた、親ノードと孫ノードを更に比較していく事が可能になります。

#（child = 2*child+1）をした事を忘れずに！！
array[(child-1)/2] = temp

elsif文のスコープを抜けたら、array[(child-1)/2]、つまり、子ノードに親ノードを格納して上書きをしています。一見、array[(child-1)/2]という記述なので、「親ノード?」と疑問を持つと思います。しかし、一つ前の処理で、変数childの値を孫ノードに上書きしています。したがって、孫ノードの親は、子ノードになるので、array[(child-1)/2]は、子ノードである事が証明できます。

以上で、max_intメソッドのロジックの解説は終了になります。heap_sortメソッドに戻りましょう。

i = array_size-1
while i > 0
    temp = array[0]
    array[0]=array[i]
    array[i] = temp
    max_int(array,0,i-1)
    i-=1
end

先程までは、ヒープを構築するまでの解説になります。次の段階では、実際にヒープから、最大値を見つけて、ソートされていない配列の末尾と入れ替えていきソートしていきます。

i = array_size-1

まずは、繰り返し処理を行う前に変数iを初期化をしていきます。今回のループ処理では、配列操作する範囲を末尾から徐々に狭めていきたいです。したがって、変数iの初期値は、配列の要素数になります。

while i > 0
    temp = array[0]
    array[0]=array[i]
    array[i] = temp
    max_int(array,0,i-1)
    i-=1
end

　次に、繰り返し処理の中身を見ていきましょう。

while i > 0
end

こちらは、変数iが0より大きい限り繰り返すという条件を提示をしています。先程、解説した通り、配列操作する範囲を末尾から徐々に狭めていきたいです。なので、１ループごとにiに1を引いて実現をしていきます。

temp = array[0]
array[0]=array[i]
array[i] = temp

こちらの記述で、配列の先頭とソートされていない配列の末尾を入れ替えていき、ソートしていきます。

 max_int(array,0,i-1)
 i-=1

max_intメソッドを呼び出します。なおmax_inメソッドの解説は先程、解説したので省略させていただきます。まあ、最大値を見つけて、配列の先頭に持ってくると理解しておけば問題ないです。

以上で、ヒープソートの解説を終了します。配列を木構造に見立てて、考えるの難しく感じると思いますが、紙などに書き出して状況を整理をすれば、「なるほど」と思いますので頭を柔らかくして考えてみましょう。

シェルソート

シェルソートとは、挿入ソートの上位互換のアルゴリズムです。具体的には、まず、間隔の離れた要素の組に対してソートを行います。その後、徐々に間隔を狭めていき、最終的に通常の挿入ソートを行い、ソートします。文字だけでは理解できないと思うので、下記の動画を参照してみてください。

フローチャートを確認しよう

シェルソートの特徴を抑えた所で、シェルソートをフローチャートで表現をしていきましょう。

コードに置き換えよう

フローチャート を確認をした所で、実際にソースコードに置き換えていきましょう。なお今回は、挿入する間隔を(4,2,1)という前提で処理を実装していきます。

def shell_sort(array)
  n = array.length-1
  h = 1
  while h <= n/9
    h = 3*h + 1
  end
  while h > 0
    for i in (h..n) do
      temp = array[i]
      if temp < array[i-h]
        j = i
        while true
          array[j] = array[j-h]
          j-=h
          break  if j<h || temp >= array[j-h]
        end
        array[j] = temp
      end
    end
    h = h/2
  end
end

array =[2,3,45,5,1,3,5,21,12,23]
shell_sort(array)
puts array
#ソート前:[2, 3, 45, 5, 1, 3, 5, 21, 12, 23]
#ソート後:[1, 2, 3, 3, 5, 5, 12, 21, 23, 45]

それでは、解説をしていきます。

 n = array.length-1
 h = 1

変数nには、配列の要素数を格納し、変数hを1を代入をします。

while h <= n/9
  h = 3*h + 1
end

次に、変数nを９で割った和が変数h以上な限り繰り返すと条件を提示をします。要するにシェルソートをする必要があるかを判定をします。配列の要素数が少ない状態でシェルソートを行っても、あまりメリットがないので、条件に該当しない場合は、挿入ソートのみでソートをしていきます。

while h > 0
    for i in (h..n) do
      temp = array[i]
      if temp < array[i-h]
        j = i
        while true
          array[j] = array[j-h]
          j-=h
          break  if j<h || temp >= array[j-h]
        end
        array[j] = temp
      end
    end
    h = h/2
  end

では、シェルソートに根幹部分を解説をしていきます。

while h > 0
end

こちらは、変数hが0より大きい限り繰り返すという条件を提示をしていきます。なお、変数hは挿入する間隔を表します。つまり、この条件に該当しなくなったらソートが完了した事になります。

for i in (h..n) do
   temp = array[i]
   if temp < array[i-h]
      j = i
      while true
        array[j] = array[j-h]
        j-=h
        break  if j<h || temp >= array[j-h]
      end
      array[j] = temp
   end
end

次にfor文の中身をみていきましょう。

for i in (h..n) do
end

まずは、(h..n)は、範囲オブジェクトです。この処理を言語化すると、h〜nまで繰り返すとなります。変数hは、挿入する間隔を表し、変数nは、配列の要素数を格納しています。したがって、配列の要素数まで、挿入する間隔をずらす事で、挿入ソートを行う、組み合わせを１ループごとに１つずらしています。

temp = array[i]

変数tempに挿入する要素を一時的に格納しておきます。

if temp < array[i-h]
  j = i
  while true
    array[j] = array[j-h]
    j-=h
    break  if j<h || temp >= array[j-h]
  end
  array[j] = temp
end

次に、実際に挿入ソートを行う記述を解説をしていきます。

if temp < array[i-h]
  j = i
end

こちらは、挿入済みの要素が挿入する要素より大きい場合と条件を提示をしています。今回は、先頭から小さい順に並べていきたいです。なので、挿入済みの要素が挿入する要素より大きい場合に要素を入れ替えていきます。したがって、変数jに変数i(挿入する要素の添字)を格納をしています。

while true
    array[j] = array[j-h]
    j-=h
    break  if j<h || temp >= array[j-h]
end

では、実際に値を入れ替えていく処理を見ていきましょう。

while true  
end

まずは、trueな限り繰り返すという条件を提示をしましょう。

array[j] = array[j-h]

次に挿入する要素が格納されている位置に挿入済みの要素で上書きしましょう。

j-=h

次に変数jを変数hで引いていきましょう。要するに、挿入する要素の添字に対して、挿入する間隔を引く事で、挿入済みの要素の添字を求めています。以前の解説をした「挿入ソート」では、常に挿入する間隔が1なので動的に値を変えなく良いのですが、シェルソートは、徐々に間隔を狭めていき挿入ソートを行うという特徴があります。その特徴を押さえるために、動的に値を変えていく必要がありますので、変数を活用しました。

 break  if j<h || temp >= array[j-h]
end

こちらは、挿入する間隔が挿入する要素の添字より大きい場合または挿入する要素が挿入済み以上の場合と条件を提示をしています。要するに挿入ソートを行う必要がなくなった場合ですね。条件に該当する場合は、break文を用いて、ループを抜けます。

 array[j] = temp

while文のスコープを抜けたら、挿入済みの要素の位置に挿入する要素を挿入をします。注意点は、同じ変数jでも格納されている値は違う点です。

j-=h

挿入する要素の添字に対して挿入する間隔を引いているからです。

  h = h/2

for文のスコープを抜けたら、変数hを2で割ります。つまり、挿入する間隔を狭めていきます。今回は、4,2,1と間隔を狭めてます。

この一連の流れを繰り返す事で、シェルソート は成り立っています。以上で、シェルソートの解説を終了します。挿入ソートの応用した内容ですので、もし、理解ができない場合は、挿入ソートを復習をしておきましょう。

まとめ：アルゴリズム3

今回は、

• マージソート
• クイックソート
• ヒープソート
• シェルソート

上記、4つの応用的なソートについて解説をしていきました。基本的なソート3つと比較すると、とても難しい内容でした。なので、一度で覚えようとせずに徐々に頭の中に入れていきましょう！！

以上、kazutoでした。

• facebook
• Tweet
• hatebu
• Share
• Read Later