Insertion Sort Performance Analysis

Problem Statement

Write a Java program that measures the execution time of the Insertion Sort algorithm for sorting arrays of integers in ascending order, testing arrays of increasing sizes (e.g., 10, 100, 1000 elements). Compare its performance with Bubble Sort and Selection Sort across best-case (already sorted), average-case (random elements), and worst-case (reversed order) scenarios, reporting execution times in milliseconds and counting shifts (for Insertion Sort) or swaps (for Bubble and Selection Sort). Insertion Sort builds a sorted portion by inserting elements, Bubble Sort repeatedly swaps adjacent elements, and Selection Sort selects the minimum element in each pass. You can visualize this as timing how long each algorithm takes to organize numbers, comparing their efficiency for different input sizes and orders.

Input:

Arrays of integers with sizes 10, 100, and 1000, generated for best (sorted), average (random), and worst (reversed) cases. Output: The execution time (in milliseconds) and number of shifts/swaps for each algorithm, array size, and case, along with a string representation of the input and sorted arrays for verification. Constraints:
Array sizes are 10, 100, 1000.
Array elements are integers in the range [0, 10^6] for random cases.
Execution times are averaged over multiple runs for accuracy. Example:
Input: Array size = 10, Cases: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (best), [5, 2, 8, 1, 9, 3, 7, 4, 6, 10] (average), [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] (worst)
Output (example, times vary):
- Size 10, Best Case:
  - Insertion Sort: Time = 0.02 ms, Shifts = 0
  - Bubble Sort: Time = 0.03 ms, Swaps = 0
  - Selection Sort: Time = 0.03 ms, Swaps = 0
- Size 10, Average Case:
  - Insertion Sort: Time = 0.03 ms, Shifts = 4
  - Bubble Sort: Time = 0.04 ms, Swaps = 5
  - Selection Sort: Time = 0.04 ms, Swaps = 4
Explanation: Insertion Sort performs best in the best case, while all algorithms have similar times for small arrays due to O(n²) complexity.

Pseudocode

FUNCTION insertionSort(arr)
    SET n to length of arr
    CREATE shifts as integer, initialized to 0
    FOR i from 1 to n-1
        SET key to arr[i]
        SET j to i - 1
        WHILE j >= 0 AND arr[j] > key
            SET arr[j + 1] to arr[j]
            INCREMENT shifts
            DECREMENT j
        ENDWHILE
        SET arr[j + 1] to key
    ENDFOR
    RETURN shifts
ENDFUNCTION

FUNCTION bubbleSort(arr)
    SET n to length of arr
    CREATE swaps as integer, initialized to 0
    FOR i from 0 to n-1
        FOR j from 0 to n-i-2
            IF arr[j] > arr[j + 1] THEN
                SET temp to arr[j]
                SET arr[j] to arr[j + 1]
                SET arr[j + 1] to temp
                INCREMENT swaps
            ENDIF
        ENDFOR
    ENDFOR
    RETURN swaps
ENDFUNCTION

FUNCTION selectionSort(arr)
    SET n to length of arr
    CREATE swaps as integer, initialized to 0
    FOR i from 0 to n-1
        SET minIdx to i
        FOR j from i+1 to n-1
            IF arr[j] < arr[minIdx] THEN
                SET minIdx to j
            ENDIF
        ENDFOR
        IF minIdx != i THEN
            SET temp to arr[i]
            SET arr[i] to arr[minIdx]
            SET arr[minIdx] to temp
            INCREMENT swaps
        ENDIF
    ENDFOR
    RETURN swaps
ENDFUNCTION

