[JS - 개념] Sort() <배열 고차함수>

 

 

sort를 공부하기전에 - 

 

배열 고차 함수

 

고차 함수는 함수를 인수로 전달받거나 함수를 반환하는 함수를 말한다.

자바스크립트의 함수는 일급 객체이므로 함수를 값처럼 인수로 전달할 수 있으며 반환할 수도 있다.

고차 함수는 외부 상태의 변경이나 가변데이터를 피하고 불변성을 지향하는 함수형 프로그래밍에 기반을 두고 있다. 

 

함수형 프로그래밍은 순수 함수와 보조 함수의 조합을 통해 로직 내에 존재하는 조건문과 반복문을 제거하여 복잡성을 해결하고 변수의 사용을 억제하여 상태 변경을 피하려는 프로그래밍 패러다임이다.

조건문이나 반복문은 로직의 흐름을 이해하기 어렵게 하여 가독성을 해치고, 변수는 누군가에 의해 언제든지 변경될 수 있어 오류 발생의 근본적 원인이 될 수 있기 때문이다.

함수형 프로그래밍은 결국 순수 함수를 통해 부수 효과를 최대한 억제하여 오류를 피하고 프로그램의 안전성을 높이려는 노력의 일환이라고 할 수 있다.

 

자바스크립트는 고차 함수를 다수 지원한다. 특히 배열은 매우 유용한 고차 함수를 제공한다. 

배열 고차 함수는 활용도가 매우 높으므로 샤용법을 잘 이해해야한다.

 

 

Array.prototype.sort 

 

sort 메서드는 배열의 요소를 정렬한다.

원본 배열을 직접 변경하며 정렬된 배열을 반환한다.

 arr.sort([compareFunction])

 

sort의 매개변수는 cpmapreFunction이라는 것이 있다. 

이는 정렬의 순서를 정의하는 함수이다.  

내가 직접 순서를 정해줘도 된다는 소리이다.   

만약 아무것도 입력안하고 실행시 배열은 각 요소의 문자열 변환에 따라 각 문자의 유니 코드 코드 포인트 값에 따라 정렬된다. 

 

 

먼저 sort 매개변수에 아무것도 입력을 하지 않고 그냥 사용했을 때이다. 

arr1 = [2, 3, 4, 0, 1];
arr2 = ['d', 'f', 'g', 'u', 'a', 'c', 'b'];
arr3 = ['나', '다', '가', '라'];
arr4 = ['3', '1', '9', '2'];
arr5 = ['가', 'a', 'A', '2', 1, '나'];

arr1.sort();
arr2.sort();
arr3.sort();
arr4.sort();
arr5.sort();

console.log(arr1); // [ 0, 1, 2, 3, 4 ]
console.log(arr2); // ['a', 'b', 'c', 'd', 'f', 'g', 'u']
console.log(arr3); // [ '가', '나', '다', '라' ]
console.log(arr4); // [ '1', '2', '3', '9' ]
console.log(arr5); // [ 1, '2', 'A', 'a', '가', '나' ]

이 예제는 sort함수에 매개변수를 넣지 않고 실행시켰기에 유니 코드 코드 포인트 순서로 문자열을 비교하여 정렬시킨것이다. 

또한 만약 배열안에 문자열이 아닌게 있다면 문자열로 변환하고 유니 코드 코드 포인트 순서에 따라 정렬을 진행한뒤 다시 원래대로 타입으로 되돌린다.   예를 들어서 숫자가 있다면 숫자를 문자열로 변환시킨뒤에 유니 코드 코드 포인트 순서에 따라 정렬하고 다시 숫자로 되돌린다. 

 

 

이 예제를 통해 우리는 세 가지를 알 수 있다. 

1. 그냥 sort()를 사용하면 오름차순으로 정렬이 되구나

2. 문자열이 아니면 문자열로 변환해서 정렬하고 다시 원래대로 되돌리구나

3. 유니 코드 코드 포인트 순서에 따라 숫자, 영어, 한글 순으로 정렬이 되는 구나 

 

 

그런데 여기서 의문점이 생긴다. 

그렇다면 내림차순으로 정렬하려면 어떻게해야할까?  

그전에 숫자를 정렬할 때 주의해야할 점을 알아보자. 

 

arr = [1, 2, 3, 10, 20, 30, 100, 200, 300, 99];

arr.sort();

console.log(arr); // [1, 10, 100, 2, 20, 200, 3, 30, 300, 99]

이 예제를 잘보면 정렬이 우리가 예상한대로 되지 않았다는 것을 알 수 있다.  

