Hi everyone, inside this article we will see the concept about Bubble Sort Analysis.
Bubble sort is a simple, yet inefficient sorting algorithm used to arrange elements in a list or array in ascending or descending order. It gets its name from the way elements “bubble” to the top of the list during each iteration of the algorithm.
How does Bubble Sort Work?
Bubble sort works by repeatedly comparing adjacent elements in a list or array and swapping them if they are in the wrong order. During each pass over the list, the largest (or smallest) element “bubbles” up to its correct position at the end (or beginning) of the list. This process is repeated until the entire list is sorted.
Here is an example of how bubble sort works on a list of integers:
Consider the list [5, 2, 8, 3, 1, 9]
First pass:
- Compare 5 and 2: swap them to get [2, 5, 8, 3, 1, 9]
- Compare 5 and 8: do not swap, list remains [2, 5, 8, 3, 1, 9]
- Compare 8 and 3: swap them to get [2, 5, 3, 8, 1, 9]
- Compare 8 and 1: swap them to get [2, 5, 3, 1, 8, 9]
- Compare 8 and 9: do not swap, list remains [2, 5, 3, 1, 8, 9]
After the first pass, the largest element (9) is in its correct position at the end of the list.
Second pass:
- Compare 2 and 5: do not swap, list remains [2, 5, 3, 1, 8, 9]
- Compare 5 and 3: swap them to get [2, 3, 5, 1, 8, 9]
- Compare 5 and 1: swap them to get [2, 3, 1, 5, 8, 9]
- Compare 5 and 8: do not swap, list remains [2, 3, 1, 5, 8, 9]
After the second pass, the second largest element (8) is in its correct position, and so on.
The process continues for the remaining elements until the entire list is sorted.
Bubble sort has a time complexity of O(n^2) in the worst case, where n is the number of elements in the list. This makes it inefficient for large lists, but it can be useful for small lists or educational purposes due to its simplicity.
Algorithm of Bubble Sort
The algorithm for bubble sort is as follows:
- Start with an unsorted list of n elements.
- Set a flag to track whether any swaps were made during a pass.
- Repeat the following steps for n-1 passes: a. For each pass, iterate over the list from the first element to the last unsorted element. b. Compare each adjacent pair of elements, and if they are in the wrong order, swap them. c. If any swaps were made during the pass, set the flag to True. d. If no swaps were made during the pass, the list is already sorted, so we can stop iterating.
- Return the sorted list.
Here is the bubble sort algorithm in pseudocode:
function bubbleSort(list):
n = length(list)
for i from 0 to n-1:
swapped = False
for j from 0 to n-i-1:
if list[j] > list[j+1]:
swap(list[j], list[j+1])
swapped = True
if not swapped:
break
return listIn this algorithm, we use two nested loops to iterate over the list and compare adjacent elements. We also use a flag swapped to track whether any swaps were made during a pass, and we break out of the outer loop if no swaps were made, indicating that the list is already sorted. Finally, we return the sorted list after all passes are complete.
Example
// C++ program for implementation
// of Bubble sort
#include <bits/stdc++.h>
using namespace std;
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
// Last i elements are already
// in place
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
// Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code
int main()
{
int arr[] = {5, 1, 4, 2, 8};
int N = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, N);
cout << "Sorted array: \n";
printArray(arr, N);
return 0;
}
The above program will output:
Sorted array:
1 2 4 5 8 Time Complexity: O(N2)
Auxiliary Space: O(1)
Optimized Implementation of Bubble Sort
Bubble sort can be optimized in several ways to improve its performance, especially for large lists. Here are some of the common optimizations for bubble sort:
- Stop iterating if the list is already sorted: Bubble sort can be inefficient if the list is already sorted or nearly sorted. To avoid unnecessary comparisons and swaps, we can check if any swaps were made during an iteration. If no swaps were made, it means that the list is already sorted, and we can stop iterating.
- Reduce the number of comparisons: Bubble sort compares adjacent elements in the list, even if they are already in the correct order. We can optimize bubble sort by reducing the number of comparisons in each pass by iterating only up to the last unsorted element. This means that we don’t need to compare elements that are already sorted.
- Reduce the number of swaps: Bubble sort swaps adjacent elements if they are in the wrong order, even if they are far apart from each other. This can result in unnecessary swaps and slow down the algorithm. We can optimize bubble sort by adding a flag that tracks whether any swaps were made during a pass. If no swaps were made, we can stop swapping, since the remaining elements are already in their correct positions.
Here is the optimized implementation of bubble sort with the above optimizations:
function bubbleSort(list):
n = length(list)
for i from 0 to n-1:
swapped = False
for j from 0 to n-i-1:
if list[j] > list[j+1]:
swap(list[j], list[j+1])
swapped = True
if not swapped:
break
In this optimized implementation, we added a flag swapped to track whether any swaps were made during a pass. We also added a check to break out of the loop if no swaps were made during a pass, indicating that the list is already sorted.
Example
// Optimized implementation of Bubble sort
#include <bits/stdc++.h>
using namespace std;
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n - 1; i++)
{
swapped = false;
for (j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// IF no two elements were swapped
// by inner loop, then break
if (swapped == false)
break;
}
}
// Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << " " << arr[i];
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int N = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, N);
cout << "Sorted array: \n";
printArray(arr, N);
return 0;
}
The above program will output:
Sorted array:
11 12 22 25 34 64 90Time Complexity: O(N2)
Auxiliary Space: O(1)
Worst Case Analysis for Bubble Sort
The worst-case analysis for bubble sort involves considering the scenario in which the input list is in reverse order. In this case, the largest element “bubbles” to the beginning of the list in the first pass, and then each subsequent pass only moves the second largest element to its correct position. Therefore, bubble sort requires n-1 passes over the list to fully sort it, where n is the number of elements in the list.
During each pass, bubble sort makes n-1 comparisons between adjacent elements in the list. Therefore, the total number of comparisons in the worst case is (n-1) * (n-1) = n^2 – 2n + 1.
In addition, bubble sort swaps adjacent elements that are in the wrong order during each pass. In the worst case, the list is in reverse order, so bubble sort needs to swap every adjacent pair of elements during each pass. Therefore, the total number of swaps in the worst case is also (n-1) * (n-1) = n^2 – 2n + 1.
As a result, the worst-case time complexity of bubble sort is O(n^2). This means that the time it takes to sort a list of n elements grows exponentially with n. For very large lists, bubble sort can be very slow compared to more efficient sorting algorithms like quicksort or mergesort, which have a worst-case time complexity of O(n log n). However, for small or already partially sorted lists, bubble sort may perform relatively well.
Where is the Bubble sort algorithm used?
Bubble sort is a simple and intuitive algorithm that can be used to sort small lists or arrays of elements. However, due to its inefficiency, bubble sort is rarely used in practice for large datasets. Instead, other more efficient sorting algorithms like quicksort, mergesort, or heapsort are preferred.
Bubble sort can be useful for educational purposes or for learning about sorting algorithms, as it is easy to understand and implement. It can also be used in situations where the input list is nearly sorted or already partially sorted, as bubble sort performs well in such cases.
Bubble sort is a simple and intuitive sorting algorithm that has both advantages and disadvantages. Here are some of them:
Advantages:
- Easy to understand and implement: Bubble sort is one of the simplest sorting algorithms to understand and implement. It requires only basic programming knowledge and can be a good algorithm to teach to beginners.
- Low space complexity: Bubble sort requires only a constant amount of extra space to store a temporary variable for swapping elements. This makes it a good choice when memory usage is a concern.
- Stable sorting algorithm: Bubble sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the list. This can be important in certain applications where maintaining the order of equal elements is necessary.
Disadvantages:
- Inefficient for large datasets: Bubble sort has a worst-case time complexity of O(n^2), which makes it inefficient for large datasets. It can take a long time to sort a list with many elements compared to more efficient sorting algorithms like quicksort or mergesort.
- Inefficient for nearly sorted or partially sorted lists: Bubble sort requires n-1 passes over the list to fully sort it, where n is the number of elements in the list. This means that it is not very efficient when the input list is nearly sorted or already partially sorted.
- Not suitable for real-time applications: Bubble sort is not suitable for real-time applications where speed is critical. Other sorting algorithms that have faster time complexity are preferred in such cases.
In summary, while bubble sort has some advantages like simplicity, low space complexity, and stability, its inefficiency for large datasets and nearly sorted lists make it less desirable in many practical applications.
We hope this article helped you to understand Bubble Sort Analysis in a very detailed way.
Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.
If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.