FUNCTION generateBestCase(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to i + 1
    ENDFOR
    RETURN arr
ENDFUNCTION

FUNCTION generateAverageCase(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to random integer in [0, 10^6]
    ENDFOR
    RETURN arr
ENDFUNCTION

FUNCTION generateWorstCase(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to n - i
    ENDFOR
    RETURN arr
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET sizes to [10, 100, 1000]
    SET runs to 10
    FOR each size in sizes
        SET bestArr to generateBestCase(size)
        SET avgArr to generateAverageCase(size)
        SET worstArr to generateWorstCase(size)
        FOR each case (bestArr, avgArr, worstArr)
            FOR each algorithm (insertionSort, bubbleSort, selectionSort)
                SET totalTime to 0
                SET totalOperations to 0
                FOR i from 0 to runs-1
                    CREATE copy of case array
                    SET startTime to current nano time
                    SET operations to algorithm(copy)
                    SET endTime to current nano time
                    ADD (endTime - startTime) to totalTime
                    ADD operations to totalOperations
                ENDFOR
                PRINT algorithm, case details, input array, sorted array
                PRINT average time in milliseconds and average operations
            ENDFOR
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

Reuse insertionSort: a. Initialize shifts to 0. b. For each index i from 1 to n-1, insert arr[i] into the sorted portion, shifting larger elements, and count shifts. c. Return the number of shifts.
Define bubbleSort: a. Initialize swaps to 0. b. Repeatedly swap adjacent elements if out of order, counting swaps. c. Return the number of swaps.
Define selectionSort: a. Initialize swaps to 0. b. For each index i, find the minimum in arr[i..n-1], swap if needed, and count swaps. c. Return the number of swaps.
Define generateBestCase: a. Create array [1, 2, ..., n] (sorted).
Define generateAverageCase: a. Create array with random integers in [0, 10^6].
Define generateWorstCase: a. Create array [n, n-1, ..., 1] (reversed).
Define toString: a. Convert array to a string, limiting output for large arrays.
In main, test with: a. Array sizes: 10, 100, 1000. b. Cases: best (sorted), average (random), worst (reversed). c. Run each case 10 times for each algorithm, average times and operations. d. Measure time using System.nanoTime(), convert to milliseconds.

Java Implementation

import java.util.*;

public class InsertionSortPerformanceAnalysis {
    // Performs Insertion Sort and counts shifts
    public int insertionSort(int[] arr) {
        int n = arr.length;
        int shifts = 0;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                shifts++;
                j--;
            }
            arr[j + 1] = key;
        }
        return shifts;
    }

    // Performs Bubble Sort and counts swaps
    public int bubbleSort(int[] arr) {
        int n = arr.length;
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swaps++;
                }
            }
        }
        return swaps;
    }

    // Performs Selection Sort and counts swaps
    public int selectionSort(int[] arr) {
        int n = arr.length;
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
                swaps++;
            }
        }
        return swaps;
    }

    // Generates best-case array (sorted)
    private int[] generateBestCase(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        return arr;
    }

    // Generates average-case array (random)
    private int[] generateAverageCase(int n) {
        Random rand = new Random(42); // Fixed seed for reproducibility
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(1000001); // [0, 10^6]
        }
        return arr;
    }

    // Generates worst-case array (reversed)
    private int[] generateWorstCase(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = n - i;
        }
        return arr;
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        int limit = Math.min(arr.length, 10); // Limit output for large arrays
        for (int i = 0; i < limit; i++) {
            result.append(arr[i]);
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            result.append("]");
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        int size;
        String type;
        int[] arr;

        TestCase(int size, String type, int[] arr) {
            this.size = size;
            this.type = type;
            this.arr = arr;
        }
    }

    // Main method to test performance
    public static void main(String[] args) {
        InsertionSortPerformanceAnalysis sorter = new InsertionSortPerformanceAnalysis();
        int[] sizes = {10, 100, 1000};
        int runs = 10;

        // Run test cases
        for (int size : sizes) {
            System.out.println("Array Size: " + size);
            TestCase[] cases = {
                new TestCase(size, "Best Case", sorter.generateBestCase(size)),
                new TestCase(size, "Average Case", sorter.generateAverageCase(size)),
                new TestCase(size, "Worst Case", sorter.generateWorstCase(size))
            };

            for (TestCase testCase : cases) {
                System.out.println(testCase.type + ":");
                System.out.println("Input Array: " + sorter.toString(testCase.arr));
                int[] sorted = testCase.arr.clone();
                sorter.insertionSort(sorted); // For display
                System.out.println("Sorted Array: " + sorter.toString(sorted));

                // Test Insertion Sort
                long totalTime = 0;
                long totalShifts = 0;
                for (int i = 0; i < runs; i++) {
                    int[] arr = testCase.arr.clone();
                    long startTime = System.nanoTime();
                    int shifts = sorter.insertionSort(arr);
                    long endTime = System.nanoTime();
                    totalTime += (endTime - startTime);
                    totalShifts += shifts;
                }
                double avgTimeMs = totalTime / (double) runs / 1_000_000.0; // Convert to ms
                double avgShifts = totalShifts / (double) runs;
                System.out.printf("Insertion Sort - Average Time: %.2f ms, Average Shifts: %.0f\n", avgTimeMs, avgShifts);

                // Test Bubble Sort
                totalTime = 0;
                long totalSwaps = 0;
                for (int i = 0; i < runs; i++) {
                    int[] arr = testCase.arr.clone();
                    long startTime = System.nanoTime();
                    int swaps = sorter.bubbleSort(arr);
                    long endTime = System.nanoTime();
                    totalTime += (endTime - startTime);
                    totalSwaps += swaps;
                }
                avgTimeMs = totalTime / (double) runs / 1_000_000.0;
                double avgSwaps = totalSwaps / (double) runs;
                System.out.printf("Bubble Sort - Average Time: %.2f ms, Average Swaps: %.0f\n", avgTimeMs, avgSwaps);

                // Test Selection Sort
                totalTime = 0;
                totalSwaps = 0;
                for (int i = 0; i < runs; i++) {
                    int[] arr = testCase.arr.clone();
                    long startTime = System.nanoTime();
                    int swaps = sorter.selectionSort(arr);
                    long endTime = System.nanoTime();
                    totalTime += (endTime - startTime);
                    totalSwaps += swaps;
                }
                avgTimeMs = totalTime / (double) runs / 1_000_000.0;
                avgSwaps = totalSwaps / (double) runs;
                System.out.printf("Selection Sort - Average Time: %.2f ms, Average Swaps: %.0f\n\n", avgTimeMs, avgSwaps);
            }
        }
    }
}

