TIL 1007 _.sortBy(arr.sort()) _.flatten(재귀함수) 3일걸린 문제

계속 이해가 안가서 3일 밤낮으로 고민했던 문제.
항상 문제를 제대로 이해했다고 생각하고 푸는순간 맹점이 생긴다.
잘했다고 생각했는데 풀리지 않는것은 맹점을 놓치고 있어서다.
이것을 꼭 반드시 항상 주의하자.

_.sortBy ( arr.sort( ) )

계속 sort( function(a, b){...} ) 으로 풀려고 시도했는데, 인자로 전달해주는 function 에서 어떤 순서로 a, b가 들어가는지어떤 알고리즘으로 정렬되는지 이해하지 못해서 계속 골머리를 앓았다. 검색해보다 누군가가 댓글로 설명해 둔것이 있어 참고하고 완전한 이해는 힘들다고 판단. 흐름만 이해하기로 했다.

아래는 내가 이 문제를 며칠동안 고민하게 만든 이유

1. 인자로 주어지는 arr이 const로 선언되어 값이 변경될 수 없다.
arr.sort()를 해봐야 정렬(값의 수정)이 이루어지지 않으므로 당연히 정렬된 값을 출력할 수 없다.
(테스트케이스를 잘 읽자..)

const list는 상수라 안바뀐다!! 인자 형태에 유의하자

2. sort(function(a,b){ ... } ); 의 정렬 알고리즘에 대한 이해가 부족하다.

