Bubble Sort Recursive
- Bubble Sort Recursive Algorithm
- Bubble Sort Recursive Algorithm Example
- Bubble Sort Recursive Algorithm Implementation
- Bubble Sort Algorithm Complexity
Bubble sort is a simple sorting algorithm. It works by repeated comparison of adjacent elements and swapping them if they are in the wrong order. The repeated comparisons bubble up the smallest/largest element towards the end of the array, and hence this algorithm is named bubble sort. Although inefficient, it still represents the foundation for sorting algorithms.
Bubble Sort Recursive Algorithm
Let us assume that we have an unsorted array A[]
containing n elements.
If the size of array
A
is1
, then the array is already sorted. So, return.Else, perform one pass of iterative bubble sort on the given subarray. It will place the last element at its correct position.
Use recursion call to perform the above steps again on a smaller subarray with size reduced by one.
Bubble Sort Recursive Algorithm Example
Suppose we have the array: (5,3,4,2,1)
. We will sort it using the bubble sort algorithm.
- First Pass:
(5 3 4 2 1) | → | (3 5 4 2 1) | (3 < 5 swapped) |
(3 5 4 2 1) | → | (3 4 5 2 1) | (4 < 5 swapped) |
(3 4 5 2 1) | → | (3 4 2 5 1) | (2 < 5 swapped) |
(3 4 2 5 1) | → | (3 4 2 1 5) | (1 < 5 swapped) |
- Second Pass:
(3 4 2 1 5) | → | (3 4 2 1 5) | |
(3 4 2 1 5) | → | (3 2 4 1 5) | (2 < 4 swapped) |
(3 2 4 1 5) | → | (3 2 1 4 5) | (1 < 4 swapped) |
- Third Pass:
(3 2 1 4 5) | → | (2 3 1 4 5) | (2 < 3 swapped) |
(2 3 1 4 5) | → | (2 1 3 4 5) | (1 < 3 swapped) |
- Fourth Pass:
(2 1 3 4 5) | → | (1 2 3 4 5) | (1 < 2 swapped) |
We get the sorted array after the fourth pass - (1 2 3 4 5)
Bubble Sort Recursive Algorithm Implementation
#include<bits/stdc++.h>
using namespace std;
void bubbleSort(int arr[], int n)
{
if (n == 1)return;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
}
}
bubbleSort(arr, n - 1);
}
int main() {
int n = 8;
int arr[8] = {9, 8 , 3 , 7, 5, 6, 4, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bubbleSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
Bubble Sort Algorithm Complexity
Time Complexity
- Average Case
On average, n-i
comparisons are made in the ith
pass of bubble sort. So if there are n passes, then the average time complexity can be given by below.
(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2
Hence the time complexity is of the order of O(n^{2}).
- Worst Case
The worst case occurs when the array is reversely sorted, and the maximum number of comparisons and swapping has to be performed.
The worst-case time complexity is O(n^{2}).
- Best Case
The best-case occurs when the array is already sorted, and then only N comparisons are required.
The best-case time complexity is O(n)
.
Space Complexity
Space Complexity for this algorithm is O(n)
due to the recursive calls stored inside the stack.