[Javascript] sort() 동작 방식 (내부 알고리즘)

일단 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

---

sort 알고리즘 자체는 2개의 배열 인자를 뺄셈연산을 이용하여, 뺀값이 양수면 2개의 배열인자를 자리바꿈하고, 음수면 바꾸지않음.

javascript의 sort() defalut 동작은 오름차순으로 밑의 사진과 같이 a-b 로 뺐을때 음수가 나와 자리바꿈하지않음

 

내림차순으로 바꾸려면 뺀값이 양수가 나와야 하므로 밑의사진과 같이 b-a가 되야함