ソート

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

バブルソート

基本的な考え方

1. 先頭から順に見ていって、左右の並びがおかしいところがあれば、入れ替える。
2. 最後までたどり着いたら再び先頭に戻って、同じように見ていく。
3. 1度も並び替えをすることなく先頭から最後まで見終わったら完了。

class BubbleSort
  def initialize( n )
    @target = Array.new(n)
  end
  
  def main
    puts "準備中"
    
    @target.each_index do |i|    # ----- 配列にランダムな値を格納
      @target[i] = rand(1000)
    end
    
    p @target
    
    puts "並び替え開始"
    bubbleSort()
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def bubbleSort()
    flag = nil
    begin
      i = 0
      flag = false
      while i < @target.size - 1
        if @target[i] > @target[i + 1]
          flag = true
          j = @target[i]
          @target[i] = @target[i + 1]
          @target[i + 1] = j
          p @target
        end
        i = i + 1
      end
    end while(flag)
  end

end

N = 10  # データの件数

bubbleSort = BubbleSort.new(N)
bubbleSort.main

class BubbleSort
  def initialize( array )
    @target = array
  end

  def sort
    flag = nil
    begin
      flag = false
      (@target.size - 1).times do |i|
        if @target[i] > @target[i + 1]
          flag = true
          j = @target[i]
          @target[i] =@target[i + 1]
          @target[i + 1] = j
        end
      end
    end while( flag )
  end
end

# ---------- Main
if __FILE__ == $0
  N = 10
  puts "準備中"
  array = Array.new( N )
  array.each_index do |i|
    array[i] = rand( 1000 )
  end

  p array
  s = BubbleSort.new( array )

	  puts "並び替え開始"
  s.sort
  puts "終了"
  p array
end

class BubbleSort
  def initialize( n )
    @target = Array.new(n)
  end
  
  def main
    puts "準備中"
    
    @target.each_index do |i|    # ----- 配列にランダムな値を格納
      @target[i] = rand(1000)
    end
    
    p @target
    
    puts "並び替え開始"
    bubbleSort()
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def bubbleSort()
    flag = nil
    begin
      i = 0
      t = 0
      flag = false
      while i < @target.size - 1 - t  # ----- ここが変更されている
        if @target[i] > @target[i + 1]
          flag = true
          j = @target[i]
          @target[i] = @target[i + 1]
          @target[i + 1] = j
          p @target
        end
        i = i + 1
      end
      t = t + 1
    end while(flag)
  end
end

N = 10  # データの件数

bubbleSort = BubbleSort.new(N)
bubbleSort.main

class BubbleSort
  def initialize( array )
    @target = array
  end

  def sort
    flag = nil
    begin
      flag = false
      t = 0
      (@target.size - 1 - t).times do |i|
        if @target[i] > @target[i + 1]
          flag = true
          j = @target[i]
          @target[i] = @target[i + 1]
          @target[i + 1] = j
        end
      end
      t += 1
    end while( flag )
  end
end


if __FILE__ == $0
  N = 10
  puts "準備中"
  array = Array.new( N )

  array.each_index do |i|
    array[i] = rand( 1000 )
  end

  p array
  s = BubbleSort.new( array )

  puts "並び替え開始"
  s.sort

  puts "終了"
  p array
end

クイックソート

基本的な考え方

1. ある適当な値を決めて、それよりも大きいものは後ろへ、小さいものは前へ移動する。
2. 2つに分けたそれぞれのグループの中で、再び適当な値を決めて、それよりも大きいものは後ろへ、小さいものは前へ移動する。
3. 上記を繰り返す。
4. それ以上グループ分けが出来なくなったら完了。

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

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(0, N - 1, @target)
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def quickSort( bottom, top, data )
    lower = bottom
    upper = top
    
    return if (bottom >= top)
    
    div = data[bottom]
    while lower < upper
      while (lower <= upper && data[lower] <= div )
        lower += 1
      end

      while (lower <= upper && data[upper] > div )
        upper -= 1
      end

      if (lower < upper)
        temp = data[lower]
        data[lower] = data[lower]
        data[lower] = data[upper]
        data[upper] = temp
      end
      p data
    end
    temp = data[bottom]
    data[bottom] = data[upper]
    data[upper] = temp

    quickSort(bottom, upper - 1, data)
    quickSort(upper + 1, top,data)
  end
end

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

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()
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def quickSort()
    @target.sort
  end
end

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

マージソート

