Understanding Recursion (applying it on Bubble Sort)

Question

I am trying to figure out how to use recursion in programs. I understand how recursion works in classical examples like "factorial", but am not sure how to apply it on my own...

I am starting out with converting an iterative bubble sort code into a recursive code... I have searched over the net for the same.... but am not able to find a convincing solution/explanation..

Example iterative code for bubble sort is:

arr[n]-> array with elements (1..n) which is to be sorted

for(i:1 to n)  
    for(j:1 to n-1)  
      if(arr[j+1]>arr[j])  
         swap(arr[j+1],arr[j]);

Would feel helpful if someone could give a hint about how to go about...

Answer 1

Hope this helps.

    public class Main {
public static void swapping(int[] arr2, int m, int n) {
    if (m == n) {
        return;
    }
    if (arr2[m - 1] > arr2[m]) {
        int temp = arr2[m];
        arr2[m] = arr2[m - 1];
        arr2[m - 1] = temp;
    }
    
    swapping(arr2, m + 1, n);
}

public static int[] recurrsionBubbleSort(int[] arr2, int n) {
    if (n == 1) {
        return arr2;
    }
    /*
    IF YOU DONT WANT TO USE ITERATION AT ALL, SKIP THIS STEP AND USE SWAPPING() FUNCTION.
    for(int j=1;j<n;j++){
        if(arr2[j-1]>arr2[j]){
            int temp=arr2[j];
                arr2[j]=arr2[j-1];
                arr2[j-1]=temp;
        }
    }
    */
    swapping(arr2, 1, n);
    recurrsionBubbleSort(arr2, n - 1);
    
    return arr2;
}

public static void main(String[] args) {

    int[] arr2 = new int[] {8,2,4,5,1,0,7,6};
    System.out.println("Sorting using recursion");
    recurrsionBubbleSort(arr2, arr2.length);
    for (int i = 0; i < arr2.length; i++) {
        System.out.println(arr2[i]);
    }
 }
}

Answer 2

Golang:

// BubbleSortRecursive ...
func BubbleSortRecursive(data []int) {

    i := 0
    max := len(data)

    bubbleSortRecursive(data, i, max)
}

func bubbleSortRecursive(data []int, i, max int) {

    fmt.Printf("data = %v, i = %v, max = %v\n", data, i, max)

    if i == max-1 {
        max--
        i = 0
    }

    if i < max-1 {
        if data[i] > data[i+1] {
            data[i], data[i+1] = data[i+1], data[i]
        }
        bubbleSortRecursive(data, i+1, max)
    }
}

Answer 3

package com.examplehub.sorts;

public class BubbleSortRecursion implements Sort {
  @Override
  public void sort(int[] numbers) {
    sortRecursion(numbers, numbers.length);
  }

  /**
   * BubbleSort algorithm implements using recursion.
   *
   * @param numbers the numbers to be sorted.
   * @param length the length of numbers.
   */
  public void sortRecursion(int[] numbers, int length) {
    boolean swapped = false;
    for (int i = 0; i < length - 1; ++i) {
      if (numbers[i] > numbers[i + 1]) {
        int temp = numbers[i];
        numbers[i] = numbers[i + 1];
        numbers[i + 1] = temp;
        swapped = true;
      }
    }
    if (!swapped) {
      return;
    }
    sortRecursion(numbers, length - 1);
  }

  @Override
  public <T extends Comparable<T>> void sort(T[] array) {
    sortRecursion(array, array.length);
  }

  /**
   * Generic BubbleSort algorithm implements using recursion.
   *
   * @param array the array to be sorted.
   * @param length the length of array.
   * @param <T> the class of the objects in the array.
   */
  public <T extends Comparable<T>> void sortRecursion(T[] array, int length) {
    boolean swapped = false;
    for (int i = 0; i < length - 1; ++i) {
      if (array[i].compareTo(array[i + 1]) > 0) {
        T temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped = true;
      }
    }
    if (!swapped) {
      return;
    }
    sortRecursion(array, length - 1);
  }
}

