Understanding recursion (applying it when sorting bubbles)

Question

I am trying to figure out how to use recursion in programs. I understand how recursion works in classic examples, such as factorial, but I'm not sure how to apply it myself ...

I start by converting an iterative bubble sort code to a recursive code ... I searched the net for the same thing .... but can't find a convincing solution / explanation.

An example of iterative code for sorting bubbles:

arr [n] → an array with elements (1..n) 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]);

It would be helpful if someone could give a hint on how to do this ...

Answer 1

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 be useful to someone

Answer 2

I'm not sure if Bubblesort is a good algorithm for recursion practice. It would be pretty ugly to convert it to recursion because it is a nested loop. It will 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); } 

The same goes for a loop, only longer to determine using a lot more memory.

Instead, you should try to implement QuickSort. This requires recursion, and in most cases it is much faster than BubbleSort. Most platforms are already implemented, so you don’t need to write this yourself, but it’s good to know how it works and helps to understand recursion.

If you want, you can also try to solve this problem using recursion:
You have a table of NxM numbers and a starting coordinate (position). This is the position of the traveler. A traveler can move to a neighboring cell (right, left, up or down), which has a smaller number than the one on which it is located. You must write a program that calculates the longest path that a traveler can go under these restrictions. Use random to generate an array or generate it manually.

Answer 3

Recursion is a design method based on inductive evidence. Considers one or more basic (simple) cases (s) for your problem and one or more ways to move the problem closer to the problem with the base region. Then, at each step of the algorithm, you either recognize the completion (and deal with the base case) so that the problem is a little closer to the base case.

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

• Base case: there is an array of size 1 (or less) for sorting. Of course, this is sorted.
• Inductive case: Bubble is the largest element at the top of the array. Now a singleton smaller array is used for sorting.

You can write this idea in your chosen programming language, and you get a bubble view. Oh, but you have to define what it means to bubble the biggest element. Well, this is another opportunity for recursive design. I think you understand this idea.

Faster sorting is mainly based on observations of how you approach the goal in lesser work. Quick sorting, for example, is based on the concept that if an array is sorted, that is, some element P, and all elements smaller than P equal P to the left, and all elements larger than P equal P to the right. If you can set this property in an array, and also select P, then you can solve the problem in half at each step, and not just one.

Answer 4

Here is the recursive bubblecream 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 two lines inside the function allow the user to call bubbleSortRecursive(array) , and the function will determine index1 and index2

Answer 5

Since I found this question as one of the first examples, I would like to provide another way to do 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 

Thus, we will sort the entire array piecewise for each call.

Why does it work? Since each sorting of bubbles is done, we will put at least the largest element in the rightmost index.
We know that all the elements until the last swap are in an unknown state, all after the last swap are sorted.

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

Answer 6

 #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 7

Here is my answer. This is essentially the same as the answer of VladimirFromUa (a recursive option for sorting bubbles), but instead of making a fixed number of runs, additional runs are only performed if he finds that the array was reordered in the previous run.

Another couple of differences below:

1. The parameter indexing the starting point in the array was reset by shifting the address of the array in recursive calls. 2. Checking "if (first <last && last> 0)" in Vlad or "if (--p_length == 1)" in my code is better done before a recursive call, which will lead to an array of length equal to 1, since this is one calling a call on the stack.

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

 #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 8

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

 static void RecursiveBubbleSort(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]); RecursiveBubbleSort(Arr, l - 1); } 

Answer 9

How about such a 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

 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 11

 #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==ni-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 12

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

 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 13

Here's another version of javascript recursion with some es6 / 7 syntax, like 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 14

 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); } }