Recursive Bubble Sort
def bubble_sort(list_data: list, length: int = 0) -> list:
"""
It is similar is bubble sort but recursive.
:param list_data: mutable ordered sequence of elements
:param length: length of list data
:return: the same list in ascending order
>>> bubble_sort([0, 5, 2, 3, 2], 5)
[0, 2, 2, 3, 5]
>>> bubble_sort([], 0)
[]
>>> bubble_sort([-2, -45, -5], 3)
[-45, -5, -2]
>>> bubble_sort([-23, 0, 6, -4, 34], 5)
[-23, -4, 0, 6, 34]
>>> bubble_sort([-23, 0, 6, -4, 34], 5) == sorted([-23, 0, 6, -4, 34])
True
>>> bubble_sort(['z','a','y','b','x','c'], 6)
['a', 'b', 'c', 'x', 'y', 'z']
>>> bubble_sort([1.1, 3.3, 5.5, 7.7, 2.2, 4.4, 6.6])
[1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7]
"""
length = length or len(list_data)
swapped = False
for i in range(length - 1):
if list_data[i] > list_data[i + 1]:
list_data[i], list_data[i + 1] = list_data[i + 1], list_data[i]
swapped = True
return list_data if not swapped else bubble_sort(list_data, length - 1)
if __name__ == "__main__":
import doctest
doctest.testmod()
About this Algorithm
Bubble Sort is one of the simplest sorting algorithms that compares two elements at a time and swaps them if they are in the wrong order. This process is repeated until the entire sequence is in order.
- Time Complexity:
O(n ^ 2)for average case;O(n)for best case. - Space Complexity:
O(n); note that iterative bubble sort has space complexity asO(1).
Steps
Base case: If the size of the array is 1, return.
- We need to fix the last element of the current sub-array. For this, iterate over the entire array using normal Bubble Sort, and perform swapping.
- Next, call the function on the entire array excluding the last element(which was fixed by the iteration in the above step)
- Repeat until Base Case is reached.
Example
Let the given array be: {5, 3, 2, 1, 4}
First Iteration:
- {
5,3, 2, 1, 4} -> {3,5, 2, 1, 4} Swap since5 > 3 - {3,
5,2, 1, 4} -> {3,2,5, 1, 4} Swap since5 > 2 - {3, 2,
5,1, 4} -> {3, 2,1,5, 4} Swap since5 > 1 - {3, 2, 1,
5,4} -> {3, 2, 1,4,5} Swap since5 > 4
This iteration has fixed the position of 5. Now, we will consider the array up to index 3.
Second Iteration:
- {
3,2, 1, 4, 5} -> {2,3, 1, 4, 5} Swap since3 > 2 - {2,
3,1, 4, 5} -> {2,1,3, 4, 5} Swap since3 > 1 - {2, 1,
3,4, 5}; As3 < 4, do not swap
Note: As we check one less element with every iteration, we do not need elements at index 3 and 4 i.e., 4 and 5, as 5 is already in order. Formally, for an array with n integers, we consider elements only up to index n - i, where i is the iteration number.
Third Iteration:
- {
2,1, 3, 4, 5} -> {1,2, 3, 4, 5} Swap since1 > 2 - {1,
2,3, 4, 5}; As2 < 3, do not swap
Fourth Iteration:
- {
1,2, 3, 4, 5}; As1 < 2, do not swap
Fifth Iteration:
- {
1, 2, 3, 4, 5}; As the size of the array is 1, return.
Note: This is the base case.
Pseudo Code
void bubbleSort(arr[], n)
if(n==1)
return;
for(i = 0; i<n-1; i++)
if(arr[i] > arr[i+1])
swap(arr[i], arr[i+1])
bubbleSort(arr, n-1)
Implementations
Video Explanation
A video explaining iterative as well as recursive bubble sort
Β© Alger 2022