class Sorts

Sorts class 4 methods corresponding to algorithm_selector module 5 sorting algorithms (selection, insertion, bubble, merge, quick)

Public Instance Methods

all(data_set, trials) click to toggle source

Show all results from sorting algorithms

# File lib/algorithm_selector.rb, line 57
def all(data_set, trials)
  {
    sorted: merge_sort(data_set),
    results: {
      bubble_sort: display_time(Proc.new {bubble_sort(data_set)}, trials),
      insertion_sort: display_time(Proc.new {insertion_sort(data_set)}, trials),
      selection_sort: display_time(Proc.new {selection_sort(data_set)}, trials),
      merge_sort: display_time(Proc.new {merge_sort(data_set)}, trials),
      quick_sort: display_time(Proc.new {quick_sort(data_set)}, trials),
      heap_sort: display_time(Proc.new {heap_sort(data_set)}, trials)
    }
  }
end
analyze(data_set, algorithm, trials) click to toggle source

Show specific sorting algorithm by name

# File lib/algorithm_selector.rb, line 88
def analyze(data_set, algorithm, trials)
  hash = all(data_set, trials)
  alg = {}
  hash[:results].each do |key, val|
    if algorithm.to_sym == key
      alg = Hash[key, val]
    end
  end
  {
    sorted: hash[:sorted],
    alg.keys[0] => alg[alg.keys[0]]
  }
end
best(data_set, trials) click to toggle source

Show the best sorting algorithm

# File lib/algorithm_selector.rb, line 72
def best(data_set, trials)
  hash = all(data_set, trials)
  best_time = 0
  best_algorithm = {}
  hash[:results].each do |key, val|
    if val < best_time || best_time == 0
      best_time = val
      best_algorithm = Hash[key, val]
    end
  end
  {
    best_algorithm.keys[0] => best_algorithm[best_algorithm.keys[0]]
  }
end
bubble_sort(data_set) click to toggle source

Bubble sort Worst-Case Space Complexity: O(1) Averge-Case Time Complexity: O(n^2) Worst-Case Time Complexity: O(n^2)

# File lib/algorithm_selector.rb, line 124
def bubble_sort(data_set)
  return data_set if data_set.length < 2
  switched = true
  until switched == false
    switched = false
    (1...data_set.length).each do |i|
      if data_set[i-1] > data_set[i]
        temp = data_set[i]
        data_set[i] = data_set[i-1]
        data_set[i-1] = temp
        switched = true
      end
    end
  end
  return data_set
end
compare(data_set, first_algorithm, second_algorithm, trials) click to toggle source

Show comparison of two algorithms

# File lib/algorithm_selector.rb, line 103
def compare(data_set, first_algorithm, second_algorithm, trials)
  hash = all(data_set, trials)
  first = {}
  second = {}
  hash[:results].each do |key, val|
    if first_algorithm.to_sym == key
      first = Hash[key, val]
    elsif second_algorithm.to_sym == key
      second = Hash[key, val]
    end
  end
  {
    first.keys[0] => first[first.keys[0]],
    second.keys[0] => second[second.keys[0]]
  }
end
heap_sort(data_set) click to toggle source

Quick sort Worst-Case Space Complexity: O(1) Averge-Case Time Complexity: O(n log(n)) Worst-Case Time Complexity: O(n log(n))

# File lib/algorithm_selector.rb, line 206
def heap_sort(data_set)
  (2..data_set.length).to_a.each do |idx|
    BinaryMinHeap.heapify_up(data_set, idx - 1, idx)
  end
  (2..data_set.length).to_a.reverse.each do |idx|
    data_set[idx - 1], data_set[0] = data_set[0], data_set[idx - 1]
    BinaryMinHeap.heapify_down(data_set, 0, idx - 1)
  end
  data_set.reverse!
end
insertion_sort(data_set) click to toggle source

Insertion sort Worst-Case Space Complexity: O(1) Averge-Case Time Complexity: O(n^2) Worst-Case Time Complexity: O(n^2)

# File lib/algorithm_selector.rb, line 145
def insertion_sort(data_set)
  return data_set if data_set.length < 2
  (1...data_set.length).to_a do |i|
    value = data_set[i]
    j = i - 1
    while (j >= 0 && data_set[j] > value) do
      data_set[j+1] = data_set[j]
      j = j - 1
    end
    data_set[j+1] = value
  end
  data_set
end
merge_sort(data_set) click to toggle source

Merge sort Worst-Case Space Complexity: O(n) Averge-Case Time Complexity: O(n log(n)) Worst-Case Time Complexity: O(n log(n))

# File lib/algorithm_selector.rb, line 182
def merge_sort(data_set)
  return data_set if data_set.length < 2
  middle = data_set.length/2
  left = data_set[0...middle]
  right = data_set[middle...data_set.length]
  merge(merge_sort(left), merge_sort(right))
end
quick_sort(data_set) click to toggle source

Quick sort Worst-Case Space Complexity: O(log(n)) Averge-Case Time Complexity: O(n log(n)) Worst-Case Time Complexity: O(n^2)

# File lib/algorithm_selector.rb, line 194
def quick_sort(data_set)
  return data_set if data_set.count < 2
  pivot = data_set[0]
  left = data_set.select {|el| el < pivot}
  right = data_set.select {|el| el > pivot}
  quick_sort(left) + [pivot] + quick_sort(right)
end
selection_sort(data_set) click to toggle source

Selection sort Worst-Case Space Complexity: O(1) Averge-Case Time Complexity: O(n^2) Worst-Case Time Complexity: O(n^2)

# File lib/algorithm_selector.rb, line 163
def selection_sort(data_set)
  (0...data_set.length-1).to_a.each do |i|
    min = i
    (i+1...data_set.length).to_a.each do |j|
      if (data_set[j] < data_set[min])
        min = j
      end
    end
    if min != i
      data_set[min], data_set[i] = data_set[i], data_set[min]
    end
  end
  return data_set
end