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

Answer 1

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

Answer 2

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 }

Answer 3

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

Answer 4

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

Answer 5

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.