アルゴ式をRubyで解く。【コンピュータサイエンス入門】

begin
  lines = readlines.map(&:chomp)
  event_count = lines[0].to_i
  event_times = lines[1..].map { |word| word.split.map(&:to_i) }

  sequential_events_count = 0

  # バブルソート
  # これで右端の値でソートしたevent_timesが出来上がる
  (0..(event_count - 1)).each do |i|
    (0..(event_count - (i + 2))).each do |j|
      if event_times[j][1] > event_times[j + 1][1]
        event_times[j], event_times[j + 1] = event_times[j + 1], event_times[j]
      end
    end
  end

  event_times.reduce do |result, event_time|
    if result[1] <= event_time[0]
      sequential_events_count += 1
      result = event_time
    end
    result
  end

  puts sequential_events_count + 1
rescue StandardError => e
  p "raise: error", e
end

# @param [Integer] target
# @param [Array<Integer>] sorted_array
# return [Integer]
def binary_search_index(target, sorted_array)
  start_index = 0
  end_index = sorted_array.length - 1

  while start_index <= end_index
    center_index = (start_index + end_index) / 2
    if target == sorted_array[center_index]
      return center_index
    elsif target > sorted_array[center_index]
      start_index = center_index + 1
    else
      end_index = center_index - 1
    end
  end

  - 1
end

# バブルソート
# バブルソートは与えられた配列以外の記憶領域が不要

# @params [Array<Integer>] numbers
def bubble_sort(numbers:)
  (0..numbers.length - 1).each do |i|
    exchange_count = 0

    (1..(numbers.length - (i + 1))).each do |j|
      if numbers[j - 1] > numbers[j]
        numbers[j - 1], numbers[j] = numbers[j], numbers[j - 1]
        exchange_count += 1
      end
    end

    # 上のループの隣り合う2項の比較で、一度も要素が交換されなかったら、処理を終了する
    break if exchange_count.zero?

    puts numbers.join(" ")
  end

  numbers
end

begin
  lines = readlines.map(&:chomp)
  # numbers_count = lines[0].to_i
  numbers = lines[1].split.map(&:to_i)

  bubble_sort(numbers: numbers)
  # p sorted_numbers
rescue StandardError => e
  p "raise error:", e.message
end

# 選択ソート

# @params [Array<Integer>] numbers
def selection_sort(numbers:)
  (0..numbers.length - 2).each do |i|
    minimum_number = numbers[i..].min
    minimum_number_index = numbers[i..].find_index(minimum_number)
    numbers[i], numbers[minimum_number_index + i] = numbers[minimum_number_index + i], numbers[i]
    puts numbers.join(" ")
  end
  numbers
end

begin
  lines = readlines.map(&:chomp)
  # numbers_count = lines[0].to_i
  numbers = lines[1].split.map(&:to_i)

  selection_sort(numbers: numbers)
  # p sorted_numbers
rescue StandardError => e
  p "raise error:", e.message
end

# @param [Array<Integer>]
# return [Array<Integer>]
def quick_sort(numbers)
  return numbers if numbers.length == 1
  return numbers if numbers.empty?

  standard_number = (numbers.length / 2).floor
  left_numbers = numbers.filter.with_index { |number, i| i != standard_number && number < numbers[standard_number] }
  right_numbers = numbers.filter.with_index { |number, i| i != standard_number && number >= numbers[standard_number] }

  sorted_left_numbers = quick_sort(left_numbers)
  sorted_right_numbers = quick_sort(right_numbers)

  sorted_left_numbers.push(numbers[standard_number]).concat(sorted_right_numbers)
end

begin
  lines = readlines.map(&:chomp)
  # numbers_count = lines[0].to_i
  numbers = lines[1].split.map(&:to_i)

  sorted_numbers = quick_sort(numbers)
  puts sorted_numbers.join(" ")
rescue StandardError => e
  p "raise error:", e.message
end

# マージソート

# @param [Array<Integer>]
# return [Array<Integer>]
def merge_sort(numbers)
  return numbers if numbers.length <= 1

  # 整数 / 整数なら、デフォルトで切り捨て羅れる
  middle_index = numbers.length / 2
  left_numbers = numbers[0...middle_index]
  right_numbers = numbers[middle_index..(numbers.length - 1)]

  sorted_left_numbers = merge_sort(left_numbers)
  sorted_right_numbers = merge_sort(right_numbers)
  merge_numbers = sorted_left_numbers.concat(sorted_right_numbers.reverse)

  sorted_merge_numbers = []
  until merge_numbers.empty?
    if merge_numbers.first <= merge_numbers.last
      sorted_merge_numbers.push(merge_numbers.shift)
    else
      sorted_merge_numbers.push(merge_numbers.pop)
    end
  end

  sorted_merge_numbers
end

begin
  lines = readlines.map(&:chomp)
  # numbers_count = lines[0].to_i
  numbers = lines[1].split.map(&:to_i)

  sorted_numbers = merge_sort(numbers)
  puts sorted_numbers.join(" ")
rescue StandardError => e
  p "raise error:", e.message
end