Implementations Of Algorithms & Data Structures

Front 1

Insertion Sort

Back 1

(1..numbers.size-1).each do |j|
key = numbers[j]
i = j - 1
while i >= 0 && numbers[i] > key
numbers[i+1] = numbers[i]
i -= 1
end
numbers[i+1] = key unless j == i+1
end

Front 2

Quick Sort

Back 2

class QuickSort
attr_reader :array

def initialize(array)
@array = array
end

def call
sort(array)
end

def sort(sub_array)
sub_array.length <= 1 ? sub_array : quick_sort(sub_array)
end

private

def quick_sort(sub_array)
pivot = sub_array.pop

less = []
greater = []

sub_array.each do |x|
if x <= pivot
less << x
else
greater << x
end
end

sort(less) + [pivot] + sort(greater)
end
end

Front 3

Find the missing integers in an array of integers

Back 3

def missing_int(source_array)
missing = 0
source_array.each do |i|
missing ^= i
end
integers.each do |i|
missing ^= i
end
missing
end

Front 4

Find the largest continuous sum of an array of integers

Back 4

def largest_continuous_sum
max = integers[0]
cur = integers[0]

integers[1..-1].each do |i|
cur += i
max = cur if cur >= max
end

max
end