Learn how to implement the recursive bubble sort in javascript.
Bubble sort is one of the simplest sorting algorithms which sorts the elements by repeatedly swapping them if they are in the wrong order.
Example
Input: [-5, 2, 33, 10, -7] Output: //Sorted in ascending order [-7, -5, 2, 10, 33]
Check out the following image for a better understanding of bubble sort.
Implementation of recursive bubble sort
- We will mimic the iterative appraoch of the bubble sort to implement it recursively.
- We will create a function for sorting in which we will check if the array length is 1 then return the array.
- Else loop till the given length and swap the elements depending on their order.
- Recursively call the same function again with one element less.
//Recursive Bubble Sort
let recursiveBubbleSort = (arr, n = arr.length) => {
//If there is only single element
//the return the array
if(n == 1){
return arr;
}
//Swap the elements by comparing them
for(let j = 0; j < n - 1; j++){
if(arr[j] > arr[j + 1]){
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
//Recursively call the function to sort.
return recursiveBubbleSort(arr, n-1);
}
Input: console.log(recursiveBubbleSort([-5, 2, 33, 10, -7])); Output: [-7, -5, 2, 10, 33]
Time complexity: O(n ^ 2).
Space complexity: O(n).
Time and Space complexity of recursive bubble sort
- We are calling the same function recursively for each element of the array and inside the function, we are looping till the given length of the array, So Time complexity is O(n ^ n) = O(n ^ 2).
- We are recursively calling the function for each element of the array, So space complexity is O(n).