Day 16: Bubble Sort and Selection Sort
Sorting algorithms are fundamental in computer science, playing a crucial role in organizing data efficiently. In this post, we will explore two classic sorting algorithms: Bubble Sort and Selection Sort. We will cover their explanations, implementations in Java, time complexity analyses, and example problems to solidify your understanding.
What is Bubble Sort?
Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted. The algorithm is called “Bubble Sort” because smaller elements “bubble” to the top of the list.
Implementation in Java
Here’s how you can implement Bubble Sort in Java:
javaCopy codepublic class BubbleSort {
public static 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 arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
}
}
Time Complexity Analysis
- Best Case: O(n) – The best case occurs when the array is already sorted. A single pass through the array will confirm this.
- Average Case: O(n²) – In most cases, the algorithm will require multiple passes to sort the data.
- Worst Case: O(n²) – This occurs when the array is sorted in reverse order.
While Bubble Sort is easy to understand and implement, it is not the most efficient for large datasets.
What is Selection Sort?
Selection Sort is another simple sorting algorithm that divides the input list into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the sorted region.
Implementation in Java
Here’s how to implement Selection Sort in Java:
javaCopy codepublic class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap arr[i] and arr[minIndex]
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
}
}
Time Complexity Analysis
- Best Case: O(n²) – There are no best cases; every iteration still requires checking all unsorted elements.
- Average Case: O(n²) – Similar to the worst case, the average time complexity is quadratic due to the nested loops.
- Worst Case: O(n²) – This occurs regardless of the initial order of the elements.
Selection Sort is also simple but generally performs better than Bubble Sort in practice, though both are not suitable for large datasets.
Example Problems
- Bubble Sort Example: Given an array of integers:
{5, 1, 4, 2, 8}, using Bubble Sort will transform it to{1, 2, 4, 5, 8}. - Selection Sort Example: Given an array of integers:
{29, 10, 14, 37, 13}, using Selection Sort will result in{10, 13, 14, 29, 37}.
Conclusion
Bubble Sort and Selection Sort are fundamental sorting algorithms that are easy to understand and implement. However, they are not the most efficient for large datasets. Understanding these algorithms provides a solid foundation for learning more complex sorting techniques.
In our next post, we will explore Insertion Sort and Merge Sort, diving deeper into their implementations and performance analyses. Stay tuned!
Also see: The Z Blogs
my other Blog: The Z Blog ZB
