Insertion Sort:
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by repeatedly taking the next element from the unsorted part of the array and inserting it into its correct position in the sorted part of the array.
Algorithm:
- Start with the second element (index 1) and consider it as the key.
- Compare the key with the elements before it, moving larger elements one position to the right until finding the correct position for the key.
- Insert the key into its correct position.
- Repeat steps 1-3 for each element in the array until the entire array is sorted.
Complexity:
- Average Case: O(n^2), where n is the number of elements in the array.
- Worst Case: O(n^2), when the array is in reverse order.
- Best Case: O(n), when the array is already sorted.
Bubble Sort:
Bubble Sort is another simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, indicating that the list is sorted.
Algorithm:
- Start from the beginning of the array.
- Compare each pair of adjacent elements.
- If the elements are in the wrong order, swap them.
- Repeat steps 1-3 until no more swaps are needed (indicating the array is sorted).
Complexity:
- Average Case: O(n^2), where n is the number of elements in the array.
- Worst Case: O(n^2), when the array is in reverse order.
- Best Case: O(n), when the array is already sorted.
Comparison and Analysis:
- Both Insertion Sort and Bubble Sort are simple and easy to implement.
- Insertion Sort tends to perform better than Bubble Sort in practice, particularly for small datasets or when the array is partially sorted.
- Bubble Sort performs poorly on large datasets and is generally not recommended for practical use.
- Insertion Sort is more efficient than Bubble Sort in terms of average and best-case time complexity, but they both have the same worst-case time complexity.
- In terms of space complexity, both algorithms have O(1) space complexity as they don’t require additional memory proportional to the size of the input.
 while both Insertion Sort and Bubble Sort are basic sorting algorithms, Insertion Sort is generally more efficient and practical, especially for small datasets, due to its better average-case performance. However, for larger datasets or when efficiency is critical, more advanced sorting algorithms like Merge Sort or Quick Sort are typically preferred.