Output

Running the main method produces (times vary by system, example shown):

Array Size: 10
Best Case:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Insertion Sort - Average Time: 0.02 ms, Average Shifts: 0
Bubble Sort - Average Time: 0.03 ms, Average Swaps: 0
Selection Sort - Average Time: 0.03 ms, Average Swaps: 0

Average Case:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178]
Sorted Array: [333, 360, 289796, 304135, 374316, 628178, 648054, 727595, 766336, 767890]
Insertion Sort - Average Time: 0.03 ms, Average Shifts: 4
Bubble Sort - Average Time: 0.04 ms, Average Swaps: 5
Selection Sort - Average Time: 0.04 ms, Average Swaps: 4

Worst Case:
Input Array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Insertion Sort - Average Time: 0.04 ms, Average Shifts: 45
Bubble Sort - Average Time: 0.05 ms, Average Swaps: 45
Selection Sort - Average Time: 0.04 ms, Average Swaps: 4

Array Size: 100
Best Case:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Insertion Sort - Average Time: 0.10 ms, Average Shifts: 0
Bubble Sort - Average Time: 0.30 ms, Average Swaps: 0
Selection Sort - Average Time: 0.25 ms, Average Swaps: 0

Average Case:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178, ...]
Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
Insertion Sort - Average Time: 0.20 ms, Average Shifts: 2450
Bubble Sort - Average Time: 0.35 ms, Average Swaps: 2450
Selection Sort - Average Time: 0.30 ms, Average Swaps: 48

