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

- Begin at the second element. Compare the element to the element prior. Swap if less than the element prior.
- Increment by one element. Compare this element to prior two elements. Insert accordingly.
- 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

- Start at first element of unsorted list. Look for the smallest element in the list. Swap with left most unsorted element.
- 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

- Start at first element. Compare adjacent pairs. Swap if out of order.
- 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.)

- Determine sublists by splitting the list in half repeatedly.
- Insertion sort of the elements in each sublist.
- 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

- Divide the unsorted list into sublists around a pivot.
- Recursively call merge sort on the sublists.
- 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[0] <= right[0] ? left.shift : right.shift)
elsif left.length > 0
result << left.shift
else
result << right.shift
end
end
result
end
```

### Heap Sort

- 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.
- 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[0]}"
list[last], list[0] = list[0], 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

- Divide list into two smaller lists.
- Pick a pivot.
- Reorder list so that all elements less than the pivot come before it and all elements greater than the pivot come after it.
- 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
```