アルゴリズム

Rubyでスタックを扱う

Arrayをスタックとして扱えるので簡単 Array#pushで末尾に追加、Array#popで末尾から取り出し 例として逆ポーランド記法で与えられた数式を計算する 1 2 + 3 4 - * を入力 input = gets.chomp.split(' ') stack = [] input.each do |c| case c when '+' a = …

Rubyでのキューの扱い

Rubyでは、Array#shiftを使用して簡単にキューを実現できる キューで一定時間のプロセスを順番に実行していく、ラウンドロビンスケジューリングを実装する。 # 入力 5 100 p1 150 p2 80 p3 200 p4 350 p5 20 n, q = gets.chomp.split(' ').map(&:to_i) a = […

Rubyで選択ソート

選択ソート # a: int型の配列 # n: 配列の大きさ def selectionSort(a, n) min_index = 0 (0..n-1).each do |i| min_index = i (i..n-1).each do |j| if a[j] < a[min_index] min_index = j end end if a[min_index] < a[i] tmp = a[i] a[i] = a[min_index] …

Rubyでバブルソート

バブルソート # a: int型の配列 # n: 配列の大きさ def bubbleSort(a, n) (0..n-1).each do |i| (i+1..n-1).to_a.reverse_each do |j| if a[j] < a[j-1] tmp = a[j] a[j] = a[j-1] a[j-1] = tmp end end end end

Rubyで挿入ソート

挿入ソート # a: intの配列 # n: 配列の大きさ def insertionSort(a, n) (1..n-1).each do |i| tmp = a[i] j = i - 1 while j >= 0 && a[j] > tmp do a[j+1] = a[j] j -= 1 a[j+1] = tmp end end end