Bubble Sort Performance Analysis
Problem Statement
Write a Java program that measures the execution time of the Bubble 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. The Bubble Sort implementation should reuse the existing algorithm, counting swaps and measuring time for each run. You can visualize this as timing how long it takes to organize a list of numbers, observing how Bubble Sort’s 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) for each array size and case, the number of swaps performed, and 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.02 ms, Swaps = 0
- Size 10, Average Case: Time = 0.05 ms, Swaps = 23
- Size 10, Worst Case: Time = 0.06 ms, Swaps = 45
- Explanation: Best case requires no swaps, average case has moderate swaps, worst case has maximum swaps, with times increasing accordingly.
Pseudocode
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 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 bubbleSort(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
- Reuse
bubbleSort: a. Initialize a counterswapsto 0. b. For each pass i from 0 to n-1, compare and swap if arr[j] > arr[j+1]. c. Return the number of swaps. - Define
generateBestCase: a. Create array [1, 2, ..., n] (already 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, e.g., "[1, 2, 3]". - 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 usingSystem.nanoTime(), convert to milliseconds.
Java Implementation
import java.util.*;
public class BubbleSortPerformanceAnalysis {
// 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]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = 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) {
BubbleSortPerformanceAnalysis sorter = new BubbleSortPerformanceAnalysis();
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.bubbleSort(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.bubbleSort(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.02 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.05 ms
Average Swaps: 22
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.06 ms
Average Swaps: 45
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.15 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: 1.80 ms
Average Swaps: 2478
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: 2.10 ms
Average Swaps: 4950
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: 1.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, ...]
Average Time: 180.00 ms
Average Swaps: 249750
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: 210.00 ms
Average Swaps: 499500
Explanation:
- Size 10: Best case (0 swaps, minimal time), average case (~22 swaps, moderate time), worst case (45 swaps, highest time).
- Size 100: Best case (0 swaps), average case (~2478 swaps), worst case (4950 swaps), with times scaling quadratically.
- Size 1000: Best case (0 swaps), average case (~249750 swaps), worst case (499500 swaps), showing significant time increase.
- Times are averaged over 10 runs for accuracy; actual values depend on system performance.
How It Works
- bubbleSort: Sorts in ascending order, counting swaps (reused from
BasicBubbleSort.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: Multiple swaps to move 1 to end.
- Total swaps: 45 (n*(n-1)/2 for reversed array).
- Time measured per run, averaged over 10 runs.
Complexity Analysis Table
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| bubbleSort | 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 bubbleSort (n passes, up to n-1 comparisons/swaps); O(n) for generating arrays and toString.
- Space complexity: O(1) for bubbleSort (in-place); O(n) for generating arrays and toString (array storage and string builder).
- Worst case: O(n²) time for reversed arrays; best case: O(n) time for sorted arrays.
✅ Tip: Use
System.nanoTime()for precise timing in performance analysis. Average multiple runs to reduce variability from system noise. Fixed seeds in random generation ensure reproducible results.
⚠ Warning: Bubble 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.