[JavaScript] sort() 의 동작방식 이해하기

1. sort() 메서드에서 첫번째 주의할 점은 () 안에 compareFunction Optional 즉

정렬 순서를 정의하는 함수를 생략하면, 배열은 각 요소를 문자열로 변환하고, 문자열에 따라 각 문자의 유니 코드 코드 포인트 값에 따라 정렬됩니다.

 

2. 두번째 주의할 점은 반환값으로는 원 배열이 변환되기 때문에 만약 원 배열을 훼손시키고 싶지 않으면 slice() 를 통해 얕은 복사를 한 뒤 사용해주는게 좋다.

 

//2개의 값을 비교했을때 양수면 순서가 바뀐다고 생각하면 됨.

let arr = [6,10,2]

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

// 1-1. 6 - 10 음수이기 때문에 값 변하지 않음 [6,10,2]
// 1-2. 6 - 2 양수이기 때문에 순서 변함 [2, 10, 6]
// 2-1. 2 - 10 음수이기 때문에 값 변하지 않음 [2, 10, 6]
// 2-2. 2 - 6 음수이기 때문에 값 변하지 않음 [2, 10, 6]
// 3-1. 10 - 6 양수이기 때문에 순서 변함 [2, 6, 10]
// 3-2. 6 - 10 음수이기 때문에 순서 변하지 않음 [2, 6, 10]


console.log(arr) // [2, 6, 10]

 

 

한 블로그의 댓글에서 설명이 잘 된 부분이 있어 퍼온 글! 읽어보면 sort 의 알고리즘이 어떻게 작동하는지 이해하기 쉽다.

구체적인 정렬 알고리즘은 프로그래밍 초심자가 이해하기 어려워서

이고잉님께서 일부러 설명을 스킵하신 것 같은데...

밑에 잘못된 정보가 있어 제가 굳이 설명을 보탭니다.


우선 [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)

디버깅해 보시면 쉽게 아실 수 있을 겁니다

출처 - 댓글에서퍼옴
https://opentutorials.org/course/50/109