Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Selection Sort Performance Analysis

Problem Statement

Write a Java program that measures the execution time of the Selection Sort algorithm for sorting arrays of integers in ascending order, testing arrays of increasing sizes (e.g., 10, 100, 1000 elements). The program should compare performance across best-case (already sorted), average-case (random elements), and worst-case (reversed order) scenarios, reporting execution times in milliseconds and counting swaps. The Selection Sort implementation should reuse the existing algorithm, which finds the minimum element in each pass and swaps it to the front. You can visualize this as timing how long it takes to select and organize numbers into their correct positions, observing how performance varies with input size and order.

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 swaps for each 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: Time = 0.03 ms, Swaps = 0
    • Size 10, Average Case: Time = 0.04 ms, Swaps = 4
    • Size 10, Worst Case: Time = 0.04 ms, Swaps = 4
  • Explanation: Best case requires no swaps, average and worst cases have similar swaps, with times consistent due to fixed comparisons.

Pseudocode

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)
            SET totalTime to 0
            SET totalSwaps to 0
            FOR i from 0 to runs-1
                CREATE copy of case array
                SET startTime to current nano time
                SET swaps to selectionSort(copy)
                SET endTime to current nano time
                ADD (endTime - startTime) to totalTime
                ADD swaps to totalSwaps
            ENDFOR
            PRINT case details, input array, sorted array
            PRINT average time in milliseconds and average swaps
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Reuse selectionSort: a. Initialize a counter swaps to 0. b. For each index i from 0 to n-1, find the minimum element’s index in arr[i..n-1]. c. Swap if needed, increment swaps, and return the count.
  2. Define generateBestCase: a. Create array [1, 2, ..., n] (already sorted).
  3. Define generateAverageCase: a. Create array with random integers in [0, 10^6].
  4. Define generateWorstCase: a. Create array [n, n-1, ..., 1] (reversed).
  5. Define toString: a. Convert array to a string, limiting output for large arrays.
  6. In main, test with: a. Array sizes: 10, 100, 1000. b. Cases: best (sorted), average (random), worst (reversed). c. Run each case 10 times, average times and swaps. d. Measure time using System.nanoTime(), convert to milliseconds.

Java Implementation

import java.util.*;

public class SelectionSortPerformanceAnalysis {
    // 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) {
        SelectionSortPerformanceAnalysis sorter = new SelectionSortPerformanceAnalysis();
        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) {
                long totalTime = 0;
                long 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;
                }
                double avgTimeMs = totalTime / (double) runs / 1_000_000.0; // Convert to ms
                double avgSwaps = totalSwaps / (double) runs;
                System.out.println(testCase.type + ":");
                System.out.println("Input Array: " + sorter.toString(testCase.arr));
                int[] sorted = testCase.arr.clone();
                sorter.selectionSort(sorted);
                System.out.println("Sorted Array: " + sorter.toString(sorted));
                System.out.printf("Average Time: %.2f ms\n", avgTimeMs);
                System.out.printf("Average Swaps: %.0f\n\n", 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]
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]
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]
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, ...]
Average Time: 0.20 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, ...]
Average Time: 0.25 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, ...]
Average Time: 0.26 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, ...]
Average Time: 2.00 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, ...]
Average Time: 2.50 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, ...]
Average Time: 2.60 ms
Average Swaps: 499

Explanation:

  • Size 10: Best case (0 swaps, minimal time), average and worst cases (~4 swaps, similar times due to fixed comparisons).
  • Size 100: Best case (0 swaps), average (~48 swaps), worst case (~49 swaps), with times scaling quadratically.
  • Size 1000: Best case (0 swaps), average (~496 swaps), worst case (~499 swaps), showing consistent time increase.
  • Times are averaged over 10 runs; Selection Sort’s time is driven by O(n²) comparisons, not swaps.

How It Works

  • selectionSort: Finds the minimum element in each pass, swaps it to the front, counts 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.
    • Measures time with System.nanoTime(), converts to milliseconds.
    • Reports average time and swaps.
  • Example Trace (Size 10, Worst Case):
    • Array: [10, 9, ..., 1].
    • Pass 1: Find min=1, swap with 10: [1, 9, ..., 2] (1 swap).
    • Total swaps: ~4. Time measured per run, averaged over 10 runs.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
selectionSortO(n²)O(1)
generateBestCaseO(n)O(n)
generateAverageCaseO(n)O(n)
generateWorstCaseO(n)O(n)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n²) for selectionSort (n passes, up to n comparisons each); O(n) for generating arrays and toString.
  • Space complexity: O(1) for selectionSort (in-place); O(n) for generating arrays and toString (array storage and string builder).
  • Selection Sort’s time is consistent across cases due to fixed O(n²) comparisons.

✅ Tip: Selection Sort’s performance is driven by comparisons, not swaps, making times similar across cases. Use System.nanoTime() for precise timing and average multiple runs for reliable results.

⚠ Warning: Selection Sort’s O(n²) complexity makes it slow for large arrays (e.g., n=1000). Limit output for large arrays to avoid overwhelming console logs.