toy 16 quickSort

퀵 정렬 알고리즘 구현(콜백함수의 리턴값으로 정렬 기준을 정하는 것 까지도 포함.)

작성 코드

function quickSort(arr, transform = (item) => item) { 
  //왜 여기서 콜백함수를 이렇게 쓴 거냐: default parameters이기 때문, 콜백 없을 때는 그냥 그대로 리턴하는 것과 동일. 
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (transform(arr[i]) < transform(pivot)) left.push(arr[i]);
    else right.push(arr[i]);
  }

  const lSorted = quickSort(left, transform);
  const rSorted = quickSort(right, transform);
  return [...lSorted, pivot, ...rSorted];
}

아고라스테이츠 질문//

현재 어떤 스프린트를 진행 중이고, 어떤 문제에 부딪혔나요? 토이 16번 문제를 푸는 중, forEach 문을 사용하였을 때 테스트케이스 "최대 길이 100,000인 배열을 정렬해야 합니다" 가 통과되지 않았습니다.

**안 되는 부분을 해결하기 위해서 구체적으로 어떤 노력을 했나요?**레퍼런스 코드와 제가 작성한 코드를 비교해 보고, 어떤 점에서 차이가 나서 테스트 통과가 안되는지,에러로 의심되는 부분들을 하나씩 레퍼런스에 작성된 코드로 바꿔가며 테스트를 해봤습니다.

(1) 함수 표현식과 함수 선언식 : 함수의 선언 방식은 테스트 케이스에 영향을 미치지 않아서, 이 부분은 문제가 되지 않았습니다.(2) 마지막 리턴문: 이 부분도 테스트 케이스에 영향을 미치지 않아 (1)과 같은 결론을 내렸습니다.(3) forEach문과 for 문: 저는 아래와 같이 forEach 문을 사용하여 small 배열과 large 배열을 만들었는데, for문으로 바꾸어서 작성했더니 통과가 되었습니다.

`const quickSort = function (arr,callback = (item) => item) { if(arr.length < 2) return arr;

let pivot = arr[0];
let small = [];
let large = [];
arr.forEach(ele => { 
  if(callback(ele) > callback(pivot)){ 
    large.push(ele);
  }else if(callback(ele) < callback(pivot)){ 
    small.push(ele);
  }
})
return quickSort(small,callback).concat(pivot,quickSort(large,callback));

};`

통과가 안된 테스트케이스에는 "최대 길이 100,000인 배열을 정렬해야 합니다" 라고 적혀 있었는데,대량의 데이터를 다룰 때도 시간 소요가 많이 되지 않아야 하는 것인가? 하는 생각이 들었고,이에 forEach 문과 for 문이 성능 면에서 어떤 차이가 난다고 결론을 내렸습니다.for문과 forEach의 차이에 대해 검색해봤는데, for문과 forEach를 가지고 연산 속도를 비교한 내용에 대한 글을 봤습니다.그 글에서는 매번 배열의 모든 요소(정수)들을 제곱하는 것을 가지고 비교했는데, 이 표를 보고 for문이 forEach문보다는 빠르구나, 라는 결론을 내렸습니다.(세로축은 배열의 길이이고 그 옆의 숫자들은 소요시간(ms)입니다.)

**어떠한 부분에서 이해가 안 되었나요?**테스트가 통과되지 않는 이유가 forEach 가 for문보다 시간적으로 연산이 느려서라고 이해하는 게 맞을까요?

에러 코드를 붙여넣기 해 주세요.

Test Result
AssertionError: expected false to be true
    at Assertion.fail (/node_modules/should/cjs/should.js:275:17)
    at Assertion.value (/node_modules/should/cjs/should.js:356:19)
    at Context.<anonymous> (/submission/index.test.js:68:32)
    at processImmediate (internal/timers.js:464:21) ...

Test Code
function () {
      const result = quickSort(arr);
      const hashed = sha256(result);
      (hashed === hash).should.equal(true);
    }

//sha256을 쓴 이유는 일일이 하나하나 배열을 직접 비교하기 힘드니 좀 짧은 256비트 길이를 갖는 문자열로 바꿔주고 비교하는 게 훨 낮기 때문이다. 각 값마다 고유한 값을 리턴해주는 거 같음. 그래서 쓰는거같다.

에러가 출력된 곳에서, 이유라고 생각하는 부분을 열 줄 이내로 붙여넣기 해 주세요. (잘 모르겠으면 에러라고 생각하는 곳을 넣어주세요)

`arr.forEach(ele => { 
  if(callback(ele) > callback(pivot)){ 
    large.push(ele);
  }else if(callback(ele) < callback(pivot)){ 
    small.push(ele);
  }
})`

검색했던 링크가 있다면 첨부해 주세요.https://www.geeksforgeeks.org/difference-between-foreach-and-for-loop-in-javascript/https://betterprogramming.pub/which-is-the-fastest-while-for-foreach-for-of-9022902be15e