우리 생각대로라면 [1, 2, 3, 10, 20 ,30, 99, 100, 200, 300]  이와 같이 정렬이 되야하는데 뭔가 이상하다. 

이렇게 정렬이 된 이유는  "10"의 유니 코드 순서는 "2"의 유니 코드 순서보다 빠르기 때문이다. 

마찬가지로 "99"의 유니코드 순서보다 "200"의 유니코드 순서가 빠르기에 더 앞으로 정렬이 되었다. 

 

 

숫자

그럼 숫자는 어떻게 정렬을 해야할까? 

arr = [1, 2, 3, 10, 20, 30, 100, 200, 300, 99];

arr.sort((a, b) => a - b);

console.log(arr); // [1, 2, 3, 10,  20, 30, 99, 100, 200, 300]

이렇게 compareFunction를 직접 정의 해서 해야한다. 

 

compareFunction은 어떻게 생겼을까?

function compare(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

return 값이 음수인 경우 a를 b보다 앞으로 정렬한다.  즉, a가 먼저온다. 

return 값이 양수인 경우 b를 a보다 앞으로 정렬한다.  즉, b가 먼저온다. 

return 값이 0인 경우 아무것도 정렬하지 않는다. 

 

여기서  첫 번째 if 문에 a > b 를 넣고 두 번째 if 문에 a < b를 넣으면 내림 차순이되고

첫 번재 if문에 b > a를 넣고 두 번째 if 문에 b < a를 넣으면 올림차순이 된다.  이 부분은 조금 뒤에 자세히 알아보고 

 

if문 말고 a-b  or b-a를 사용해서 구하는 법을 알아보자. 

숫자를 정렬할때  이 방법이 많이 사용된다.  

문자가아닌 숫자는 두 수를 뺄셈을 통해 양수,음수,0을 구할 수 있으니 가능한 것이다. 

그래서 만약 a-b가 양수이면 a가 더 큰 것이고  음수이면 b가 더 큰것이고  0이면 서로 같다는 것이다. 

 

아래 예시를 통해 sort가 정렬하는 과정을 알아보자 

arr = [3, 1, 4, 2];

arr.sort((a, b) => a - b)

1. 첫 번째 비교 

a=3, b=1

비교 함수 'a - b'를 사용하면  'a - b = 2'가 된다. 

양수가 된다는 소리는 "b를 a보다 앞으로 정렬한다."이다.  첫 번째 요소(a) 3이 두 번째 요소(b) 1보다 뒤로 정렬된다는 뜻이다. 

따라서 배열은 '[1, 3, 4, 2]' 로 변경이 된다. 

 

2. 두 번째 비교 

a=3, b=4 

비교 함수 'a - b'를 사용하면, '3 - 4 = -1' 가 된다. 

음수가 된다는 소리는 "a를 b보다 앞으로 정렬한다"이다. 첫 번째 요소(a) 3이 두 번째 요소(b) 4 앞으로 정렬된다는 뜻이다. 

하지만 이미 그렇게 정렬되어있어서 배열은 '[1, 3, 4, 2]' 그대로 이다. 

 

3. 세 번째 비교

a = 4, b = 2

비교 함수 'a-b'를 사용하면, '4 - 2 = 2'가 된다.

양수가 된다는 소리는 "b를 a보다 앞으로 정렬한다."이다. 첫 번째 요소(a) 4가 두 번째 요소(b) 2보다 뒤로 정렬된다는 뜻이다. 

따라서 배열은  '[1, 3, 2, 4]'로 변경된다. 

 

다시 처음으로 돌아와서 비교를 시작한다. 

 

4. 첫 번째 비교 

a = 1, b = 3

비교 함수 'a - b'를 사용하면 '1 - 3 = -2'가 된다.

음수가 된다는 소리는 "a를 b보다 앞으로 정렬한다"이다.  첫 번째 요소(a) 1이 두 번째 요소(b) 3보다 앞으로 정렬된다는 뜻이다. 

하지만 이미 그렇게 정렬되어 있어서 배열은 '[1, 3, 2, 4]' 그대로 이다. 

 

5. 두 번째 비교

a = 3, b = 2

비교 함수 'a - b'를 사용하면 '3 - 2 = 1'이 된다. 

양수가 된다는 소리는 "b를 a보다 앞으로 정렬한다."이다.  첫 번째 요소(a) 3이 두 번째 요소(b) 2보다 뒤로 정렬된다는 뜻이다.

따라서 배열은 '[1, 2, 3, 4]'로 변경된다. 

 

6. 세 번째 비교 

a = 3, b = 4

비교 함수 'a-b'를 사용하면 '3 - 4 = -1'이 된다.

음수가 된다는 소리는 'a를 b보다 앞으로 정렬한다."이다. 첫 번째 요소(a) 3이 두 번째 요소(b) 4보다 앞으로 졍렬된다는 뜻이다.

하지만 이미 그렇게 정렬되어 있어서 배열은 '[1, 2, 3, 4]' 그대로이다. 

 

이렇게 반복이 끝나고 sort함수도 끝이나서 정렬이 완성된다. 

 

만약 내림차순으로 하고 싶다면  sort((a, b) => b - a)를 하면 된다. 

왜냐하면 지금 설명한 예시의 반대 값이 나오기때문이다. 

음수였음 양수로 양수였음 음수로 나오기때문에 자연스럽게 내림차순으로 정렬이 된다. 

 

sort함수는 효율적인 정렬 알고리즘을 사용하여 배열을 정리한다. 

일반적으로 퀵소트 또는 Timesort와 같은 고성능 정렬 알고리즘을 구현하여 sort 함수를 실행한다. 

 

정렬 알고리즘의 동작 방식에 따라 최선의 경우, 평균적인 경우, 최악의 경우의 시간복잡도가 다를 수 있다. 

일반적으로 퀵소트는 평균 적으로 O(n log n)의 시간 복잡도를 가지며, 병렬 정렬(MergeSort)또는 팀소트(Timsort)는 최악의 경우에도 O(n log n)의 시간 복잡도를 가진다. 

 

 

이런식으로 문자도 정렬이 될까?  결론부터 말하면 NO이다

arr = ['b', 'c', 'a', 'd'];

arr.sort((a, b) => a - b);

console.log(arr); //[ 'b', 'c', 'a', 'd' ]

아예 정렬이 되지 않는다. 

그럼 문자열 정렬은 어떻게 해야할까 ?

 

 

문자열

 

처음에도 보았듯이 그냥 sort()만 사용해도 문자는 오름차순으로 정렬이 잘 된다.  

그럼 내림차순은 어떻게 해야할까?  

const arr = ['c', 'a', 'b'];

// 오름 차순 1
arr.sort();
console.log(arr); // [ 'a', 'b', 'c' ]

// 오름차순 2
arr.sort((a, b) => {
  if (a > b) {
    return 1; // 양수를 return 한다는 것은 -> a가 b보다 크면 a를 b보다 뒤로 정렬 
  } else if (a < b) {
    return -1; // 음수를 return 한다는 것은 -> a가 b보다 작으면 a를 b보다 앞으로 정렬
  } else {
    return 0; // a와 b가 같으면 순서 변경하지 않음
  }
});
console.log(arr); // [ 'a', 'b', 'c' ]

// 내림 차순
arr.sort((a, b) => {
  if (a > b) {
    return -1; // a가 b보다 크면 a를 b보다 앞으로 정렬 (음수)
  } else if (a < b) {
    return 1; // a가 b보다 작으면 a를 b보다 뒤로 정렬 (양수)
  } else {
    return 0; // a와 b가 같으면 순서 변경하지 않음
  }
});
console.log(arr); // [ 'c', 'b', 'a' ]

 

 

 

이걸 응용하면 이제 객체도 정렬할 수 있다. 

const todos = [
  { id: 4, content: 'JavaScript'},
  { id: 1, content: 'HTML'},
  { id: 2, content: 'CSS' }
];

//비교함수. 매개변수 key는 프로퍼티 키다.
function compare(key) {
	// 프로퍼티 값이 문자열인 경우 - 산술 연산으로 비교하면 NaN이 나오므로 비교 연산을 사용한다.
    // 비교 함수는 양수/음수/0을 반환하면 되므로 - 산술 연산 대신 비교 연산을 사용할 수 있다.
    return (a, b) => (a[key] > b[key] ? 1 : (a[key] < b[key] ? -1 :0 ));
}

// id를 기준으로 오름차순 정렬
todos.sort(compare('id'));
console.log(todos);

/*
[

const todos = [
  { id: 1, content: 'HTML'},
  { id: 2, content: 'CSS' },
  { id: 4, content: 'JavaScript'},
];

]
*/

//content를 기준으로 오름차순 정렬
todos.sort(compare('content'));
console.log(todos);

/*
[
   { id: 2, content: 'CSS' },
   { id: 1, content: 'HTML'},
   { id: 4, content: 'JavaScript'},
]
*/