Java Bubble Sort Algorithm

Question

Answers ( 1 )

    0
    2024-01-29T19:46:36+00:00

    Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

    Here is a detailed description and an example of the Bubble Sort algorithm in Java:

    Bubble Sort Algorithm in Java

    1. Starting from the first element: The algorithm starts by comparing the first two elements of the array.

    2. Comparing Adjacent Elements: If the first element is greater than the second element, they are swapped. This operation is performed for all adjacent pairs of elements in the array.

    3. Repeat the Process: The above process is repeated, but with each pass, the largest element among the unsorted elements is bubbled up to its correct position. This is because, with each iteration, the largest element in the unsorted part will move to the end.

    4. Termination: The algorithm stops when no more swaps are needed, which means the array is sorted.

    Java Code Example

    public class BubbleSort {
        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]) {
                        // swap arr[j+1] and arr[j]
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
        }
    
        // Method to test the above algorithm
        public static void main(String args[]) {
            BubbleSort ob = new BubbleSort();
            int arr[] = {64, 34, 25, 12, 22, 11, 90};
            ob.bubbleSort(arr);
            System.out.println("Sorted array");
            for (int i=0; i < arr.length; i++)
                System.out.print(arr[i] + " ");
        }
    }
    

    In this code, bubbleSort is a method that implements the bubble sort algorithm. The main method tests the bubbleSort method with an example array.

    Complexity and Performance

    • Time Complexity: Worst and Average Case - O(n^2), Best Case - O(n) when the array is already sorted.
    • Space Complexity: O(1), as it requires only a constant amount of additional space.

    Alternatives

    While bubble sort is a simple and easy-to-understand algorithm, it is not efficient for large datasets. Alternatives like Quick Sort, Merge Sort, and Heap Sort are generally preferred for their better performance in most cases.

Leave an answer