It's great that you're digging into how these sorting algorithms work! Though both Bubble and Insertion Sorts have the same time complexity, O(n²), in both the worst and average cases, they work differently. These differences explain why Insertion Sort is generally considered better.
How the Algorithms Work.
- Bubble Sort:
Mechanism: Bubble Sort works by stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The pass-throughs "bubble" the largest unsorted element to its correct position.
Behavior: The algorithm of Bubble Sort performs element comparisons and potential swaps between the two adjacent elements in each pass. After each complete pass, the next largest element goes to its final position at the end of the array. It is done iteratively until the array is sorted.
Comparisons/Swaps: It consistently makes O(n) comparisons per pass whether the array is already sorted or nearly sorted. As a result, there are unwanted comparisons even when the array is nearly sorted.
- Insertion Sort:
Process: Insertion sort builds the sorted array one element at a time by taking an element from the unsorted portion of the list and placing it into its correct position within the sorted portion.
Behavior: Insertion sort picks the next element and places it in its correct position by shifting larger elements to the right. Starting with the first element as a "sorted" list of one, the sorted portion of the list grows one element at a time.
Comparisons/Swaps: The number of comparisons rises slowly as more elements are sorted. In case of the array nearly being sorted, Insertion sort performs fewer comparisons and swaps and hence is effective in this case.
Distinguishing Features of Their Operation
Movement of Elements:
Bubble Sort: In every single pass of the array, the biggest element is moved to its correct position at the right. In this algorithm, the program keeps comparing and swapping till the entire list is sorted.
Insertion Sort: Places each element in its appropriate position within the sorted array it scans through. It makes fewer comparisons and swaps, especially for nearly sorted arrays.
Efficiency on Nearly Sorted Data:
Bubble Sort: Unless an optimization like early termination is applied to it, it will go on making O(n²) comparisons and swaps even if the array is nearly sorted.
Insertion Sort: Intrinsically does well with nearly sorted data, since it has to make few comparisons to put every element in its rightful place and may attain almost O(n) in such cases.
Typical Use Case:
Bubble Sort: Rarely used in practice due to its inefficiency compared to other algorithms.
Insertion Sort: Practically, it is useful when the data is nearly sorted or small. Used in hybrid sorting algorithms like Timsort.
Why Quicksort is Generally Better
Adaptability: Insertion sort does better for partially sorted arrays and, in general, it is more efficient in real-world use due to data often being nearly sorted.
Fewer Swaps: Insertion sort generally involves fewer swaps. It shifts only those elements that are necessary and does not swap the adjacent elements again and again. Thus, the overall cost of the operation is reduced.
Practical Performance: Insertion sort performs better and faster than bubble sort for small or nearly sorted datasets in practice even though it has the same time complexity as O(n²).