arr.sort(function(a, b) {

  if(a < b){
    return -1; //순서바꿈
  }else{
    return 1;  
  } 

}

위 코드는 오름차순 정렬을 할 때이다.
사실 return 0과 return 1의 차이를 잘 모르겠다.
return 1은 a가 앞에 b가 뒤에이고,
return 0은 a, b 위치를 바꾸지 않는다. 라는데 그게 그거 아닌가?

정렬 알고리즘을 모르겠어서 설명을 생활코딩 댓글에서 가져왔다
출처 : https://opentutorials.org/course/50/109 ('지나가다가'님의 댓글)

우선 [20, 10, 9,8,7,6,5,4,3,2,1]의 배열에서 a-b라는 연산을 모두 한 다음
그 결과값으로 정렬하는 것이 결코 아닙니다.

(a,b) 형식으로 지정한 두 인자를 차례로 비교합니다.
우선 배열 numbers[0]과 numbers[1]
즉, 20과 10을 비교해 볼까요?
20-10 = 10 결과값이 10 즉, 양수입니다.
sort함수에 sortNumber(a,b)의 return 값으로 양수 10을 전달합니다.
그럼 sort함수가 양수값을 전달받고 배열의 순서를 바꾸어 버립니다.
(정확하게 말하면 두 배열 안에 든 값을 교체)

그럼 배열이 [10, 20, 9,8,7,6,5,4,3,2,1] 이렇게 바뀝니다.
그 다음 numbers[0]과 numbers[2] 즉 10과 9를 비교합니다.
10 - 9 = 1 >0, 양수입니다.
결과값이 양수이므로 또 10과 9의 순서를 바꿉니다.

이런 식으로 계속 두 인자를 비교해서 결과값이 양수가 나오면 순서를 바꾸고,
음수가 나오면 순서를 그대로 유지하는 겁니다.
배열이 바뀌어가는 순서를 보면 이해하기 쉽습니다.

[(20), (10), 9,8,7,6,5,4,3,2,1]
20-10 = 10,
즉 양수이므로 순서바뀜!
()는 비교되는 인자값.

[(10), 20, (9),8,7,6,5,4,3,2,1]
10 - 9 = 1
또 양수, 순서 바뀜.

[(9), 20, 10, (8),7,6,5,4,3,2,1]
반복...
[(8), 20, 10, 9,(7)...]
...
[(2). 20, 10...3, (1)]
[(1), 20, 10...]

그럼 배열 내에서 가장 작은 값 1이 찾아지겠죠.
[1, 20, 10, 9,8,7,6,5,4,3,2]
1의 순서는 바뀌지 않습니다.
1-2 = -1 즉 결과값이 음수이기 때문이죠.
그 다음은 두번째 배열 차례입니다.
20 - 10 = 10 > 0 이므로 순서를 또 바꿉니다.
[1, (20), (10), 9,8,7,6,5,4,3,2]
[1, (10), 20, (9), 8...]
[1, (9), 20, 10, (8)...]

이런 식으로 반복하다 보면 두번째로 작은 값 2도 찾게 됩니다.

....
[1, 2, 20, 10, 9,8,7,6,5,4,3]

그럼 다음은 세번째...
이렇게 지루하게 반복하면 결국 정렬이 됩니다.
물론 실제 자바스크립트에서는 비교하는 순서가 다릅니다.
다른 알고리즘을 쓰기 때문이죠.

이렇게 차례차례 비교해 나가면 인간이 이해하기는 쉽지만 연산량이 기하급수적으로 늘어나기 때문에
다른 정렬 알고리즘을 쓰는 것이죠.
실제로는 [20, 10, 9,8,7,6,5,4,3,2,1] 배열의 양쪽 끝부터 비교하고 (20, 1 둘을 비교)
그 다음 배열의 가운데 값을 차례로 비교해 나갑니다.
(1,6) 디버깅해 보시면 쉽게 아실 수 있을 겁니다

결론

댓글을 다 읽어보고 직접 a, b값을 콘솔창에 출력도 해보고 손으로 써가면서 어떻게 정렬 되는지 알고 싶었지만
만족스러운 답은 얻지 못했다. sort 메서드 내부를 뜯어서 보지 않는 한 완벽히 정확한 이해를 하기엔 한계가 있었다.

그래서 일단은 맥락상 a는 배열에서 비교하는 두 요소 중 뒤쪽 요소를 말하고
b는 앞쪽 요소를 말한다고 생각하기로 했다.

[ 3, 2 ] 를 비교한다고 하면
b가 3 이고 a가 2이다.

그러므로 if( a < b )일때 return -1로 순서를 바꾸게 된다면
( if( b > a ) 로 쓰면 보기 편하다 )
오름차순으로 정렬이 되어서 결과는
[ 2, 3 ] 이 된다.

내림차순으로 정렬을 하고싶을 땐
부등호 방향만 바꾸고 return -1의 위치는 바꾸지 않으면 된다.

  cloneArr.sort(function(a, b){
      // return a - b //문자열 비교때문에 이렇게는 사용하지 못한다
      //숫자요소만 정렬할 때는 이렇게 사용 가능하다.(오름차순)
      // return b - a (내림차순)

    if(오름차순 정렬 조건){
      if( a < b ){ //오름차순
        return -1; //a, b 순서를 바꿈
      }
    }

    if(내림차순 정렬 조건){
      if( a > b ){ //부등호 방향을 반대로. (내림차순)
        return -1; //a, b 순서를 바꿈
      }
    }

  });

정확한 코드는 아니지만 (return 0, return 1 부분이 없으므로)
위 설명을 예로 들기 위한 코드이다.

3. (팁?) 인자를 전달받을 때 undefined인지 검사와 동시에 초기화 시키는 방법을 몰랐다.

if( order === undefined) 이런식으로 써왔는데
위 방법이 훨씬 간결하고 좋은것 같다.

_.flatten ( 재귀함수 )

1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우 사용
2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우 사용

중첩배열을 순환할 때 주석처럼 작성하면 제대로 작동하지 않았다

오답노트

ele가 배열일 때,
재귀함수 flat에 인자로 ele의 "특정 인덱스"를 전달하는 것은
"해당 인덱스"의 값이 배열이 아닐수 있기 때문에

배열만 전달받는 _.each 메서드에서 사용이 불가능하다.

그래서, "해당 인덱스"의 값이 배열이 아닌 경우에 재귀함수가 작동할 수가 없다.
그러므로 배열 자체인 ele를 그대로 인자로 전달해주면 해결.