Worst Case:
Input Array: [100, 99, 98, 97, 96, 95, 94, 93, 92, 91, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Insertion Sort - Average Time: 0.25 ms, Average Shifts: 4950
Bubble Sort - Average Time: 0.40 ms, Average Swaps: 4950
Selection Sort - Average Time: 0.30 ms, Average Swaps: 49

Array Size: 1000
Best Case:
Input Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Insertion Sort - Average Time: 1.00 ms, Average Shifts: 0
Bubble Sort - Average Time: 3.00 ms, Average Swaps: 0
Selection Sort - Average Time: 2.50 ms, Average Swaps: 0

Average Case:
Input Array: [727595, 333, 648054, 374316, 767890, 360, 766336, 304135, 289796, 628178, ...]
Sorted Array: [90, 333, 360, 1350, 2734, 3965, 6618, 10422, 13764, 16008, ...]
Insertion Sort - Average Time: 2.20 ms, Average Shifts: 249500
Bubble Sort - Average Time: 3.50 ms, Average Swaps: 249500
Selection Sort - Average Time: 3.00 ms, Average Swaps: 496

Worst Case:
Input Array: [1000, 999, 998, 997, 996, 995, 994, 993, 992, 991, ...]
Sorted Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]
Insertion Sort - Average Time: 2.50 ms, Average Shifts: 499500
Bubble Sort - Average Time: 4.00 ms, Average Swaps: 499500
Selection Sort - Average Time: 3.00 ms, Average Swaps: 499

Explanation:

Size 10: Insertion Sort is fastest in best case (0 shifts), slightly better than Bubble and Selection Sort in average/worst cases.
Size 100: Insertion Sort outperforms Bubble Sort in all cases; Selection Sort has fewer swaps but similar times due to O(n²) comparisons.
Size 1000: Insertion Sort is consistently faster, especially in best case; Bubble Sort is slowest; Selection Sort has fewer swaps but similar times.
Times are averaged over 10 runs; Insertion Sort excels in best case, while all algorithms have O(n²) complexity.

How It Works

insertionSort: Inserts each element into the sorted portion, shifting larger elements, counting shifts (reused from BasicInsertionSort.md).
bubbleSort: Repeatedly swaps adjacent elements if out of order, counting swaps (reused from BasicBubbleSort.md).
selectionSort: Finds the minimum element in each pass, swaps if needed, counting swaps (reused from BasicSelectionSort.md).
generateBestCase: Creates sorted array [1, 2, ..., n].
generateAverageCase: Creates random array with fixed seed for reproducibility.
generateWorstCase: Creates reversed array [n, n-1, ..., 1].
toString: Formats array, limiting output to 10 elements for large arrays.
Main Method:
- Tests sizes 10, 100, 1000.
- For each size, runs best, average, and worst cases 10 times for each algorithm.
- Measures time with System.nanoTime(), converts to milliseconds.
- Reports average time and shifts/swaps.
Example Trace (Size 10, Worst Case, Insertion Sort):
- Array: [10, 9, ..., 1].
- i=1: key=9, shift 10: [10, 9, ...] (1 shift).
- Total shifts: ~45. Time measured per run, averaged over 10 runs.

Complexity Analysis Table

Operation	Time Complexity	Space Complexity
insertionSort	O(n²) worst, O(n) best	O(1)
bubbleSort	O(n²)	O(1)
selectionSort	O(n²)	O(1)
generateBestCase	O(n)	O(n)
generateAverageCase	O(n)	O(n)
generateWorstCase	O(n)	O(n)
toString	O(n)	O(n)

Note:

n is the array length.
Time complexity: O(n²) for all algorithms in worst/average cases; Insertion Sort is O(n) in best case; O(n) for generating arrays and toString.
Space complexity: O(1) for sorting algorithms (in-place); O(n) for generating arrays and toString (array storage and string builder).
Insertion Sort minimizes operations in best case, while Selection Sort minimizes swaps in all cases.

✅ Tip: Insertion Sort is highly efficient for nearly sorted arrays due to O(n) best-case complexity. Use System.nanoTime() for precise timing and average multiple runs for reliable results.

⚠ Warning: Bubble Sort is generally slower due to frequent swaps. Limit output for large arrays to avoid overwhelming console logs.

Keyboard shortcuts

Java Data Structures and Algorithms for Beginners