Java Coding Test Course, Bubble Sort Program 2

1. Problem Overview

In this course, we will enhance our understanding of the bubble sort algorithm using Java and learn how to solve problems that are frequently presented in actual coding tests.
Bubble sort is one of the most basic sorting algorithms, and it is very useful when a sorted dataset is required.
The goal of this problem is to sort the given array in ascending order.

2. Problem Description

You are given the following array: 

        int[] array = {5, 2, 9, 1, 5, 6};

Write a program to sort this array in ascending order using the bubble sort algorithm.
The sorted result should be printed as follows: 

        Sorted array: [1, 2, 5, 5, 6, 9]

3. Problem-Solving Process

3.1. Understanding the Bubble Sort Algorithm

Bubble Sort works by repeatedly comparing adjacent elements in a list and swapping them if they are in the wrong order.
This process is repeated until all elements are sorted.

  • In the first pass, the largest number moves to the end.
  • In the next pass, the second largest number moves to the second last position.
  • This continues until the array is sorted.

The worst-case time complexity of bubble sort is O(n^2). However, due to its simplicity and ease of understanding, it is widely used for educational purposes.

3.2. Step-by-Step Implementation of Bubble Sort

To solve this problem, we will proceed with the following steps:

  1. Determine the length of the array.
  2. Use a nested loop to compare all elements of the array.
  3. Compare adjacent elements and swap them if they are not sorted.
  4. Repeat until all elements are sorted.

3.3. Implementing Code in Java

Now, let’s write the actual Java code based on the logic above.
Below is a Java program that sorts an array using bubble sort: 

        
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        bubbleSort(array);
        System.out.print("Sorted array: [");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // If no two elements were swapped, break
            if (!swapped) {
                break;
            }
        }
    }

4. Code Analysis

Let’s analyze the code.
In the code above, the main method initializes the array and then calls the bubbleSort method.
The bubbleSort method works as follows:

  • n stores the length of the array.
  • The swapped variable tracks whether a swap has occurred during a cycle.
  • The outer loop (for (int i = 0; i < n - 1; i++)) determines the number of overall cycles.
  • The inner loop compares adjacent elements and swaps them if necessary.
    It can perform up to O(n^2) comparisons in the worst case.
  • If no swaps occur during a cycle, the array is already sorted, and further repetition stops. This is an example of an optimized bubble sort.

4.1. Execution Result

When the program is run, the following result is printed: 

        Sorted array: [1, 2, 5, 5, 6, 9]

5. Efficiency Evaluation

Bubble sort is intuitive and easy to implement, but its time complexity of O(n^2) makes it inefficient.
For large datasets, other sorting algorithms (e.g., quick sort, merge sort, etc.) are more efficient.
However, it is suitable for learning algorithms and can be useful for small datasets.

6. Conclusion

Through this course, we learned the principles of bubble sort and how to implement it in Java.
Understanding sorting problems is very important in algorithmic problems.
To cultivate the ability to learn various sorting algorithms and choose the right one for the situation, a lot of practice is required.
We hope you will continue to improve your algorithm skills through various problems.