source from

Answer 4

Here is another easy way to sort your array recursively using Bubble-Sort.

static void recursive_bubble_sort(int[] Arr, int l)
{// 'Arr' is the array where 'l' is the length of the array

    if (l == 0) {
       return;
    }

    for (int j = 0; j < l - 1; j++) {
        if (Arr[j] > Arr[j + 1]) {
            swap(Arr[j], Arr[j + 1]);
        }
    }

    recursive_bubble_sort(Arr, l - 1);
}

For recursive solution, the length must be updated so function always works with the remaining items from array.

Answer 5

Here's another javascript recursion version with some es6/7 syntax such as default argument parameters:

let unsorted = [4, 2, 4, 99, 1, 1, 5];

const bubSort = (arr, end = 0) => {
  // base case
  if (end >= arr.length) {
    return arr;
  }

  // bubble sort, goes through once
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      // swap!
      let hold = arr[i + 1];
      arr[i + 1] = arr[i];
      arr[i] = hold;
    }
  }

  // down the rabbit hole; updating `end` is a small optimization
  return bubSort(arr, ++end);
}

const sorted = bubSort(unsorted);
console.log(sorted);

Answer 6

Here is scala functional code. Everything is immutable. And this is tail recursion. So the stack should be fine

def sort(initial: List[Int], result: List[Int] = Nil): List[Int] = {

  def getBiggest(list: List[Int], rest: List[Int] = Nil): (List[Int], Int) = list match {
    case x1 :: x2 :: tail =>
      if(x1 > x2)
        getBiggest(x1 :: tail, x2 :: rest)
      else
        getBiggest(x2 :: tail, x1 :: rest)
    case x :: Nil => (rest, x)
  }

  initial match {
    case _ :: _ :: _ =>
      getBiggest(initial) match {
        case (rest, biggest) => sort(rest, biggest :: result)
      }
    case x :: Nil => x :: result
    case Nil => Nil
  }
}

Answer 7

#include <stdio.h>
void bubbleSort(int *,int ,int ,int );
void swap(int *, int *);
void printArray(int *,int);

int main()
{
    int n,c;

    printf("Enter number of elements\n");
    scanf("%d", &n);

    int array[n];

    printf("Enter %d integers\n", n);

    for (c = 0; c < n; c++)
        scanf("%d", &array[c]);

    printf("Before Sorting:\n");
    printArray(array,n);

    bubbleSort(array,0,0,n);

    printf("After Soring:\n");
    printArray(array,n);

 }

 void bubbleSort(int *array,int i,int j,int n)
 {
     if(j==n-i-1)
     {
         i = i+1;
         j = 0;
     }
     if(i==n-1)
         return;

     if(array[j]>array[j+1])
         swap(&array[j],&array[j+1]);

     j++;
     bubbleSort(array,i,j,n);
 }

 void swap(int *p,int *q)
 {
     int t = *q  ;
     *q = *p;
     *p = t;
 }

 void printArray(int *array,int n)
 {
     int c=0;
     for (c = 0; c < n; c++)
        printf("%d ", array[c]);
    printf("\n");
 }

Answer 8

def bubble_sort(l):
    for i, num in enumerate(l):
        try:
            if l[i+1] < num:
                l[i] = l[i+1]
                l[i+1] = num
                bubble_sort(l)
        except IndexError:
            pass
    return l

Answer 9

How about this kind of solution:

package recursive.bubble;

public class RecursiveBubble {