基本的な考え方

1. 全体を小さなブロックに区切る。
1. 全体を2つに分ける。
2. 分けた2つを、またそれぞれ2つに分ける。
3. ブロックの大きさが完全に1つになるまで分け続ける。
2. 各ブロックをソートしながらつなぎ合わせ、中くらいのソート済みブロックにまとめる。
3. 中くらいのソート済みブロックをつなぎ合わせ、大きなソート済みブロックにまとめる。
4. 上記を繰り返して全体がソート済みになるようにする。

class MergeSort
  def initialize( n )
    @target = Array.new(n)
  end
  
  def main
    puts "準備中"
    
    @target.each_index do |i|
      @target[i] = rand(1000)
    end
    
    p @target
    
    puts "並び替え開始"
    mergeSort(@target.size, @target, 0)
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def mergeSort( n, x, offset )
    return if n <= 1
    m = n / 2
    
    # ブロックを2分割する
    mergeSort(m, x, offset)
    mergeSort(n - m, x, offset + m)
    
    # 併合操作
    buffer = Array.new(m)
    i = 0
    while i < m do
      buffer[i] = x[offset + i]
      i += 1
    end
    
    j = m
    i = 0
    k = 0
    
    while (i < m && j < n) do
      if buffer[i] <= x[offset + j]
        x[offset + k] = buffer[i]
        i += 1
      else
        x[offset + k] = x[offset + j]
        j += 1
      end
      k += 1
    end
    
    while (i < m) do
      x[offset + k] = buffer[i]
      k += 1
      i += 1
    end
    p x
  end
end

N = 10
merge = MergeSort.new(N)
merge.main

コームソート

基本的な考え方

　バブルソートとは異なり、離れた要素同士を比較して交換していく。徐々に比較する距離を縮めていき、比較する距離が1になった時点でバブルソートと同じになり、完了となる。

class CombSort
  def initialize( n )
    @target = Array.new(n)
  end
  
  def main
    puts "準備中"
    
    @target.each_index do |i|
      @target[i] = rand(1000)
    end
    
    p @target
    
    puts "並び替え開始"
    combSort()
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def combSort()
    flag = nil
    gap = @target.size
    
    begin
      gap = (gap * 10 ) / 13
      gap = 1 if gap == 0
      flag = true
      i = 0
      while i < @target.size - gap do
        if @target[i] > @target[i + gap]
          flag = false
          temp = @target[i]
          @target[i] = @target[i + gap]
          @target[i + gap] = temp
        end
        i += 1
      end
    end while( gap > 1 || !flag)
  end
end

N = 10
comb = CombSort.new(N)
comb.main

挿入ソート

基本的な考え方

　ほとんど整列が完了しているデータに対して効率がよい。単純挿入ソートでは、リニアサーチを使い、2分挿入ソートでは、バイナリサーチを使う。

class InsertSort
  def initialize( n )
    @target = Array.new(n)
  end
  
  def main
    puts "準備中"
    
    @target.each_index do |i|
      @target[i] = rand(1000)
    end
    
    p @target
    
    puts "並び替え開始"
    insertSort()
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def insertSort()
    sorted = 0
    while sorted < @target.size - 1 do
      insert = @target[sorted + 1]
      i = 0
      while i <= sorted do
        break if @target[i] > insert
        i += 1
      end
      
      while i <= sorted + 1 do
        temp = @target[i]
        @target[i] = insert
        insert = temp
        i += 1
      end
      sorted += 1
    end
  end
end

N = 10
insert = InsertSort.new(N)
insert.main

class InsertSort
  def initialize( n )
    @target = Array.new(n)
  end
  
  def main
    puts "準備中"
    
    @target.each_index do |i|
      @target[i] = rand(1000)
    end
    
    p @target
    
    puts "並び替え開始"
    insertSort()
    puts "終了"
    
    p @target
  end
  
  private
  # ----- ソートアルゴリズム
  def insertSort()
    sorted = 0
    while sorted < @target.size - 1 do
      insert = @target[sorted + 1]
      i = 0
      left = 0
      right = sorted
      while left < right do
        mid = (left + right) / 2
        if @target[mid] <= insert
          left = mid + 1
        else
          right = mid
        end
      end
      
      i = left
      while i <= sorted + 1 do
        temp = @target[i]
        @target[i] = insert
        insert = temp
        i += 1
      end
      sorted += 1
    end
  end
end

N = 10
insert = InsertSort.new(N)
insert.main