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