    public static boolean sort(int []arr){
        if(!bubbleSorted(arr, 0)){
            return sort(arr);
        }
        return true;
    }
    public static boolean bubbleSorted(int []a,int index){    
        if(a.length<2){
            return true;
        }
        if(index==a.length-2){
            if(a[index+1]<a[index]){
                swap(a,index,index+1);
                return false;
            }
            return true;
        }
        boolean isSorted=false;
        if(a[index]<=a[index+1]){
            isSorted=true;
        }else{
            swap(a,index,index+1);
        }
        return isSorted && bubbleSorted(a, index+1);
    }
    private static void swap(int[] a, int index, int i) {
        int tmp=a[index];
        a[index]=a[i];
        a[i]=tmp;
    }
    public static void main(String[] args) {
        int []a={4,5,6,2,2,3,9,1,8};
        if(sort(a))
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

Answer 10

Bubble sort: recursive and efficient

public static void bubbleSort(int[] ele, int counter, int index) {
            int temp=-1;
            if (counter < ele.length) {
                if (index < ele.length - 1) {
                    if (ele[index] > ele[index+1]) {
                        ele[index] += ele[index+1];
                        ele[index+1] = ele[index] - ele[index+1];
                        ele[index] = ele[index] - ele[index+1];
                        temp = ele[index];
                    }
                    bubbleSort(ele, counter, index+1);
                    //temp = sortedIndex;
                    return;
                }
                if(counter == ele.length-1 && temp==-1){
                    return;
                }
                bubbleSort(ele, counter+1, 0);
            }

        }

Answer 11

Here is a recursive bubblesort in javascript:

function bubbleSortRecursive(array, index1, index2) {
    //define index1 and index2 if user doesn't pass them in
    index1 = typeof index1 == "undefined" ? 0 : index1;
    index2 = typeof index2 == "undefined" ? array.length : index2;

    if (index1 > index2) {
        return array;
    } else if (index1 == index2 - 1) {
        return bubbleSortRecursive(array, 0, index2 - 1);
    } else if (array[index1] > array[index1 + 1]) {
        //bubble the larger value towards the end of the array
        var temp = array[index1];
        array[index1] = array[index1 + 1];
        array[index1+1] = temp;
        return bubbleSortRecursive(array, index1 + 1, index2);
    } else {
        return bubbleSortRecursive(array, index1 + 1, index2);
    }
}

The first 2 lines inside the function allow the user to call bubbleSortRecursive(array) and the function will define the index1 and index2

Answer 12

Here's my answer. It's essentially the same as VladimFromUa's answer (a recursive variant of bubble sort) but instead of doing a fixed number of runs, additional runs are only performed if it's detected that the array was reordered on the previous run.

Another couple of differences are below:

1.The parameter indexing the starting point in the array has been dropped by offsetting the address of the array in recursive calls. 2.The check "if(first < last && last > 0)" in Vlad's or "if (--p_length == 1)" in my code is better performed before the recursive call that would result in the array length being 1, since it is one less call on the stack.

I added some code to read the input from the command line and print both the unsorted and sorted arrays, for convenience.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef enum { FALSE, TRUE } boolean_t;

void
swap_int(int *a, int *b) {

    int temp = *a;

    *a = *b;
    *b = temp;
}

boolean_t
sort_array(int p_array[], int p_length) {

    boolean_t result;

    if (p_array[0] > p_array[1]) {
        swap_int(p_array, p_array + 1);
        result = TRUE;
    } else {
        result = FALSE;
    }

    if (--p_length == 1) {
        return result;
    }

    result |= sort_array(p_array + 1, p_length);

    if (result) {
        sort_array(p_array, p_length);
    }

    return result;
}

void
print_array_int(int p_array[], int p_length) {

    int n;

    for (n = 0; n < p_length - 1; n++) {
        printf("%d, ", p_array[n]);
    }

    printf("%d\n", p_array[n]);
}

int
main(int argc, char **argv) {

    int *array;
    int array_length = argc - 1;
    int n;

    array = malloc(array_length * sizeof(*array));

    for (n = 0; n < array_length; n++) {
        sscanf(argv[n + 1], "%d", array + n);
    }

    printf("\nUnsorted array:\n");
    print_array_int(array, array_length);
    sort_array(array, array_length);
    printf("\nSorted array:\n");
    print_array_int(array, array_length);

return 0;
}

Answer 13

#include <stdio.h>
#include <stdlib.h>

void sort(int *arr, int first, int last){

    if(first < last && last > 0){
        if(arr[first] > arr[first+1]){
            int temp = arr[first];
            arr[first] = arr[first+1];
            arr[first+1] = temp;
        }
        sort(arr, first+1, last);
        sort(arr, first, last-1);
    }
    else
        return;
}
int main(void) {

    int data [] = { 3, 5 , 6, 2, 1, 10, 4};
    int len = sizeof(data)/sizeof(int);
    int i = 0;
    sort(data,0,len-1);
    for(i=0;i<len;i++)
        printf("%d ",data[i]);

    return EXIT_SUCCESS;
}

Answer 14

Because I found this question as one of the first examples, I would like to provide an other way to do the recursion, without additional arguments:

function bubblesort (input: some integer array):
  if input is empty:
    return input
  else:
    do one bubble sort run for input
    subarray = bubblesort(unsorted part of input)
    return subarray append sorted part of input

In this way, we will sort the whole array piecewise for each call.

Why does it work? Because every bubble sort run, we will put at least the largest element to the rightmost index.
We know that all elements until the last swap are in unknown state, all after the last swap are sorted.

Implementations in Java (array/list argument-modifying/not) could be found there: https://codereview.stackexchange.com/questions/24006/recursive-bubble-sort-in-java/24133#24133

Answer 15

public void sort(int[] arr, int first, int last){

    if(first < last && last > 0){
        if(arr[first] > arr[first+1]){
            int temp = arr[first];
            arr[first] = arr[first+1];
            arr[first+1] = temp;
        }
        sort(arr, first+1, last);
        sort(arr, first, last-1);
    }
    else
        return;
}

Late for 2 years, but maybe it will useful to someone

Answer 16

Recursion is a design technique based on inductive proofs. Considers one or more base (simple) case(s) for your problem, and one or more ways to move the problem closer to being a base-case problem. Then, at each step of the algorithm, you either recognize completion (and deal appropriately with a base case) make the problem slightly closer to being a base case.

Bubble sort is just an application of the observation that a sorted array has all adjacent pairs of elements in order. Defined recursively, it works like:

1. Base case: There's an array of size 1 (or less) to sort. It's sorted, of course.
2. Inductive case: Bubble the largest element to the top of the array. Now there's a one-element smaller array to sort, which do.

You can write that very idea in the programming language of your choice, and you get bubble sort. Oh, but you have to define what it means to "bubble the largest element". Well, that's another opportunity for recursive design. I think you get the idea, though.

Faster sorts are mostly based on observations about how you get closer to the goal in less work. Quick sort, for instance, relies on the notion that, if an array is sorted, then there is some element P, and all elements less than P are to P's left, and all elements more than P are to P's right. If you can establish that property on an array, and also pick P, then you can cut the problem roughly in half at each step instead of simply by one.

Answer 17

I am not sure whether Bubblesort is a good algorithm to practice recursion on. It would be quite ugly to convert it to recursion because it's a nested cycle. It would look something like this:

function pass(i,j,n,arr)
{
  if(arr[i]>arr(j))
    swap(arr[i],arr[j]);

  if(j==n)
  {
    j=0;
    i=i+1;
  }
  if(i==n+1)
    return arr;

  return pass(i,j+1,n,arr);
}

It's the same for loop, only longer to define, using a lot more memory.

You should instead try to implement QuickSort. It needs recursion, and it's a lot faster in most cases than BubbleSort. Most platforms implemented it already, so you don't have to write it yourself, but it's good to know how it works, and it helps understand recursion.

If you want you might also try to solve this problem using recursion:
You have a table NxM of numbers, and a starting coordinate (position). It's a ^travellers^ position. The traveller can travel to an adjacent cell (right, left, up or down) which has a smaller number than the one he's on. You must write a program that computes the longest path the traveller can pass under these constraints. Use random to generate the array, or generate it manually.