Bubble Sort in Java

Bubble sort is a popular sorting algorithm that is used to sort a given set of data in either ascending or descending order. It is a simple and efficient algorithm that works by comparing each pair of adjacent elements and swapping them if they are not in the correct order. Bubble sort is considered one of the easiest sorting algorithms to understand and implement. This article will provide an in-depth look at the bubble sort algorithm and how it works, as well as its time and space complexities. We will also discuss how to implement the bubble sort algorithm in Java and provide coding exercises at the end of the article to help you test your understanding of this sorting algorithm.

What is Bubble Sort?

Bubble sort is an algorithm used for sorting a given set of data. The algorithm works by repeatedly comparing adjacent elements and swapping them if they are not in the correct order. This process is repeated until the list is fully sorted. Bubble sort is a simple and intuitive sorting algorithm that is easy to understand and implement. It is also a stable sorting algorithm, meaning that elements that have the same value remain in the same order relative to each other after the sorting is completed.

How Bubble Sort Works

Bubble sort works by comparing each pair of adjacent elements and swapping them if they are not in the correct order. This process is repeated until the list is fully sorted. The algorithm can be broken down into the following steps:

1. Start at the beginning of the list and compare the first two elements.
2. If the first element is greater than the second element, swap them.
3. Move on to the next pair of elements and repeat step 2.
4. Continue steps 2 and 3 until you reach the end of the list.
5. If no swaps were made in the last iteration, the list is now sorted and the algorithm can end. Otherwise, go back to step 1.

Time Complexity of Bubble Sort

The time complexity of bubble sort depends on the number of elements in the list. In the best case, when the list is already sorted, the algorithm has a time complexity of O(n). This means that the time taken to sort the list is directly proportional to the number of elements in the list.

In the worst case, when the list is in reverse order, the time complexity of bubble sort is O(n2). This means that the time taken to sort the list is proportional to the square of the number of elements in the list.

The average time complexity of bubble sort is also O(n2). This means that on average, the time taken to sort the list is proportional to the square of the number of elements in the list.

Space Complexity of Bubble Sort

The space complexity of bubble sort is O(1). This means that the algorithm does not require any additional space for sorting and all of the sorting is done in-place.

Java Implementation of Bubble Sort

Now that we have discussed how bubble sort works and its time and space complexities, we can look at how to implement the algorithm in Java. The following code snippet shows a Java implementation of the bubble sort algorithm:

public static void bubbleSort(int[] arr) { 
    boolean swapped = true; 
    int j = 0; 
    int tmp; 
    while (swapped) { 
        swapped = false; 
        j++; 
        for (int i = 0; i < arr.length - j; i++) { 
            if (arr[i] > arr[i + 1]) { 
                tmp = arr[i]; 
                arr[i] = arr[i + 1]; 
                arr[i + 1] = tmp; 
                swapped = true; 
            } 
        } 
    } 
}

In the above code snippet, we have created a method called bubbleSort() that takes an array of integers as a parameter. We then have a loop that runs until no swaps have been made. In the loop, we compare each pair of adjacent elements and swap them if they are not in the correct order. Once the loop has finished, the array will be sorted.

Conclusion

In this article, we discussed the bubble sort algorithm and how it works. We also discussed its time and space complexities, as well as how to implement the algorithm in Java. Bubble sort is a simple and intuitive sorting algorithm that is easy to understand and implement. It is also a stable sorting algorithm and has a time complexity of O(n2) in the worst case and a space complexity of O(1).

Exercises

public static void sortArray(int[] arr) {
    bubbleSort(arr);
}

public static void sortArrayDescending(int[] arr) {
    bubbleSort(arr);
    for (int i = 0; i < arr.length/2; i++) {
        int temp = arr[i];
        arr[i] = arr[arr.length - 1 - i];
        arr[arr.length - 1 - i] = temp;
    }
}

public static void sortSubArray(int[] arr, int start, int end) {
    int[] subArray = new int[end-start+1];
    System.arraycopy(arr, start, subArray, 0, end-start+1);
    bubbleSort(subArray);
    System.arraycopy(subArray, 0, arr, start, end-start+1);
}

public static boolean isSorted(int[] arr) {
    int[] sortedArray = new int[arr.length];
    System.arraycopy(arr, 0, sortedArray, 0, arr.length);
    bubbleSort(sortedArray);
    return Arrays.equals(arr, sortedArray);
}

public static int findSmallestElement(int[] arr) {
    int smallestElement = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < smallestElement) {
            smallestElement = arr[i];
        }
    }
    return smallestElement;
}