bubble sort in javascript - recursive version not working

Question

I tried to build a Bubble Sort algorithm to sort an array. It works in sorting the array, but for its recursive implementation, it never stops... I understand I should put some break clause to stop the execution of the for loop, but I'm not sure where.

Could please someone provide some useful guidance on these types of problems with recursive functions?

Thank you

input = [1, 7, 5, 6, 8, 9, 9, 100, 24, 35, 10]

function bubbleSort(input) {
  for (let i = 0; i < input.length; i++) {
    if (input[i] > input[i + 1]) {
      let newvar = input[i];
      input[i] = input[i + 1];
      input[i + 1] = newvar;
      bubbleSort(input);
    }
  }
};
console.log(bubbleSort(input));

You've at least got the problem of going off the end of the array. The loop limit should be `input.length - 1` so that the `i + 1` offsets in the loop body don't go beyond the end. — Pointy, Aug 24 '19 at 12:19
Also bubble sort is a strange choice for a recursive adaptation. The recursion point you've chosen is not the best idea I think. I'd keep track of whether the `for` loop finds one or more swaps to make. If it makes at least one swap, then do the recursive call *outside* the `for` loop. If not, then the array is sorted and the function can exit. — Pointy, Aug 24 '19 at 12:26
This isn't bubblesort. Instead of recursive step you should perhaps have another for loop. What you do here is do the whole sort over and over for each element switched back. — Sylwester, Aug 24 '19 at 12:35

score 3 · Answer 1 · answered Aug 24 '19 at 12:43

You have to use a counter variable to count the current iteration and return the array when the counter is equal to the length of the array

input = [1, 7, 5, 6, 8, 9, 9, 100, 24, 35, 10]

function bubbleSort(input,curr){
  if(curr==input.length){
  return input;
  }
  for (let i = 0; i < input.length; i++) {
    if (input[i] > input[i + 1]) {
      let newvar = input[i];
      input[i] = input[i + 1];
      input[i + 1] = newvar;
    }
  }
  return bubbleSort(input,curr+1);

 }
console.log(bubbleSort(input,0));

score 2 · Answer 2 · answered Aug 24 '19 at 15:25

Here's a version using only recursion - without for loops -

const bubbleSort = (a = []) =>
  a.length < 2
    ? a
    : cont (singlePass (a))
        ( r =>
            [ ...bubbleSort (r .slice (0, -1))
            , ...r .slice (-1)
            ]
        )

const cont = x =>
  k => k (x)
  
const None =
  Symbol ()

const singlePass = ([ x = None, y = None, ...more ]) =>
  y === None
    ? [ x ]
: x === None
    ? []
: x > y
    ? [ y, ...singlePass ([ x, ...more ]) ]
    : [ x, ...singlePass ([ y, ...more ]) ]

const input =
  [ 1, 7, 5, 6, 8, 9, 9, 100, 24, 35, 10 ]

console .log (bubbleSort(input))
// [ 1, 5, 6, 7, 8, 9, 9, 10, 24, 35, 100 ]

If you package this as a module, only bubbleSort should be exported -

module.exports = { bubbleSort }

This is very good indeed! Is there a name for this "pattern": `const cont = x => k => k (x)`. I understand what this is doing and why it's done this way. I'm just curious to know if that is a common thing to do in FP and whether it has its own denomination. — customcommander, Aug 25 '19 at 07:24
@customcommander that is the continuation monad ^_^ you can see it used [here](https://stackoverflow.com/a/46918344) and in many of [my posts](https://stackoverflow.com/search?q=continuation+monad+user%3A633183). — Mulan, Aug 25 '19 at 13:12

score 0 · Answer 3 · answered Aug 24 '19 at 12:32

Here's a fixed version of your code:

input = [1,7,5,6,8,9,9,100,24,35,10]

function bubbleSort(input, n) {
  if(n === 1) {return input;} // return when all the iterations are done
  for (let i = 0; i < input.length; i++) { 
    if(input[i] > input [i+1]){
    let newvar = input[i];
    input[i] = input[i+1];    
    input[i+1] = newvar;
    
    } 
  }
 return bubbleSort(input, n - 1); // Keep it outside for loop and return it to make it recursively returned
};
console.log(bubbleSort(input, input.length - 1));

score 0 · Answer 4 · answered Aug 24 '19 at 12:37

0

input = [1, 7, 5, 6, 8, 9, 9, 100, 24, 35, 10];


function bubbleSort(input) {
  for (let i = 0; i < input.length; i++) {
    if (input[i] > input[i + 1]) {
      let newvar = input[i];
      input[i] = input[i + 1];
      input[i + 1] = newvar;
      bubbleSort(input);
    }
    //return it reaches last loop of statement
    ***if(i == input.length -1){
      return input;
    }***
  }
};
console.log(bubbleSort(input));

answered Aug 24 '19 at 12:37

Shankar_programmer

298
5
14

Welcome to Stack Overflow! While this code snippet may solve the problem, it doesn't explain why or how it answers the question. Please [include an explanation for your code](//meta.stackexchange.com/q/114762/269535), as that really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. – Samuel Philipp Aug 24 '19 at 14:08
Thanks. Here after i'll write code with explaination. – Shankar_programmer Aug 26 '19 at 05:51

score 0 · Answer 5 · answered Jan 30 '21 at 09:08

Here is one solution that has no loops and no variable to count how many iterations you have done:

const bubbleSort = (a, length) => {
    if (length === 0) {
        return a;
    }
    if (length === undefined) {
        length = a.length;
    }
    return bubbleSort(a.sort((valueA, valueB) => valueA - valueB), length - 1);
};

To use it you just pass the array that needs sorting:

const testArr = [50, 5, 0, 10, -1];
console.log(bubbleSort(testArr)); //  [ -1, 0, 5, 10, 50 ]

I don't know if it can be shorter than this and still be readable.

bubble sort in javascript - recursive version not working

5 Answers5