Bubble Sort vs Quicksort: Implementation and Comparison in Java of Sorting Algorithms

Sorting algorithms are fundamental in computer science, and understanding their performance characteristics is crucial for efficient programming. In this blog post, we’ll dive into a head-to-head comparison of two popular sorting algorithms: Bubble Sort and Quicksort.

To implement and compare the time complexity of bubble sort and quicksort on a random array of integers in Java, we’ll create a program that generates a random array, sorts it using both algorithms and measures the execution time for each. Here’s a detailed implementation and analysis:

Implementation

//Implement and compare the time complexity of bubble sort and quicksort on a random array of integers
import java.util.Arrays;
import java.util.Random;

public class Task3 {
    public static void main(String[] args) {
        int[] sizes = {1000, 10000, 100000};
        for (int size : sizes) {
            int[] arr = generateRandomArray(size);
            
            // Bubble Sort
            int[] bubbleArr = Arrays.copyOf(arr, arr.length);
            long bubbleStartTime = System.nanoTime();
            bubbleSort(bubbleArr);
            long bubbleEndTime = System.nanoTime();
            long bubbleDuration = (bubbleEndTime - bubbleStartTime) / 1000000; // Convert to milliseconds
            
            // Quick Sort
            int[] quickArr = Arrays.copyOf(arr, arr.length);
            long quickStartTime = System.nanoTime();
            quickSort(quickArr, 0, quickArr.length - 1);
            long quickEndTime = System.nanoTime();
            long quickDuration = (quickEndTime - quickStartTime) / 1000000; // Convert to milliseconds
            
            System.out.println("Array size: " + size);
            System.out.println("Bubble Sort time: " + bubbleDuration + " ms");
            System.out.println("Quick Sort time: " + quickDuration + " ms");
            System.out.println();
        }
    }

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; 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;
                }
            }
        }
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static int[] generateRandomArray(int size) {
        Random rand = new Random();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = rand.nextInt(10000); // Generate random integers between 0 and 9999
        }
        return arr;
    }
}

This implementation includes both bubble sort and quicksort algorithms, as well as a method to generate random arrays of integers. The program tests both algorithms on arrays of different sizes (1000, 10000, and 100000 elements) and measures the execution time for each.

Time Complexity Analysis

Bubble Sort

• Best Case: O(n) — when the array is already sorted
• Average Case: O(n²)
• Worst Case: O(n²) — when the array is sorted in reverse order

Bubble sort has a quadratic time complexity, which makes it inefficient for large datasets. Its performance degrades quickly as the size of the input increases.

Quick Sort

• Best Case: O(n log n) — when the pivot chosen always divides the array into two halves
• Average Case: O(n log n)
• Worst Case: O(n²) — when the pivot is always the smallest or largest element, leading to unbalanced partitions

Quicksort generally performs much better than bubble sort, especially for larger datasets. Its average-case time complexity of O(n log n) makes it one of the fastest sorting algorithms in practice.

Comparison Results

When you run the program, you’ll see output similar to this:

These results demonstrate the performance difference between bubble sort and quicksort:

1. For small arrays (1000 elements), both algorithms perform relatively quickly, but quicksort is still faster.
2. As the array size increases to 10,000 elements, the difference becomes more pronounced. Bubble sort’s execution time grows quadratically, while quicksort remains efficient.
3. For large arrays (100,000 elements), the difference is dramatic. Bubble sort takes several seconds to complete, while quicksort finishes in milliseconds.

Conclusion

This comparison illustrates why quicksort is generally preferred over bubble sort for most practical applications:

1. Efficiency: Quicksort’s O(n log n) average-case time complexity makes it much more efficient than bubble sort’s O(n²) for large datasets.
2. Scalability: Quicksort’s performance scales well with increasing input sizes, while bubble sort’s performance degrades rapidly.
3. In-place sorting: Both algorithms sort in place, but Quicksort does so more efficiently.

However, it’s worth noting that for very small arrays or nearly sorted arrays, simpler algorithms like bubble sort or insertion sort might perform better due to their lower overhead. In practice, many programming languages and libraries use hybrid sorting algorithms that combine the strengths of different sorting methods for optimal performance across various input sizes and distributions.

So, whether you’re a tech enthusiast, a professional, or just someone who wants to learn more, I invite you to follow me on this journey. Subscribe to my blog and follow me on social media to stay in the loop and never miss a post.

Together, let’s explore the exciting world of technology and all it offers. I can’t wait to connect with you!”

Connect me on Social Media: https://linktr.ee/mdshamsfiroz

Happy coding! Happy learning!