# Sorting Algorithms in Ruby

Having enjoyed excellent posts on sorting algorithms I wanted to share my implementation of common sorting algorithms in Ruby. There are some great visualizations of sorting algorithms especially on Mike Bostock's blog such as the Fisher-Yates Shuffle, merge sort, and quick sort. Taking a leaf out of Jesse La Russo's blog below are my implementations of common sorting algorithms in Ruby.

### Insertion Sort

1. Begin at the second element. Compare the element to the element prior. Swap if less than the element prior.
2. Increment by one element. Compare this element to prior two elements. Insert accordingly.
3. Continue incrementing by one element and comparing that element to all prior sorted elements until the list is fully sorted.
``````def insertion_sort(list)
(1...list.length).each do |i|
k = i
while k > 0 && list[k] < list[k-1]
list[k], list[k-1] = list[k-1], list[k]
k -= 1
end
end
list
end
``````

### Selection Sort

1. Start at first element of unsorted list. Look for the smallest element in the list. Swap with left most unsorted element.
2. Move to the second element. Swap with smallest element of this unsorted list.
``````def selection_sort(list)
(0...list.length).each do |i|
k = i

(i+1...list.length).each do |j|
k = j if list[j] < list[k]
end

if k != i
list[i],list[k] = list[k],list[i]
end
end
list
end
``````

### Bubble Sort

1. Start at first element. Compare adjacent pairs. Swap if out of order.
2. Iterate through the list repeatedly. Each iteration requires one less comparison.
``````def bubble_sort(list)
begin

swapped = false
(1...list.length).each do |i|

if list[i] < list[i-1]
list[i], list[i-1] = list[i-1],list[i]
swapped = true
end

end

end until !swapped
list
end
``````

### Shell Sort

(Insertion sort on sublists or sublists of elements allowing swap of elements far apart.)

1. Determine sublists by splitting the list in half repeatedly.
2. Insertion sort of the elements in each sublist.
3. When the sublist is one or zero elements long then the list is sorted.
``````def shell_sort(list)
gap = list.length/2
while gap > 0

# Insertion Sort
(gap...list.length).each do |i|
k = i
while k >= gap && list[k] < list[k-gap]
list[k], list[k-gap] = list[k-gap], list[k]
k -= gap
end
end

gap /= 2
end
list
end
``````

### Merge Sort

1. Divide the unsorted list into sublists around a pivot.
2. Recursively call merge sort on the sublists.
3. Merge the results of the recursive calls.
``````def merge_sort(list)
return list if list.length <= 1
left = []
right = []
pivot = list.length / 2

list.each_with_index do |e,i|
left << e if i < pivot
end

list.each_with_index do |e,i|
right << e if i >= pivot
end

left = merge_sort(left)
right = merge_sort(right)

merge(left, right)
end

def merge(left, right)
result = []
while left.length > 0 || right.length > 0
if left.length > 0 && right.length > 0
result << (left <= right ? left.shift : right.shift)
elsif left.length > 0
result << left.shift
else
result << right.shift
end
end
result
end
``````

### Heap Sort

1. Build a heap out of the data. The heap is a tree data structure where the parent node is always greater than or equal to its child nodes across the entire heap.
2. Remove the root of the heap and insert in sorted array. Reconstruct heap and repeat.
``````def heap_sort(list)
count = list.length

heapify(list, count)

last = count - 1
while last > 0
p "#{list[last]}, #{list}"
list[last], list = list, list[last]
last -= 1
sift_down(list,0,last)
end

list
end

def heapify(list, count)
start = (count - 2) / 2

while start >= 0
sift_down(list,start,count-1)
start -= 1
end
end

def sift_down(list, start, last)
root = start

while root * 2 + 1 <= last
child = root * 2 + 1
swap = root

swap = child if list[swap] < list[child]
if child + 1 <= last && list[swap] < list[child+1]
swap = child + 1
end
if swap != root
list[root], list[swap] = list[swap], list[root]
root = swap
else
return
end
end
end
``````

### Quick Sort

1. Divide list into two smaller lists.
2. Pick a pivot.
3. Reorder list so that all elements less than the pivot come before it and all elements greater than the pivot come after it.
4. Recursively apply steps 2 and 3 to the sublists until base case of size 0 or 1 lists is reached.
``````def quick_sort(list)

return list if list.length <= 1

pivot = list[list.length/2]

less, greater = list.partition {|e| e < pivot}

quick_sort(less) + [pivot] + quick_sort(greater)

end
``````