솔미는 성장중
[JS 궁금증] Array.sort는 어떤 알고리즘으로 동작할까? & 정렬 방식에 대한 알고리즘 본문
🎯 궁금증 계기
표준 내장 객체를 공부하다가 Array.sort에 대해 접하게 되었다.
예시코드)
const numbers = [3,88,1,28,501,210]
numbers.sort((a,b) => a-b)
console.log(numbers) //[1, 3, 28, 88, 210, 501] <- 오름차순
이때 a랑 b에 아이템들이 어떤 순서로 들어가는지에 대한 궁금증이 들었다.
(1,3), (1,28), ...(1,501), (3,28), (3,88), ... (210,501) 이렇게 무식하게 다 비교했으려나..?
뭔가 더 효율적인 알고리즘으로 제작되지 않았을까?!
그래서 우선 sort의 mdn 문서를 정독했다. 하지만 내가 원하는 답은 없었고, 대체로 '사용방법'에 대한 내용이었다.
사용방법이 궁금하다면 읽어보는 것을 추천한다!
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
Array.prototype.sort() - JavaScript | MDN
sort() 메서드는 배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환합니다. 정렬은 stable sort가 아닐 수 있습니다. 기본 정렬 순서는 문자열의 유니코드 코드 포인트를 따릅니다.
developer.mozilla.org
생각보다 정보를 찾기 어려웠고 그러던 중 한줄기 빛같은 글을 하나 발견했다. ヾ(•ω•`)o
🎯 sort의 정렬 방식에 대한 이야기
우선 링크부터 첨부한다!
어느 정도 기본 지식이 있다면 아래 링크 참고하길 바란다 ( •̀ ω •́ )✧
글쓴이는 뉴비에 가깝기 때문에 차근차근 이해해가는 글을 쓸 예정이다! (구체적인 코드는 다루지 않을 예정이다.)
[JavaScript] Array.sort 는 안정성을 보장할까?
JavaScript 의 sort 함수는 안정 정렬일까? 📌 안정 정렬이란? 안정 정렬(stable sort) 은 동일한 키 값에 대해 입력 순서를 보장하는 정렬 알고리즘입니다. 그 반대인 불안정 정렬(unstable sort) 은 정렬 후
handhand.tistory.com
이 글의 결론부터 이야기하자면 JS의 sort는 Timesort 알고리즘을 사용한다.
이에 대한 코드 분석 내용을 보고 싶다면 스크롤을 쭉 내려서 링크를 확인하면 된다!
🎯 안정 정렬? 불안정 정렬?
정렬에 대해서 알아보기 시작하니 크게 '안정 정렬'과 '불안정 정렬'로 나뉜다고 한다.
sort에 사용되는 정렬이 어떤 것인지 알기 위해선 먼저 알고 가야할 내용이다!
> 무엇이 안정적이라는 걸까? : 안정 정렬, 불안정 정렬 개념
안정 정렬부터 이야기해보자.
이는 말 그대로 안정적인 정렬이다.
그럼 무엇이 안정적이라는 걸까?
안정적이다
= 정렬을 하고 난 뒤에도 같은 key값을 가진 원소들의 순서가 유지된다
= 기존의 순서 유지가 보장된다
wiki에서 예시 사진을 가져왔다.
좌측 사진은 하트5와 스페이드5를 정렬하는 상황이다!
Stable쪽을 보면
5라는 숫자를 배열할 때 하트-스페이드 순서가 그대로 유지되는 것을 볼 수 있다.
이처럼 정렬 후에도 기존의 순서 유지가 보장되는 정렬이 안정 정렬이다.
반면 Not Stable쪽을 보면
하트-스페이드 순이 아닌 스페이드-하트 순인 것을 확인할 수있다.
이처럼 정렬한 후에 기존의 순서 유지가 보장되지 않는 정렬이 불안정 정렬이다!
(순서가 바뀔 수도 있고 아닐 수도 있음)
🎯 안정 정렬을 더 파보자!
> 안정 정렬의 예
대표적으로 삽입, 합병(병합), 버블 정렬이 있다.
> 1. 삽입 정렬 (insertion sort)
- 핵심
: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 알고리즘
- 이해를 도울 그림
애니메이션을 통해 개념을 확인하고 싶으면 아래 링크를 참고하면 된다!
https://ko.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/insertion-sort
장점
1. 안정적이다
2. 배열 내 요소가 적으면 다른 방법보다 유리할 수 있다.
3. 대부분이 이미 정렬된 상태라면 효율적이다.
단점
1. 많은 이동을 요할 수 있다.
2. 크기가 큰 배열을 다룰 땐 적합하지 않다.
> 2. 합병(병합) 정렬 (merge sort)
- 핵심
: 하나의 문제를 2개의 문제로 분리하여 각각 해결한 후에 결과를 모아서 본래 문제를 해결하는 전략!
- 과정
1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
2. 그렇지 않은 경우, 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
- 이해를 도울 그림
장점
1. 안정적이다
2. 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아져 그 어떤 정렬 방법보다도 효율적이다.
단점
1. 과정에 임시로 결과를 저장하는 배열이 따로 또 필요하기 때문에 메모리 자원 측면에서는 비효율적일 수 있다.
> 3. 버블 정렬 (bubble sort)
- 핵심
: 서로 인접한 두 원소를 검사해 순서대로 되어있지 않으면 교환한다
: 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
- 이해를 도울 그림
장점
1. 안정적이다
2. 구현이 간단하다
단점
1. 많은 이동을 요할 수 있다.
2. 특정 요소가 올바른 위치에 이미 있는 경우에도 교환되는 일이 생긴다.
일반적으로 '이동'작업보다 '교환'작업이 더 복잡하기 때문에 구현이 간단함에도 불구하고 버블 정렬은 거의 쓰이지 않는 방식이라고 한다...!
🎯 불안정 정렬을 더 파보자!
> 불안정 정렬의 예
대표적으로 퀵, 선택, 힙 정렬이 있다.
> 1. 퀵 정렬
- 안정 정렬의 '합병 정렬'과 비슷하게 분할 정복 알고리즘.
(문제를 2개의 작은 문제로 분리하고 각각 해결한 후 결과를 모아서 원래 문제를 해결하는 전략)
- 하지만 퀵 정렬은 리스트를 '비균등하게' 분할한다.
과정
1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
- 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
- 리스트의 크기가 0이나 1이 될 때까지 반복한다.
- 이해를 도울 그림
장점
1. 속도가 빠르다
2. 추가 메모리 공간을 필요없다.
단점
1. 정렬된 리스트에 대해선 퀵 정렬의 '불균형 분할' 때문에 수행시간이 오히려 길어진다.
불균형 분할에서 오는 문제들 때문에 피벗을 선택할 때 데이터의 중간값을 골라 균등하게 분할하는 경우도 있다고 한다!
> 2. 선택 정렬
- 배열의 인덱스 위치를 정한 후, 가장 작은 원소를 넣으며 순차적으로 정렬하는 알고리즘
(즉, 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 찾는 과정)
- 과정
1. 주어진 배열 중에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
(1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 된다!)
- 이해를 도울 사진
장점
1. 자료 이동 횟수가 미리 결정된다.
단점
1. 불안정 = 값이 있는 레코드가 있는 경우 상대적인 위치가 변경될 수 있다
2. 효율이 떨어지는 편..
> 3. 힙 정렬 (Heap sort)
- 최대 힙 트리(내림차순 정렬)나 최소 힙 트리(오름차순 정렬)를 구성해 정렬을 하는 방법
- 과정
1. 정렬하고자 하는 배열을 힙으로 만든다. (이 과정을 heapify라고 한다.)
2. 정렬된 원소들이 저장될 새로운 배열을 생성한다. (이 배열을 정렬 배열이라 부르자.)
3. 힙의 루트노드의 값을 정렬 배열에 append하고, 루트 노드의 값을 삭제한다.
4. 삭제 한 후 나머지 트리에 대해서 다시 힙으로 만든다. (heapify)
5. 힙에 남은 원소가 하나도 없을 때까지 3~4번 과정을 반복한다.
6. 힙에 남은 원소가 없으면, 정렬 배열 속 원소들은 모두 정렬이 되어있다. (Min Heap의 경우 오름차순, Max Heap의 경우 내림차순으로 정렬이 된다.)
(출처: https://hoons-dev.tistory.com/8)
힙 = 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
- 이해를 돕기 위한 그림 (새로운 요소 8을 삽입하는 경우)
장점
1. 시간복잡도가 O(nlogn)인 정렬 알고리즘 중에는 부가적인 메모리가 전혀 필요없다는게 장점
단점
1. 불안정하다.
2. 일반적으로 속도만 비교하자면 퀵이 평균적으로 더 빨라서 굳이 사용하지 않는다.
힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때!
Run-time도 가장 짧고(=효율이 좋고), 안정 정렬이기까지한 병합 정렬이 가장 좋은 정렬이 아닌가 하는 생각이 들었다.
하지만 어떤 정렬이든 장단점이 존재하고, 상황에 따라 복잡한 구현이 필요없는 경우도 있을 테니 때에 따라 알맞은 것을 선택해서 고르면 될 것 같다!
꼭 짚고 넘어가야될 것은 불안정 하다는 것이 성능이 좋지 않다는 뜻이 아니다.
기존의 정렬된 값이 필요없다면, 퀵 정렬은 난수에 가까운 수들을 정렬하는데 아주 효과적인 것이라고 할 수 있다. 그럴 때 퀵 정렬을 활용할 수 있다!
먼 길을 돌아왔다.........
그래서 JS에서 Array.propotype.sort()에는 도대체 어떤 알고리즘이 숨어있다는 것인가!!>!?!?
🎯 다시 본론으로.. JS에서 sort는 어떤 알고리즘을 사용하는가?!
위에서 안정/불안정 정렬을 정리하다보니 표준 내장 객체는 안정 정렬을 사용해야되지 않을까?하는 생각이 들었다.
그런데 신기하게도 이전에는 어떤 것으로 해야한다고 지정되어있지 않아 엔진 구현체마다 정렬방식이 달랐고, 안정 정렬일 수도 있고, 불안정 정렬일 수도 있었다고 한다.
(소스 코드가 궁금하다면 맨 처음 언급했던 링크에 접속해보길 바란다.)
하지만 지금은! 안정 정렬을 사용한다고 한다.
JS의 sort 알고리즘은 바로 'TimeSort'알고리즘!!!!!
직접 소스코드를 뜯어서 분석해 보신 분의 글이다.
찬찬히 읽어보면 이해가 될 것 같다ㅎㅎ
https://taes-k.github.io/2021/04/19/java-sort/
몰라도 되는 Java - sort 알고리즘
java array sort 자바의 Array와 Collection 등 다수의 데이터를 다루는 자료형에서는 대부분 간편하게 데이터를 정렬 할 수 있도록 sort기능을 제공하고 있습니다. 버블소트, 카운팅소트, 인서트소트, 퀵
taes-k.github.io
그리고 글로 timesort방식을 설명하신 분의 글이다! 개인적으로 이게 더 이해하기 쉬운 것 같다.
궁금증에 대한 답이 되었길! (๑•̀ㅂ•́)و✧
https://noirstar.tistory.com/359
[Javascript] sort() 동작 방식 (내부 알고리즘)
일단 sort 에 대해서 정확한 이해가 필요하다고 생각하여 글을 쓰게 되었음. 뭔가 정리를 안해놓으면 또 까먹을거같아서.. 찾아보다가 좋은 글이 있어서 퍼왔는데 이분이 설명을 잘해놓은듯함.
noirstar.tistory.com
출처)
안정 정렬과 불안정 정렬 https://blog.naver.com/PostView.nhn?blogId=raylee00&logNo=222070980588
버블 정렬 https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
'알아두면 좋을지도?' 카테고리의 다른 글
| Github - Discord Webhook 연결하기 ! (0) | 2023.12.26 |
|---|---|
| 브라우저 렌더링 과정 (0) | 2023.09.09 |
| class내에선 let/const로 선언해주지 않는 이유 (0) | 2023.08.25 |
| webpack 설정하는 방법 (1) | 2023.08.25 |
| [Github] 대용량 파일 깃허브에 업로드하기 (0) | 2023.07.17 |
