JavaScript 퀵 소트에서 무한 재귀?

Question

내가 작성한 코드는 quicksort입니다. 이 함수는 기본 케이스에 도달 할 수 없기 때문에 작동하지 않습니다. 콘솔에 피벗 r 및 l을 기록하면 sort 함수가 몇 번 호출 되더라도 상관 없습니다. 그래서 인수가 l, r이 실제로 데이터로 함수로 전달되지 않는지 궁금합니다. 왜 그런 일이 일어 났습니까?

function sort(data){ 
    if(data.length < 2){ 
     return data; 
    } 
    else{ 
     var l = []; 
     var r = []; 
     var pivot = parseInt(data.length/2); 
     for(i=0; i<data.length; i++){ 
      if(data[i] > data[pivot]){ 
       r.push(data[i]); 
      } 
      else{ 
       l.push(data[i]); 
      } 
     } 
     return sort(l).concat(sort(r)); 
    } 
} 

Answer 1

여기서 문제는 파티션 분할 단계가 입력 배열을 축소하지 않는다고 생각하는 것입니다. 예를 들어, [1, 2]를 정렬하려고하면 어떤 일이 일어나는지 추적 해 봅시다. 이 경우 피벗 요소는 요소 2가됩니다. 1> 2가 false이므로 1이 목록 l에 추가됩니다. 2> 2가 거짓이므로 2가 목록 l에 추가됩니다. 따라서 목록 l에 대한 재귀 호출은 원래 호출과 정확히 동일한 인수를 가지므로 무한 재귀가 발생합니다.

이 문제를 해결하려면 입력을 작은 값 하나, 같은 값 하나 또는 큰 값 중 하나 세 개의 목록으로 나누십시오. 자신의 목록에

function sort(data){ 
    if (data.length < 2){ 
    return data; 
    } else { 
    var l = []; 
    var r = []; 
    var e = []; 
    var i = 0; 
    var pivot = (data.length/2) | 0; 

    for(i = 0; i < data.length; i++) { 
     if (data[i] > data[pivot]) { 
     r.push(data[i]); 
     } else if (data[i] < data[pivot]) { 
     l.push(data[i]); 
     } else { 
     e.push(data[i]); 
     } 
    } 
    return sort(l).concat(e, sort(r)); 
    } 
} 

이 새로운 버전은 명시 적으로 그룹 동등한 요소를, 그래서 그들은 반복적으로 재귀 호출 중 하나에 의해 정렬되지 않습니다 :이 코드는 여기에 표시됩니다. 또한 중복 요소를 정상적으로 처리합니다.

희망이 도움이됩니다.

Answer 2

JavaScript는 객체를 참조로 전달합니다 (배열도 객체 임). 값으로 전달하려면 here과 같이 스플 라이스 함수를 사용해야합니다.

이렇게하면 많은 데이터 복사본이 만들어집니다. 아마도 네이티브 sort() 함수를 사용하고 싶을 것이다.

Answer 3

배열의 가장 큰 값을 피벗 요소로 선택하면 data의 모든 값은 l의 배열로 끝나고 r의 배열로 끝납니다. 따라서 재귀는 결코 멈추지 않을 것입니다 (그리고 l, r 그리고 pivot을 같은 값으로 유지하십시오). 뇌 기관지가 아니라면 data.sort()을 사용하면 더 효과적입니다. ;)