간만의 TIL 업데이트다. ( TIL이라 쓰고 WIL이 아닐까? )

sort 함수의 이해

원래 Javascript는 정렬을 위해 sort 함수를 제공한다.

그런데 무턱대고 쓰다가는 큰 오류와 resource를 낭비할 수 있다.

가끔, sort함수를 사용하면서 실수할 수 있는 것이 있는데, 바로 sort([compareFunction]) 에 compareFunction을 지정해주지 않으면 문자열로 취급하여, 유니코드( 참고 링크 - 위키 백과 ) 값 순서대로 정렬한다.

그렇기 때문에 compareFunction에 수식을 활용하여 정렬한다.

const arr = [12, 3, 34, 5];

console.log( arr.sort() );

// 예상값 : 3, 5, 12, 34
// 실제 출력 : 12, 3, 34, 5

• 알고리즘 동작 원리
  

정렬 알고리즘은 생각보다 간단하다. 가령 다음과 같이 적용한다고 했을 때, 내부 알고리즘의 동작은 다음과 같다.

const arr = [12, 3, 34, 5];
    
    const arr2 = arr.sort( ( a, b ) => a - b );
    
    /* sort 알고리즘
      a - b 값이 0보다 크면 return 1을 반환하고 a와 b의 자리를 바꿉니다.
      값이 0이면 return 0을 반환하고 sort를 종료합니다.
    */
    
    //*** 1번 순회 시작 ***
    //      a 위치   b 위치                    : a = 0번 index, b = 1번 index  
    //배열 [  12,      3,      34,       5 ]
    //12 - 3 > 0 => return 1 => swap( 12, 3 ) 
    //(여기서 swap은 단순히 자리를 바꿈을 나타냅니다.)
    //      a 위치         b 위치              : a = 0번 index, b = 2번 index
    //배열 [   3,    12,     34,          5 ]
    //3 - 34 < 0 => return -1 => 자리를 바꾸지 않습니다.
    //      a 위치                      b 위치 : a = 0번 index, b = 3번 index
    //배열 [   3,    12,     34,          5 ]
    //3 - 5 < 0 => return -1 => 자리를 바꾸지 않습니다.
    //*** 1번 순회 끝 ***
    
    //*** 2번 순회 시작 ***
    //             a 위치  b 위치              : a = 1번 index, b = 2번 index
    //배열 [   3,    12,     34,          5 ]
    // 12 - 34 < 0 => return -1 => 자리를 바꾸지 않습니다.
    //             a 위치               b 위치 : a = 1번 index, b = 3번 index
    //배열 [   3,    12,     34,          5 ]
    // 12 - 5 > 0 => return 1 => swap( 12, 5 )
    //             a 위치               b 위치 : a = 1번 index, b = 3번 index
    //배열 [   3,    5,     34,          12 ]
    //***2번 순회 끝***
     
    //**3번 순회 시작
    //                    a 위치         b 위치 : a = 2번 index, b = 3번 index
    //배열 [   3,    5,     34,          12 ]
    // 34 - 12 > 0 => return 1 => swap( 34, 12 )
    //배열 [   3,    5,     12,          34 ]
    //**3번 순회 끝
    
    //**4번 순회 시작
    //                                 a, b 위치 : a = 3번 index, b = 3번 index
    //배열 [   3,    5,     12,          34 ]
    // a - b = 0 => return 0 => sort를 종료합니다.
    //**4번 순회 종료
    
    console.log( arr2 );

이렇듯 매우 유용하게 쓰이는 함수이지만, 예시에서 살펴보았듯이 시간 복잡도도 높은 친구다.

• sort 함수의 시간 복잡도
  

Javascript 의 sort 시간 복잡도는 $O( nlog( n))$이다. - 출처 : 햣 블로그

시간 복잡도 그래프 - 출처 : bigocheatsheet

마치며

sort는 매우 유용하지만, 그만큼 시간 복잡도 또한 크다. 개선 알고리즘을 쓰던가, 쓸때 신중을 기해야 할 것