Sorting Algorithms

A comprehensive review of common sorting algorithms, including Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, and Radix Sort. Focuses on their performance characteristics and suitability for different data sets.

⬅ Previous Next ➡

Bubble Sort Algorithm

Introduction to Bubble Sort

Bubble Sort is a 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, which indicates that the list is sorted. It gets its name because elements 'bubble' to the top of the list as it iterates.

Explanation of Bubble Sort Algorithm

The algorithm works by comparing each pair of adjacent items in the list and swapping them if they are out of order. The largest element "bubbles" to the end of the array with each pass. This process is repeated for each element in the array until the array is completely sorted. Essentially, after each pass, the largest unsorted element is placed in its correct position.

Step-by-Step Example

Let's consider an unsorted array: [5, 1, 4, 2, 8]

Pass	Array	Comparison	Action
1	[5, 1, 4, 2, 8]	5 > 1	Swap
1	[1, 5, 4, 2, 8]	5 > 4	Swap
1	[1, 4, 5, 2, 8]	5 > 2	Swap
1	[1, 4, 2, 5, 8]	5 > 8	No swap
1 (End)	[1, 4, 2, 5, 8]		Largest element (8) is now in its correct position.
2	[1, 4, 2, 5, 8]	1 > 4	No swap
2	[1, 4, 2, 5, 8]	4 > 2	Swap
2	[1, 2, 4, 5, 8]	4 > 5	No swap
2 (End)	[1, 2, 4, 5, 8]		Second largest element (5) is now in its correct position.
3	[1, 2, 4, 5, 8]	1 > 2	No swap
3	[1, 2, 4, 5, 8]	2 > 4	No Swap
3 (End)	[1, 2, 4, 5, 8]		Third largest element (4) is now in its correct position.
4	[1, 2, 4, 5, 8]	1 > 2	No swap
4 (End)	[1, 2, 4, 5, 8]		Fourth largest element (2) is now in its correct position.

After 4 passes, the array is sorted: [1, 2, 4, 5, 8]

Pseudocode

 function bubbleSort(array) {
    n = length(array)
    for i = 0 to n-1 {
      for j = 0 to n-i-1 {
        if array[j] > array[j+1] {
          swap(array[j], array[j+1])
        }
      }
    }
    return array
  }

Time Complexity Analysis

Best Case: O(n) - Occurs when the array is already sorted. Only one pass is needed to confirm this. An optimization can be added to stop the algorithm early if no swaps occur in a pass.
Average Case: O(n²) - Occurs when the array is randomly ordered. The algorithm needs to compare and potentially swap elements multiple times.
Worst Case: O(n²) - Occurs when the array is sorted in reverse order. Every element needs to be compared and swapped in each pass.

Space Complexity Analysis

Space Complexity: O(1) - Bubble Sort is an in-place sorting algorithm because it only requires a constant amount of extra space. It performs sorting by swapping elements within the original array, without requiring any significant additional memory allocation.

Advantages of Bubble Sort

Simple to implement: The algorithm is straightforward and easy to understand, making it a good introductory sorting algorithm.
Easy to understand: The logic is clear and intuitive, making it easy to debug and maintain.
In-place sorting: Requires minimal additional memory.

Disadvantages of Bubble Sort

Inefficient for large datasets: Its quadratic time complexity makes it unsuitable for sorting large arrays.
Not adaptive: Even if the input is nearly sorted, Bubble Sort still performs all its iterations. While it can be optimized to detect already sorted lists, many other sorting algorithms offer better performance for nearly sorted data without modification.

⬅ Previous Next ➡