📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.
✅ Some premium posts are free to read — no account needed. Follow me on Medium to stay updated and support my writing.
🎓 Top 10 Udemy Courses (Huge Discount): Explore My Udemy Courses — Learn through real-time, project-based development.
▶️ Subscribe to My YouTube Channel (172K+ subscribers): Java Guides on YouTube
Bubble Sort Overview
How Bubble Sort Works?
Bubble Sort Implementation
Iterative solution
// Simple logic using for loops
private 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 temp and arr[i]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
Recursive Solution
// recursive bubble sort
private void bubbleSort(int arr[], int n) {
// Base case
if (n == 1)
return;
// One pass of bubble sort. After
// this pass, the largest element
// is moved (or bubbled) to end.
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
// swap arr[i], arr[i+1]
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
// Largest element is fixed,
// recur for remaining array
bubbleSort(arr, n - 1);
}
Optimized Solution
// optimized
private void optimizedBubbleSort(int[] arr) {
int i = 0, n = arr.length;
boolean swapNeeded = true;
while (i < n - 1 && swapNeeded) {
swapNeeded = false;
for (int j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
swapNeeded = true;
}
}
if (!swapNeeded)
break;
i++;
}
}
Complete Program
import java.util.Arrays;
/**
* Class demonstrate the Bubble sorting algorithm
* @author Ramesh Fadatare
*
*/
public class BubbleSort {
// recursive bubble sort
private void bubbleSort(int arr[], int n) {
// Base case
if (n == 1)
return;
// One pass of bubble sort. After
// this pass, the largest element
// is moved (or bubbled) to end.
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
// swap arr[i], arr[i+1]
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
// Largest element is fixed,
// recur for remaining array
bubbleSort(arr, n - 1);
}
// Simple logic using for loops
private 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 temp and arr[i]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// optimized
private void optimizedBubbleSort(int[] arr) {
int i = 0, n = arr.length;
boolean swapNeeded = true;
while (i < n - 1 && swapNeeded) {
swapNeeded = false;
for (int j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
swapNeeded = true;
}
}
if (!swapNeeded)
break;
i++;
}
}
public static void main(String[] args) {
final int[] arr = { 1, 4, 5, 6, 7, 8, 2, 3 };
final BubbleSort bubbleSort = new BubbleSort();
System.out.println("Before sorting the array elements : " + Arrays.toString(arr));
bubbleSort.bubbleSort(arr);
System.out.println("After sorting the array elements : " + Arrays.toString(arr));
bubbleSort.optimizedBubbleSort(arr);
System.out.println("After sorting the array elements order : " + Arrays.toString(arr));
bubbleSort.bubbleSort(arr, arr.length);
System.out.println("After sorting the array elements order : " + Arrays.toString(arr));
}
}
Before sorting the array elements : [1, 4, 5, 6, 7, 8, 2, 3]
After sorting the array elements : [1, 2, 3, 4, 5, 6, 7, 8]
After sorting the array elements order : [1, 2, 3, 4, 5, 6, 7, 8]
After sorting the array elements order : [1, 2, 3, 4, 5, 6, 7, 8]
Performance
- Worst case complexity: O(n2)
- Best case complexity (Improved version): O(n)
- Average case complexity (Basic version): O(n2)
- Worst case space complexity: O(1) auxiliary
What do you use "swapNeeded" for?
ReplyDelete