Turn a binary tree array into a one-dimensional array JavaScript

Question

I'm attempting to program bubble sort recursively. This is my code so far:

function recursive_bubble_sort(array) {
    if (array.length === 1) {
        return array;
    }

    for (var i = 0; i < array.length - 1; i++) {
        if (array[i] > array[i + 1]) {
            var temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }

    return [recursive_bubble_sort(array.splice(0, array.length - 1)), array[array.length -1]];
}

Technically it sorts the array but the return is not a one-dimensional array, instead it's in a reverse binary tree structure.

If the given array is [ 8, 2, 5, 1 ],
the output would be [ [ [ [ 1 ], 2 ], 5 ], 8 ].
How can I change the code so the output is like this: [ 1, 2, 5, 8 ]?

Scott Sauyet · Accepted Answer · 2020-06-10 14:30:14Z

2

Here's a slightly different version, using destructuring instead of a temporary variable for the swap and the spread operator to build the output:

const recursive_bubble_sort = (arr) => {
  if (arr.length < 2) {return arr}

  for (let i = 0; i < arr.length - 1; i ++) {
    if (arr[i] > arr[i + 1]) {
      [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]
    }
  }

  return [... recursive_bubble_sort (arr.slice(0, -1)), ... arr.slice(-1)]
}

console .log (recursive_bubble_sort ([8, 2, 5, 1]))

That last line could also be

  return [... recursive_bubble_sort (arr.slice(0, -1)), arr[arr.length - 1]]

. It's simply an aesthetic call.

answered Jun 10, 2020 at 14:30

Scott Sauyet

50.9k5 gold badges57 silver badges111 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

VLAZ · Accepted Answer · 2020-06-10 13:43:44Z

1

The problem is the return statement

return [recursive_bubble_sort(array.splice(0, array.length - 1)), array[array.length -1]];

However, since recursive_bubble_sort either returns a single element recursive_bubble_sort or an array (the other return), you need to handle both.

One easy way is to just use Array#concat - if you give it a single element, it adds it to a the array, if you give it an array, it adds all elements, instead. This ensures the result is always flat:

You can instead

function recursive_bubble_sort(array) {
    if (array.length === 1) {
        return array[0];
    }

    for (var i = 0; i < array.length - 1; i++) {
        if (array[i] > array[i + 1]) {
            var temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }

    return [].concat(recursive_bubble_sort(array.splice(0, array.length - 1)), array[array.length -1]);
}

console.log(recursive_bubble_sort([ 8, 2, 5, 1 ]))

answered Jun 10, 2020 at 13:43

VLAZ

29.6k9 gold badges65 silver badges88 bronze badges

6 Comments

jablazr Over a year ago

Thank you, concat() is what I was looking for, I tried to use push() but it didn't help.

trincot Over a year ago

Not really needed to use splice. slice will do the job without side effects.

Scott Sauyet Over a year ago

You could also do return [...recursive_bubble_sort(array.slice(0, -1)), ...array.slice(-1)]; I find this cleaner than concat.

VLAZ Over a year ago

@ScottSauyet doesn't work because the first exit condition returns a simple item, and this would attempt to spread it. To succeed, the basic case should always wrap the value in an array but for me that's unnecessary.

Scott Sauyet Over a year ago

Ah, I just copied the return from my own version, not noticing this change. But that points to another problem here, which is that sorting a one-element array returns a scalar value, not an array. I'll add a separate answer.

|

Collectives™ on Stack Overflow

Turn a binary tree array into a one-dimensional array JavaScript

2 Answers 2

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related