sorting algorithms

Simple sorts

1. Insertion sort

   O(n^2) Time, O(1) Space

   Take the element one by one and inserting in their correct position into a new sorted list.

   

2. Selection sort

   O(n^2) Time, O(1) Space

   Find the minimum value, swap it with the vlaue in the first position and repeat these steps for the remainder of the list.

   

3. Bubble sort

   O(n^2) Time

   Start at the beginning of the data set, comapres the first two elements and if the first is greater than the second, it swaps them. Continures doing this for each pair of adjacent elements to the end of the data set. Start again with the first two elements, repeating until no swaps have occurred on the last pass.

   // can be used on a list of any length that is nearly sorted.

   

Efficient sorts

1. Merge sort

   O(nlogn) Time, O(n) Space

   Divide and concure. Split the list into two parts, recursively sort them and then merge the sorted lists into a new list.

   

2. Heapsort

   O(nlogn) Time, O(n) Space

   Determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list. The efficiency comes from the heap data structure. Using a heap, finding the next largest element takes O(logn) time.

   

3. Quicksort

   O(nlogn) Average Time, O(n) Space