elementary_sorting_algorithms.rb

# NOTES
# Worst case O(N^2)
# 

# Selection Sort
# Best, Avg, Worst O(N^2) TC
# Worst SC O(1)

def selection_sort(arr)
    for i in 0...(arr.length-1)
        index_min = i
        for j in (i+1)...arr.length
            index_min = j if arr[j] < arr[index_min]
        end
        arr[i], arr[index_min] = arr[index_min], arr[i] if i != index_min
    end
    arr
end

# Bubble Sort 
# Stable
# Can stop early if numbers already sorted (no other sorting algo does this)
# Still crap though!
# Best, Avg, Wrost, Soace worst = Ω(n+k), Θ(n+k), O(n^2), O(n)

def bubble_sort(arr)
    sorted = false
    while !sorted
        sorted = true
        for i in 0...arr.length-1
            if arr[i+1] < arr[i]
                arr[i+1], arr[i] = arr[i], arr[i+1]
                sorted = false
            end
        end
    end
    arr
end

# Insertion Sort
# Best, Avg, Worst, Spapce Worst = Ω(n) 	Θ(n^2) 	O(n^2) 	O(1)
def insertion_sort(arr)
    for i in 2..arr.length
        el = arr[i-1]
        index = i - 2
        while(index >= 0) && (el < arr[index])
            arr[index+1] = arr[index]
            index-=1
        end
        arr[index+1] = el
    end
    arr
end

arr = [2,4,1,0,7,3,12,22,1]
puts selection_sort(arr).inspect
puts bubble_sort(arr).inspect
puts insertion_sort(arr).inspect