Name :

Mughees Ahmad
Reg. No:
COSC-221101043
Section :
BSCS-5A
Subject :
Design and Analysis
of Algorithm
Submitted To:
Sir Mutiullah
 Comparative Analysis of Insertion, Bubble,
Shell Sort, and Radix Sort

Sorting algorithms play a critical role in optimizing data organization for

various applications. This document provides an in-depth comparative analysis of
Insertion Sort, Bubble Sort, Shell Sort, and Radix Sort, focusing on their
approach, time and space complexities, stability, and characteristics.

Insertion Sort
Approach:
Insertion Sort works by dividing the array into a sorted and an unsorted
portion. Initially, the first element is considered sorted. Each subsequent element
is compared with elements in the sorted portion and inserted into its correct
position. The algorithm is intuitive and mimics the way humans often sort playing
cards.

Time Complexity:
• Best Case: When the input array is already sorted, the algorithm simply
traverses the array without making unnecessary comparisons or swaps.
This makes the best-case performance linear. The best-case time
complexity of insertion sort is O(n).
• Average Case: When the input array is in random order, each insertion
operation involves comparing and shifting elements, resulting in quadratic
complexity The average-case time complexity of insertion sort is O(n^2).
• Worst Case: When the array is sorted in reverse order, the algorithm must
compare each element with all preceding elements, leading to the
maximum number of comparisons and shifts. The worst-case time
complexity of insertion sort is O(n^2).
 Space Complexity:
Insertion Sort is an in-place sorting algorithm, requiring no additional
storage except for temporary variables during swaps. Its space complexity is
O(1), making it highly memory-efficient.

Characteristics:
Insertion Sort is simple to implement and works effectively for small
or partially sorted datasets. However, its performance degrades significantly as
the size of the dataset grows, making it less suitable for larger datasets.

Bubble Sort
Approach:
Bubble Sort repeatedly steps through the array, comparing adjacent
elements and swapping them if they are in the wrong order. This process
continues until no swaps are needed in a complete pass, indicating that the array
is sorted. Its name comes from the way smaller elements “bubble” to the top of
the array.

Time Complexity:
• Best Case: Optimized versions of Bubble Sort can detect when the array is
already sorted by checking if any swaps occurred during a pass. If no swaps
are needed, the algorithm terminates early, achieving linear complexity.
The best-case time complexity of insertion sort is O(n).
• Average Case: In a randomly ordered array, multiple comparisons and
swaps are required for each pass. The average-case time complexity of
insertion sort is O(n^2).
• Worst Case: Similar to the average case, but all elements must be swapped
multiple times if the array is sorted in reverse order. The worst-case time
complexity of insertion sort is O(n^2).

Space Complexity:
Bubble Sort also operates in-place with O(1) space complexity.
Characteristics:
Bubble Sort is easy to understand and implement, making it a popular
choice for educational purposes. However, its inefficiency and high number of
swaps make it impractical for real-world applications involving large datasets.

Shell Sort
Approach:
Shell Sort enhances Insertion Sort by starting with larger gaps between
elements and progressively reducing the gap. This allows elements to be moved
closer to their final position early, reducing the total number of shifts in later
stages. The efficiency of the algorithm depends significantly on the choice of the
gap sequence.

Time Complexity:
• Best Case: For well-chosen gap sequences, the algorithm approaches near-
linear performance. The best-case time complexity of insertion sort is O(n
log n).
• Average Case: The performance varies depending on the dataset and gap
sequence. The average-case time complexity of insertion sort is between
O(n log^2 n) and O(n^2).
• Worst Case: With poorly chosen gap sequences, Shell Sort may degrade to
quadratic complexity. The worst-case time complexity of insertion sort is
O(n^2).

Space Complexity:
Like the previous algorithms, Shell Sort operates in-place, with O(1) space
complexity.

Characteristics:
Shell Sort is versatile and offers improved performance over basic sorting
algorithms, especially for moderately large datasets. However, its efficiency
depends heavily on the choice of the gap sequence, making it less predictable
than some other algorithms.

Radix Sort
Approach:
Radix Sort sorts elements by processing individual digits of numbers,
starting from the least significant digit (LSD) to the most significant digit (MSD) or
vice versa. It leverages Counting Sort as a stable subroutine to sort digits in linear
time.

Time Complexity:
• Best Case: If the number of digits (kkk) in the largest number is small
relative to the array size, Radix Sort performs efficiently. The worst-case
time complexity of insertion sort is O(nk).
• Average Case: Regardless of the dataset's order, the algorithm processes
each digit of all elements, making its performance consistent. The worst-
case time complexity of insertion sort is O(nk).
• Worst Case: The performance is tied to the length of numbers and the size
of the dataset. The worst-case time complexity of insertion sort is O(nk).

Space Complexity:
Radix Sort requires additional memory to hold temporary data during digit-
wise sorting, resulting in O(n + k) space complexity.

Characteristics:
Radix Sort is efficient for sorting numerical datasets with fixed digit lengths.
It avoids comparisons entirely, which can be advantageous for certain types of
data. However, its reliance on auxiliary space and suitability limited to integers
restrict its versatility.