Sorting Algorithms Analysis and Implementation

Understanding Insertion Sort and Bubble Sort

This presentation demonstrates two fundamental sorting algorithms with detailed analysis:

  • Insertion Sort: Builds the final sorted array one item at a time
  • Bubble Sort: Repeatedly compares adjacent elements and swaps them if needed

We'll examine pseudocode, time complexity, and C++ implementations using the sample array [7, 3, 8, 1, 5].

Insertion Sort Algorithm

Description: Builds the final sorted array one item at a time by inserting each element into its proper position.

Time Complexity: O(n²) worst case, O(n) best case
Space Complexity: O(1)

Pseudocode:

1. for i = 1 to length(array) - 1:
2.     key = array[i]
3.     j = i - 1
4.     while j >= 0 and array[j] > key:
5.         array[j + 1] = array[j]
6.         j = j - 1
7.     array[j + 1] = key

Visual Legend:

Sorted elements
Current element
Comparing elements
Unsorted elements

Insertion Sort - Step 1

Array Visualization

Pseudocode Execution

for i = 1 to length(array) - 1:
    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

Step 1 of 12

Insertion Sort - Time Complexity Analysis

Mathematical Breakdown

Best Case: O(n)

Scenario: Array is already sorted

Operations: n-1 comparisons, 0 shifts

Explanation: The while loop condition fails immediately for each element, so only one comparison per element is needed.

Total operations: n-1

Average Case: O(n²)

Scenario: Random array distribution

Operations: ~n²/4 comparisons and shifts

Explanation: On average, each element needs to be compared with half of the sorted portion.

Total operations: n(n-1)/4 ≈ n²/4

Worst Case: O(n²)

Scenario: Array is reverse sorted

Operations: n(n-1)/2 comparisons and shifts

Explanation: Each element must be compared with all elements in the sorted portion.

Total operations: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2

Space Complexity: O(1)

Insertion Sort is an in-place algorithm that uses only a constant amount of extra space (variables: key, i, j).

Operation Count Comparison

Array Size (n) Best Case Worst Case
10945
50491,225
100994,950
500499124,750
1,000999499,500

Insertion Sort - Pseudocode to C++ Conversion

Pseudocode

1. for i = 1 to length(array) - 1:
2.     key = array[i]
3.     j = i - 1
4.     while j >= 0 and array[j] > key:
5.         array[j + 1] = array[j]
6.         j = j - 1
7.     array[j + 1] = key

C++ Implementation

#include <iostream>
using namespace std;

void insertionSort(int array[], int n) {
    for (int i = 1; i < n; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

Line-by-Line Conversion Explanations:

Conversion 1 of 7

Bubble Sort Algorithm

Description: Repeatedly steps through the list, compares adjacent elements and swaps them if they're in wrong order.

Time Complexity: O(n²) worst case, O(n) best case
Space Complexity: O(1)

Pseudocode:

1. for i = 0 to length(array) - 2:
2.     swapped = false
3.     for j = 0 to length(array) - 2 - i:
4.         if array[j] > array[j + 1]:
5.             swap array[j] and array[j + 1]
6.             swapped = true
7.     if not swapped:
8.         break

Visual Legend:

Sorted elements
Comparing elements
Unsorted elements

Bubble Sort - Step 1

Array Visualization

Pseudocode Execution

for i = 0 to length(array) - 2:
    swapped = false
    for j = 0 to length(array) - 2 - i:
        if array[j] > array[j + 1]:
            swap array[j] and array[j + 1]
            swapped = true
    if not swapped:
        break

Step 1 of 16

Bubble Sort - Time Complexity Analysis

Mathematical Breakdown

Best Case: O(n)

Scenario: Array is already sorted

Operations: n-1 comparisons, 0 swaps

Explanation: First pass makes no swaps, algorithm terminates early using the optimized version with swapped flag.

Total operations: n-1

Average Case: O(n²)

Scenario: Random array distribution

Operations: ~n²/2 comparisons and swaps

Explanation: On average, about half of all possible pairs need to be swapped.

Total operations: n(n-1)/4 ≈ n²/4

Worst Case: O(n²)

Scenario: Array is reverse sorted

Operations: n(n-1)/2 comparisons and swaps

Explanation: Every comparison results in a swap, requiring the maximum number of operations.

Total operations: (n-1) + (n-2) + ... + 1 = n(n-1)/2

Space Complexity: O(1)

Bubble Sort is an in-place algorithm that uses only a constant amount of extra space (variables: i, j, swapped, temp).

Operation Count Comparison

Array Size (n) Best Case Worst Case
10945
50491,225
100994,950
500499124,750
1,000999499,500

Bubble Sort - Pseudocode to C++ Conversion

Pseudocode

1. for i = 0 to length(array) - 2:
2.     swapped = false
3.     for j = 0 to length(array) - 2 - i:
4.         if array[j] > array[j + 1]:
5.             swap array[j] and array[j + 1]
6.             swapped = true
7.     if not swapped:
8.         break

C++ Implementation

#include <iostream>
using namespace std;

void bubbleSort(int array[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

Line-by-Line Conversion Explanations:

Conversion 1 of 8

Algorithm Comparison Summary

Insertion Sort

Advantages:

  • Simple implementation
  • Efficient for small datasets
  • Adaptive (faster on partially sorted arrays)
  • Stable sorting algorithm
  • In-place sorting
  • Fewer writes than Bubble Sort

Disadvantages:

  • Inefficient for large datasets
  • O(n²) worst-case time complexity
Result: [1, 3, 5, 7, 8]

Bubble Sort

Advantages:

  • Simple to understand
  • Stable sorting algorithm
  • In-place sorting
  • Can detect if array is already sorted

Disadvantages:

  • Inefficient for large datasets
  • Many unnecessary comparisons
  • Generally slower than Insertion Sort
  • O(n²) average and worst-case complexity
Result: [1, 3, 5, 7, 8]

Performance Analysis

Key Findings: Both algorithms achieve the same result with O(n²) complexity, but Insertion Sort is generally more efficient due to fewer comparisons and data movements. Understanding the pseudocode implementation helps visualize how each algorithm processes data differently, and the C++ conversion demonstrates practical implementation considerations.

Recommendation: For educational purposes, both algorithms provide excellent learning opportunities. For practical applications with small datasets, Insertion Sort is preferable, while larger datasets require more advanced algorithms like Quick Sort or Merge Sort.

1 / 10