1. Problem Statement
Implement the bubble sort algorithm to sort the given integer array in ascending order.
Bubble sort is one of the simplest sorting algorithms, which sorts by comparing two adjacent elements.
The basic idea of this algorithm is to repeatedly compare each element of the array to send the smaller value forward.
2. Algorithm Explanation
The bubble sort algorithm works as follows:
- Compare two adjacent elements from the beginning to the end of the array. If the first element is greater than the second, swap the two elements.
- Repeat this process until reaching the end of the array.
- When reaching the end of the array, the largest element will have moved to the back.
- Repeat the above process for the size of the array – 1. In each iteration, the maximum value moves to the back of the array, so the remaining elements will be compared and swapped again.
3. Example
For example, let’s assume the given array is as follows:
[64, 34, 25, 12, 22, 11, 90]When applying bubble sort, the following steps occur:
- 1st pass: [34, 25, 12, 22, 11, 64, 90]
- 2nd pass: [25, 12, 22, 11, 34, 64, 90]
- 3rd pass: [12, 22, 11, 25, 34, 64, 90]
- 4th pass: [12, 11, 22, 25, 34, 64, 90]
- 5th pass: [11, 12, 22, 25, 34, 64, 90]
Once this process is completed, the array will be sorted in ascending order.
4. Java Implementation
The following is the Java code that implements the bubble sort algorithm described above:
public class BubbleSort {
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 elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // Indicate that a swap occurred
}
}
// If no swaps occurred, the array is already sorted, so exit
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
5. Code Explanation
The above code includes the following main features:
- bubbleSort method: Accepts an array and performs the bubble sort algorithm to sort it. Uses two nested loops to compare adjacent elements and swap them if necessary.
- swapped variable: This variable acts as a flag to indicate whether a swap occurred during the current pass. If no more swaps occur, the array is already sorted, so further passes can be skipped.
- main method: On execution, defines an example array and calls the bubble sort method. After sorting, it prints the result.
6. Performance Analysis
The time complexity of the bubble sort algorithm is O(n^2) in the worst and average cases. That is, when the length of the array is n, approximately n*(n-1)/2 comparisons are needed. In the best case (for an already sorted array), it shows O(n) performance. Because of this performance, bubble sort is suitable for small datasets, while other sorting algorithms (e.g., quicksort, merge sort, etc.) are more effective for large datasets.
7. Code Optimization and Improvement
Bubble sort is a simple and easy-to-learn algorithm, but there are several improvements worth considering for performance optimization:
- A swap flag can be used to detect if the array is already sorted.
- Since the last element is already sorted in each iteration, the range of the inner loop can be reduced.
- The entire loop can be shortened by checking for sorted status.
8. Conclusion
In this lecture, we implemented the bubble sort algorithm in Java. Learning the simplest form of sorting algorithms among various sorting algorithms greatly helps in understanding the basic principles of programming. Understand the basic structure and flow of the algorithm and improve your skills by implementing it in code. In the next lecture, we will cover more advanced sorting algorithms. Thank you!