# Interview Questions

# Recursive Bubble Sort

- October 14, 2018
- Posted by: Kamal Rawat
- Category: Algorithms

Give the recursive implementation of the Bubble Sort algorithm

**Solution:**

We have already discussed the Bubble sort algorithm and its optimizations in this post. The iterative algorithm for bubble sort is shown below:

void bubbleSort(int *arr, int n) { 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], &arr[j+1]); } } }

The swap function is a normal swap function:

void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; }

This function takes O(n2) time and constant extra memory. In the recursive implementation, the function is supposed to perform one small task and rest is left for the recursive call. Let us define the recursion as below:

If there are n elements in the array, then the first function instance will move the largest element (out of these nĀ elements) to the last position of the array (a single pass of bubble sort) and then call the same function to sort the array of first n-1 elements.

The responsibility of sorting first n-1 elements is given to the recursive function call.

**Code:**

void bubbleSort(int *arr, int n) { // TERMINATING CONDITION OF RECURSION if(n <= 1){ return; } // MOVE THE LARGEST ELEMENT AT THE END for(int j=0; jarr[j+1]) swap(&arr[j], &arr[j+1]); } // CALL FUN RECURSIVELY TO SORT FIRST n-1 ELEMENTS bubbleSort(arr, n-1); }

Note that this recursive solution is not better than the iterative solution in any way. In fact, it is worse, because it takes O(n) extra space also along with multiple function calls.