class Sorts_ESN
Public Class Methods
bubble_sort(list)
click to toggle source
bubble sort! ~ best O(n) ~ normal O(n^2) ~ worst O(n^2) stable sort
# File lib/sorts_ESN.rb, line 74 def self.bubble_sort (list) # return if empty return [] if list.size == 0 # sentinels (Ruby, y u no normal for loop?) @i = 0 @j = 0 @len = list.size - 1 # get to the swapping while @i < @len do # reset @j per loop @j = 0 while @j < (@len - @i) do # if it's bigger swap it out swap(list, @j, @j + 1) if list[@j] > list[@j + 1] # increment @j = @j + 1 end # increment @i = @i + 1 end end
insertion_sort(list)
click to toggle source
insertion sort! ~ best O(n) ~ average O(n^2) ~ worst O(n^2) stable sort
# File lib/sorts_ESN.rb, line 8 def self.insertion_sort (list) # get to the sorting list.each_with_index do |v,i| # value and current index @val = v @hole = i # iterate and swap as needed while (@hole > 0 && @val < list[@hole -1]) list[@hole] = list[@hole -1] @hole = @hole - 1 end # assign list[@hole] = @val end end
join(a, b)
click to toggle source
join! helper function!
# File lib/sorts_ESN.rb, line 101 def self.join (a, b) @joined = [] @a_i = 0 @b_i = 0 while (@a_i < a.length && @b_i < b.length) if a[@a_i] < b[@b_i] @joined.push(a[@a_i]) @a_i = @a_i + 1 else joined.push(b[@b_i]) @b_i = @b_i + 1 end end # return joined.concat(a.slice(@a_i, a.length)).concat(b.slice(@b_i, b.length)) end
merge_sort(list)
click to toggle source
merge sort! ~ best O(n log n) ~ average O(n log n) ~ worst O(n log n) stable sort
# File lib/sorts_ESN.rb, line 33 def self.merge_sort (list) # break case return list if list.size <= 1 # find middle of list @mid = (list.size / 2).round # take first half @l = list.take(@mid) # take second half @r = list.drop(@mid) # recurse and join join(merge_sort(l), merge_sort(r)) end
quick_sort(list)
click to toggle source
quick sort! ~ best O(n log n) ~ normal O(n log n) ~ worst O(n^2) unstable sort
# File lib/sorts_ESN.rb, line 54 def self.quick_sort(list) # return empty array if list is empty return [] if list.size == 0 # create pointer to list @x, *xs = *list # split list @less, @more = xs.partition{|y| y < x} # recurse quick_sort(@less) + [@x] + quick_sort(@more) end
swap(list, a, b)
click to toggle source
swap! helper function!
# File lib/sorts_ESN.rb, line 121 def self.swap (list, a, b) @temp = list[a] list[a] = list[b] list[b] = @temp end