### Bubble Sort vs Insertion Sort

In this post, we will learn the difference between Bubble Sort and Insertion Sort in Java. This is a frequently asked question in Java interviews for beginners. Let's dive into it.

## Difference between Bubble Sort and Insertion Sort in Java

Feature Bubble Sort Insertion Sort
Sorting Algorithm Bubble Sort is a comparison-based sorting algorithm. Insertion Sort is also a comparison-based sorting algorithm.
Approach Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order. Insertion Sort iterates through the list and inserts each element into its correct position among the already sorted elements.
Complexity Bubble Sort has a worst-case and average-case time complexity of O(n^2). Insertion Sort has a worst-case and average-case time complexity of O(n^2).
Best Case Complexity Bubble Sort has a best-case time complexity of O(n) when the array is already sorted. Insertion Sort has a best-case time complexity of O(n) when the array is already sorted.
In-Place Sorting Bubble Sort is an in-place sorting algorithm as it does not require additional memory for sorting. Insertion Sort is also an in-place sorting algorithm as it does not require additional memory for sorting.
Stability Bubble Sort is a stable sorting algorithm, meaning the relative order of equal elements is preserved after sorting. Insertion Sort is also a stable sorting algorithm.
Use Cases Bubble Sort is rarely used in practice due to its inefficiency for large datasets. Insertion Sort is often used for small datasets or when the array is nearly sorted. It performs well when the array is almost sorted.
Performance Bubble Sort performs poorly for large datasets as it requires multiple passes through the array. Insertion Sort performs well for small datasets but becomes inefficient for large datasets due to its quadratic time complexity.
Number of Comparisons Bubble Sort performs n*(n-1)/2 comparisons in the worst case. Insertion Sort performs n*(n-1)/2 comparisons in the worst case.
Overall, both Bubble Sort and Insertion Sort are simple sorting algorithms suitable for small datasets or nearly sorted arrays. However, they are not recommended for large datasets due to their quadratic time complexity, and more efficient sorting algorithms like Merge Sort or Quick Sort are preferred for larger datasets.