Bubble Sort

  1. Simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

  2. It gets its name because smaller elements “bubble” to the top (beginning of the list) while larger elements “sink” to the bottom (end of the list) after each iteration.

  3. The algorithm iterates through the list multiple times until no more swaps are needed, indicating that the list is sorted.

  4. Bubble sort has a time complexity of O(n^2) in the worst-case scenario, making it inefficient for large lists but suitable for small datasets or educational purposes due to its simplicity.

  5. Despite its inefficiency, bubble sort is easy to understand and implement, making it a common example for teaching sorting algorithms and computer science concepts.

Insertion Sort

  1. Sorting by comparison and insertion of elements based on adjacent elements

  2. Time complexity
    • Worst Case O(N^2)
    • Best Case O(1)
  3. Somewhat inaccurate in first few iterations

Quicksort

  1. Sorting by pivot. Pivot finds its position along the line. This splits array into two. Qucksort is called recursively and resulting subarrays are also quicksorted

  2. Time complexity

    • worst case scenario O(NlogN)

Merge Sort

  1. Time complexity O(NlogN)
  2. Split arrays into groups of 2. Then sort each group, then combine sort each time multiplying size by 2 (4, 8, 16, …)

Selection sort

  1. Move through the list, and select the smallest value to swap with the front.
  2. O(N^2) always