class Sorts
Sorts
class 4 methods corresponding to algorithm_selector module 5 sorting algorithms (selection, insertion, bubble, merge, quick)
Public Instance Methods
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
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
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 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
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
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 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 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 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 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