Divide and conquer (majority element of array in Ruby with merge sorting algorithm)

majority_element_of_array_in_ruby.md

Majority Element

Problem Introduction

Majority rule is a decision rule that selects the alternative which has a majority, that is, more than half the votes. Given a sequence of elements 𝑎1, 𝑎2, . . . , 𝑎𝑛, you would like to check whether it contains an element that appears more than 𝑛/2 times. A naive way to do this is the following.

MajorityElement(𝑎1, 𝑎2, . . . , 𝑎𝑛):
for 𝑖 from 1 to 𝑛:
currentElement ← 𝑎𝑖
count ← 0
for 𝑗 from 1 to 𝑛:
if 𝑎𝑗 = currentElement:
count ← count + 1
if count > 𝑛/2:
return 𝑎𝑖
return “no majority element”

The running time of this algorithm is quadratic. Your goal is to use the divide-and-conquer technique to design an 𝑂(𝑛 log 𝑛) algorithm.

Problem Description

Task. The goal in this code problem is to check whether an input sequence contains a majority element.

Input Format.

The first line contains an integer 𝑛, the next one contains a sequence of 𝑛 non-negative integers 𝑎0, 𝑎1, . . . , 𝑎𝑛−1.

Constraints.

1 ≤ 𝑛 ≤ 105; 0 ≤ 𝑎𝑖 ≤ 109 for all 0 ≤ 𝑖 < 𝑛.

Output Format.

Output 1 if the sequence contains an element that appears strictly more than 𝑛/2 times, and 0 otherwise.

Example.

• Input:

5
2 3 9 2 2

• Output:

1

2 is the majority element.

def merge_sort(array)
  l = array.length
  return array if l <= 1

  mid = l/2
  left  = array[0...mid]
  right = array[mid...l]
  merge(merge_sort(left), merge_sort(right))
end

def merge(left, right)
  sorted = []

  until left.empty? || right.empty?
    if left[0].to_i <= right[0].to_i
      sorted << left.shift
    else
      sorted << right.shift
    end
  end
  sorted + left + right
end

el_size = gets.chomp.to_i
string_arr = gets.chomp.split

if el_size == 1
  puts 1
  return
end

# merge sorting algorithm
sorted = merge_sort(string_arr)
half = el_size.odd? ? el_size.to_f/2 : el_size/2
mid_el = sorted[el_size/2]

mid_el_count = sorted.count(mid_el)
puts mid_el_count.to_i > half ? 1 : 0