- Linear Search
Bubble Sort
The simplest sorting algorithm. It works by repeatedly swapping the adjacent elements if they are in the wrong order. It starts at the beginning of an unsorted array and 'bubbles up' unsorted values towards the end, until the array is completely sorted.
+ Simple, Elements are swapped in place without additional temporary storage
− Multiple iterations, Not efficient with a list with many items, Quadratic time complexity (O(n^2))
Selection Sort
An in-place, unstable, comparison algorithm.
It works by starting in the first position, assuming this holds the element with the smallest (or biggest) value. It selects the minimum value in a list and swaps it with the first value in the list. Then, it starts at the second position, selects the element of the array with the smallest value and it swaps with the second element. It goes on until the list is sorted.
+ Simple, Good performance on a small list
− Pure performance when dealing with a big list, Quadratic time complexity (O(n^2))
Insertion Sort
A highly intuitive, stable, in-place, and of comparison-type. The list is divided into two parts, the left, which is sorted, and the right (unsorted). Initially, the left (sorted) is empty and the right is the entire input list. The element with the minimun value is selected from the unsorted list and it is mooved to the left side (sorted). The boundary of the unsorted list is moved each time to the right by removing one element.
+ Simple, Performance advantage over complicated algorithms in some cases
− It has O(n^2) time complexity.
Quick Sort
A divide-and-conquer algorithm. An in-place sorting algorithm. This type breaks down the list in two (or more) lists. An element is picked as pivot. Then, it performs the sorting on these sub-lists. The pivot might be the first or the last element, a random element or some other element, and the list is partitioned around the pivot. Recursion is used and the lists are combined in a final result.
+ Used for solving difficult problems, Efficient use of memory, Faster than other sorting algorithms, O(nlog(n)) performance
− The efficiency is dependent on the choice of pivot (worst case: always pick the smallest / greatest element as pivot, best case: pick the middle element)