Random Sort
Time Complexity: O(n!)
Pros:
- nonexistent
Cons:
- loooooooooooooooooooooooooooooooooooooooooooooooong time to sort
Insertion Sort
Worst Case Time Complexity: O(n^2)
Best Case Time Complexity: O(1)
Process:
- Insertion sort begins by sorting a small section of the array, known as the sorted subsection
- Then, each element is compared one-by-one with the sorted subsection until its correct place is found
- This is repeated, until at the end when a check is performed and the sort is complete
Pros: - Simple, easy to implement
- Already in use in daily lives in many ways
Cons: - Slow, unpractical, as large number of comparisons makes it impractical at times
Quick Sort
Time Complexity: O(nlogn)
Process:
- Pivot element is selected, element in middle of list
- Elements are compared to pivot and moved to proper side of arraw
- New pivot is selected, and process is repeated until array is sorted
Pros: - Quick, efficient sorting
Cons: - More complicated to implement comparatively to some other algorithms
Bubble Sort
Best Case Time Complexity: O(n)
Worst Case Time Complexity: O(n^2)
Process:
- Compare two adjacent elements, and swap them accordingly
- Move down an element, repeat
- Repeat by starting over again until line is sorted
Pros: - Simple to implement
Cons: - Slow, especially if elements are far out of place
Merge Sort
Time Complexity: O(nlogn)
Process:
- Split list into two halves
- Split halves into more halves
- Repeat until left with groups of two
- Sort groups of two
- Sort groups of four
- Repeat and merge groups until list is sorted
Pros: - Quick, efficient sorting
Cons: - Complicated comparatively to some algorithms, i.e. selection sort, bubble sort, etc
Selection Sort
Time Complexity: O(n^2)
Process:
- Iterate through list and find lowest element
- Swap lowest element with first element in list
- Iterate through rest of list and find second lowest element
- Swap this with second element in list
- Repeat until list is sorted
Pros: - Simple, easy to implement
Cons: - Slow at times, depends on location of shorter and longer elements (i.e. partially sorted)