javascript - Issue in the loop in algorithm exercise

Question

I'm studing an algorithm problem and I did understand all the things except the lines that I marked up with comment into the code. Note: It is not to solve the code. The code is working good. It is only to explain me about what is the marked lines' purposes.

let arr= [40, 50, 80, 20, 21, 35] function qSort(arr) { if(arr.length == 0){ // <-- These lines. I did NOT understand its purpose return []; } var left = [] var right = [] var pivot = arr[0] for(var i= 1; i<arr.length; i++) { if(arr[i] < pivot) { left.push(arr[i]) } else { right.push(arr[i]) } } return qSort(left).concat(pivot, qSort(right)) } console.log(qSort(arr))

This code is working good, but When I comment these lines into the code, the script doesn't work and it cause an error message referencing a loop issue: Uncaught RangeError: Maximum call stack size exceeded

Does anybody explain it to me please? I would like to know what is this lines' purpose. Thanks

If array is empty than nothing have to be done and an empty array is returned. — Brain Foo Long
– Brain Foo Long, Commented May 19, 2018 at 10:29

engelant · Accepted Answer · 2018-05-19 10:31:41Z

If the given array has a length of 0 (is empty), just return an empty array, because there is no sorting to be done. Actually the line could be:

if(arr.length <= 1){ return arr; }

since for 0 and 1 elements the's no sorting to be done.

This is related to the function being recursive (it calls itself) and therefor it needs a case, at wich it stops calling itself and return a value. That's called a recursion anchor.

Jonas Wilms · Accepted Answer · 2018-05-19 10:28:30Z

This is called the base case of recursion, which ends the recursion. If you leave it away, qSort will call qSort will call qSort will call...

Skorek · Accepted Answer · 2018-05-19 10:34:41Z

This line was written for optimization.

If there is no data in array you have nothing to sort. Plus when you sort elements you are passing smaller and smaller chunks of base array to qSort function, so you have to finish qSort execution at one point.

So basically it tells the code "There is nothing to sort".

Collectives™ on Stack Overflow

javascript - Issue in the loop in algorithm exercise

3 Answers 3

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Related