SORTING ALGORITHMS

Ruby_sort.rb

Bubble Sort

Sorting by comparing two elements at a time. Swaps items in list if they are in the wrong order. Optimised by the variable `still_swapping`.
1. Move from left to right
2. If right element is greater than left element- swap.

Time Complexity - O(n^2)

Selection Sort

Sorting by repeatedly finding the smallest element in and then placing it at the beginning of the sorted array. It never makes more than O(n) swaps so it is ideal for situations where memory writes are expensive.

Time Complexity - O(n^2)
1. Movement from left to right.
2. Set the first item as a current minimum and current item.
3. Current item starts to move along the array, if the minimum is found- update current minimum and swap.
4. Creation of the first item in a sorted array.

Insertion Sort

Useful for a nearly sorted array. O(n) for small arrays.
1. Movement from left to right.
2. Examine each element and compare to the left item.
3. Insert it in the correct position in the sorted array.

Time Complexity - O(n^2)

Shell Sort

A modification of the insertion sort. Adds a gap instead of adjacent items.
1. Movement from left to right.
2. Examine elements far apart (the gap) and swap them if need be.
3. Start reducing the gap

Time Complexity - O(n^2)

Merge Sort

Uses the divide and conquer paradigm. Best in sorting linked lists and counting inversions in an array.
1. Split the list until its children have one element only.
2. Start merging them in the correct order.

Time Complexity - O(n^2)(Worst case) Best Case O(n log n)

Quick Sort

Uses the divide and conquer paradigm. Prefered over merge sort.
1. You choose a pivot element.
2. Items smaller than the pivot go to the left and items larger than the pivot go to the right.

Time Complexity - O(n^2)(Worst case) Best Case O(n log n)