単純な整列アルゴリズム

バブルソート

• O(n^2)
• 安定

# 配列の後ろから先頭に向かってスキャンしていき、
# もし隣り合う２つの要素の大小関係が逆だったら、それを入れ換える
def bubble_sort( arr )
  (arr.length-1).times do |i|
    j = arr.length-1
    while i<j
      arr[j],arr[j-1] = arr[j-1],arr[j] if arr[j]<arr[j-1]
      j -= 1
    end
  end
end

選択ソート

• O(n^2)
• 不安定

# 整列されていない部分から最小の要素を選び出して、
# それを先頭へ持っていく
def selection_sort( arr )
  (arr.length-1).times do |i| 
    lowest = i
    j = arr.length-1
    while i<j
      lowest = j if arr[j]<arr[lowest]
    end
    arr[i],arr[lowest] = arr[lowest],arr[i]
  end
end

挿入ソート

• O(n^2)
• 安定

# 配列のうち一部分を整列済みの状態にしておき、
# 残りの要素をひとつずつその中の適切な位置に挿入していく
def insersion_sort( arr )
  for i in 1..(arr.length-1)
    j = i
    while 1<=j
      arr[j],arr[j-1] = arr[j-1],arr[j] if arr[j]<arr[j-1]
      j -= 1
    end
  end
end

速度（右が早い）

バブルソート < 選択ソート < 挿入ソート

参考文献

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)