Comparative Analysis of Insertion Sort, Bubble
Sort, Shell Sort and Radix Sort
1. Insertion Sort:
Insertion Sort works by building a sorted list one element at a time. Starting
from the second element, it compares it with elements in the already sorted
part of the list and places it in its correct position. This process is repeated
until the entire list is sorted.
Algorithm:
1. Start with the second element as the current element.
2. Compare the current element with the elements in the sorted part.
3. Shift the larger elements one position to the right.
4. Insert the current element at the correct position.
5. Repeat for all elements.
code:
For I from 1 to n-i:
Key = array[i]
J=i–1
While j >= 0 and array[j] > key:
Array[j + 1] = array[j]
J=j–1
Array[j + 1] = key
Complexity:
Time Complexity:
Best Case: \( O(n) \) (already sorted)
Worst Case: \( O(n^2) \)
Space Complexity: \( O(1) \)
2. Bubble Sort:
Bubble Sort repeatedly compares adjacent elements and swaps them if they
are in the wrong order. The largest elements “bubble up” to their correct
positions In each iteration.
Algorithm:
1. Compare adjacent elements in the array.
2. Swap if the current element is greater than the next element.
3. Repeat the process for all elements, excluding the last sorted elements.
code:
For i from 0 to n-1:
For j from 0 to n-i-2:
If array[j] > array[j + 1]:
Swap(array[j], array[j + 1])
Complexity:
Time Complexity:
Best Case: \( O(n) \) (already sorted with an optimized implementation)
Worst Case: \( O(n^2) \)
Space Complexity: \( O(1) \)
3. Shell Sort:
Shell Sort is a generalized form of Insertion Sort. It uses a gap sequence to
divide the list into smaller sublists, sorting them using insertion sort, and
gradually reducing the gap.
Algorithm:
1. Define a gap sequence (e.g., \( n/2, n/4, \dots, 1 \)).
2. Sort the sublists formed by elements at the gap distance using insertion
sort.
3. Reduce the gap and repeat until the gap is 1.
code:
Gap = n // 2
While gap > 0:
For I from gap to n-1:
Key = array[i]
J=i
While j >= gap and array[j – gap] > key:
Array[j] = array[j – gap]
J = j – gap
Array[j] = key
Gap = gap // 2
Complexity:
Time Complexity Depends on the gap sequence.
Worst Case: \( O(n^2) \)
Average Case: \( O(n \log n) \)
Space Complexity: \( O(1) \)
4. Radix Sort:
Radix Sort is a non-comparative sorting algorithm that sorts integers by
processing digits from the least significant to the most significant (or vice
versa). It uses a stable subroutine like Counting Sort for sorting digits.
Algorithm:
1. Find the maximum number to determine the number of digits.
2. For each digit (starting from the least significant), sort the array using
Counting Sort.
3. Repeat until all digits are processed.
code:
For digit from least_significant to most_significant:
Count_sort(array, digit)
Complexity:
Time Complexity:
Best/Worst Case: \( O(d \times (n + b)) \), where \( d \) is the number of
digits, and \( b \) is the base.
Space Complexity: \( O(n + b) \)
Comparison:
Insertion Sort and Bubble Sort have similar performance, but Insertion
Sort is generally faster and more efficient.
Shell Sort outperforms Insertion Sort and Bubble Sort for medium-sized
datasets.
Radix Sort excels in sorting large datasets with a fixed length, but
requires additional memory.
Bubble Sort is the least efficient algorithm, but is often used for
educational purposes due to its simplicity.
Insertion Sort and Radix Sort are stable, while Shell Sort is unstable.
Radix Sort has the highest space complexity due to its need for
additional memory.
Use Cases:
Insertion Sort: Small datasets, nearly sorted data, real-time data
insertion.
Bubble Sort: Small datasets, educational purposes.
Shell Sort: Medium-sized datasets, moderate performance
requirements.
Radix Sort: Large datasets, data with a fixed length, high performance
requirements.
