[go: up one dir, main page]
Scribd
Upload
3 views3 pages

Bubble Sorting an Array

Bubble Sort is a simple sorting algorithm that repeatedly compares and swaps adjacent elements until the array is sorted. The document provides a basic implementation in Java, an optimized version with an early exit condition, and discusses the time complexity and advantages/disadvantages of Bubble Sort. While it is easy to understand and implement, it is inefficient for large datasets compared to more advanced sorting algorithms.

Uploaded by

joashodchas09
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views3 pages

Bubble Sorting an Array

Bubble Sort is a simple sorting algorithm that repeatedly compares and swaps adjacent elements until the array is sorted. The document provides a basic implementation in Java, an optimized version with an early exit condition, and discusses the time complexity and advantages/disadvantages of Bubble Sort. While it is easy to understand and implement, it is inefficient for large datasets compared to more advanced sorting algorithms.

Uploaded by

joashodchas09
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Sorting an Array: Bubble Sort in Java

Sorting is an essential operation in programming, used to arrange elements in ascending or


descending order. One of the simplest sorting algorithms is Bubble Sort.

What is Bubble Sort?


Bubble Sort is a simple sorting algorithm that repeatedly steps through the array, compares
adjacent elements, and swaps them if they are in the wrong order. This process continues until
the entire array is sorted.

Working of Bubble Sort

1. Start at the beginning of the array.


2. Compare adjacent elements.
3. If the first element is greater than the second, swap them.
4. Move to the next pair of elements and repeat the process.
5. After each pass, the largest element moves to its correct position.
6. Repeat the passes until the array is sorted.

Bubble Sort Implementation in Java


Basic Implementation
import java.util.Arrays;

public class BubbleSort {


public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};

bubbleSort(arr);

System.out.println("Sorted Array: " + Arrays.toString(arr));


}

public static void bubbleSort(int[] arr) {


int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}

Explanation

 The outer loop runs n-1 times.


 The inner loop runs fewer times in each pass, since the largest element is placed at the
end.
 Swapping occurs whenever an adjacent element is out of order.

Optimized Bubble Sort (With Early Exit)


If no swaps occur during a pass, the array is already sorted, so we can terminate early.

import java.util.Arrays;

public class OptimizedBubbleSort {


public static void main(String[] args) {
int[] arr = {2, 3, 4, 5, 6}; // Already sorted

bubbleSort(arr);

System.out.println("Sorted Array: " + Arrays.toString(arr));


}

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 - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) { // If no swaps occurred, break early
break;
}
}
}
}
Why Optimize?

 The early exit condition improves performance for nearly sorted arrays.
 Reduces unnecessary iterations when no swaps occur.

Time Complexity Analysis


Case Complexity
Best Case (Already Sorted) O(n) (Optimized)
Average Case O(n²)
Worst Case (Reversed Order) O(n²)

 Best case: The optimized version stops in one pass if the array is already sorted.
 Worst case: Every element is out of order, requiring maximum swaps.

Advantages & Disadvantages of Bubble Sort


✅ Advantages

 Simple to understand and implement.


 Works well for small datasets.
 Can be optimized with an early exit condition.

❌ Disadvantages

 Inefficient for large datasets due to O(n²) complexity.


 Slower compared to advanced sorting algorithms like Quick Sort and Merge Sort.

Conclusion
Bubble Sort is a fundamental sorting algorithm, ideal for learning but not for large-scale
applications due to its inefficiency. However, understanding Bubble Sort helps in grasping more
complex sorting techniques like Quick Sort and Merge Sort.

You might also like