Class: Sorts

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithm_selector.rb

Overview

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

Instance Method Summary collapse

Instance Method Details

#all(data_set, trials) ⇒ Object

Show all results from sorting algorithms



57
58
59
60
61
62
63
64
65
66
67
68
69
 
# 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) ⇒ Object

Show specific sorting algorithm by name



88
89
90
91
92
93
94
95
96
97
98
99
100
 
# 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) ⇒ Object

Show the best sorting algorithm



72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# 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) ⇒ Object

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



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# 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) ⇒ Object

Show comparison of two algorithms



103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
# 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) ⇒ Object

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



206
207
208
209
210
211
212
213
214
215
 
# 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) ⇒ Object

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



145
146
147
148
149
150
151
152
153
154
155
156
157
 
# 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) ⇒ Object

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



182
183
184
185
186
187
188
 
# 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) ⇒ Object

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



194
195
196
197
198
199
200
 
# 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) ⇒ Object

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



163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
# 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