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

3

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.

answered May 19, 2018 at 10:31

engelant

14310 bronze badges

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

Comments

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

1

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

answered May 19, 2018 at 10:28

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

Comments

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

0

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".

edited May 19, 2018 at 10:34

answered May 19, 2018 at 10:28

Skorek

3322 silver badges13 bronze badges

Collectives™ on Stack Overflow

javascript - Issue in the loop in algorithm exercise

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related