11월 2주차로 버블, 삽입 등 다양한 정렬 알고리즘을 배우기 위해 아웅다웅하고 있던 도중 문득 이런 궁금증이 들었다.
JS의 배열에 쓰이는 sort() 메소드가 있는데 시간복잡도가 O(nlogn) 정도 걸린다. JS로 정렬 알고리즘 문제를 푸는데 필수인 이 아이는 어떤 정렬 알고리즘을 사용하고 있는 것인지 의문이 들었다. 그래서 파고들어봤다.
근데 하면서도 후회했다. 이렇게 복잡할지.. 몰랐기에..
정렬 종류와 배경 지식
우선 정렬에는 다양한 정렬이 있다. 
위 이미지는 버블, 삽입(Insertion), 힙, 병합(Merge) 등등의 시간복잡도, 메모리, 안정(Statement)을 나타내는 표다.
여기서 핵심은 시간복잡도이다. 배열의 개수, 크기 순 배치 정도 등을 포함해 최선, 평균, 최악을 나눠 시간복잡도를 나타냈다. 그렇다면 시간 복잡도의 원리를 알아야한다..
배경: 시간복잡도
시간복잡도란 n개의 배열이 입력값으로 있고 n개의 배열을 정렬할 때 걸리는 시간을 '빅오 표기법'으로 나타낸 단어를 뜻한다. 그냥 상대적인 단위라고 생각하면 된다.
O(1)는 어떤 입력값이든 시간이 늘어나지 않는 특성을 지닌 알고리즘을 뜻하고, O(n)은 n이 커질 수록 처리 시간도 선형적으로 늘어나는 알고리즘을 뜻한다.
여기서 무조건 알아가야하는데 로그복잡도라고 불리는 O(log n)이다. 쉽게 얘기해서 값을 탐색하며 노드가 넘어가는데(1회차, 2회차... ) n / 2가 돼 매우 짧아지는, O(1)와 매우 근접하는 좋은 복잡도이다.
나머지 O(n^2) 등은 보지말고 핵심은 우리가 시간복잡도를 생각할 때 우리는 최소한 O(n log n) 이하를 추구해야한다.
참고로 O(logn)은 O(log₂n)과 똑같다. 빅오 표기법
배경: 참조 지역성 원리
시간복잡도는 다양한 요소들이 있다. O(nlogn)의 공식을 살펴보면 C × nlogn + α으로 이루어져있다.
α는 정렬 이외의 부산물로 걸리는 시간을 뜻해 상대적으로 무시할 수 있는 반면 C는 '참조 지역성 원리'에서 나온 값으로 실제 동작 시간에 큰 차이가 생긴다. 양파도 아니고 까도까도 배울 게 나온다.
'참조 지역성 원리'는 CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리다. 간단하게 말해서 CPU가 최근 참조한 메모리를 다시 참조할 확률이 높아 '캐시 데이터'에 담아둔다는 얘기다. 이러한 특성으로 연속된 메모리를 연속으로 읽는 작업이 떨어져 있는 메모리들을 읽는 것보다 빠르다!
비슷하게 시간을 줄여주는 알고리즘 중 하나가 재귀의 Memoization이다. 메모이제이션은 참조할 데이터를 따로 변수에 넣어놔 해당되는 값이 있으면 참조하여 그 값을 바로 꺼내쓸 수 있어 시간을 줄여주는데 변수의 역할이 캐시 메모리라고 생각하면 된다.
sort()의 탄생
sort()의 탄생 배경
이러한 배경 속에서 개발자들은 정렬에 대한 메소드, 함수를 구현해내고 싶었다. 왜냐면 정렬할 때마다 다양한 정렬의 코드를 암기하여 매번 쓰면 불편하고 생산성이 떨어지니까. 하지만 위 표를 보면 메소드 특성상 다양한 상황에서 매번, 거의 모든 코드에 적용돼야하는데 정렬이 특히 상황마다 시간도 천차만별이고, 배열 특성상 상황마다 메모리를 잡아먹는 것도 달라 기존에 있던 정렬 알고리즘만으로는 무리가 있었다.
위 표를 보면 그런 생각이 들지 않는가? 추가 메모리도 적고 평균 최악 모두 O(nlogn)걸리는 힙 정렬을 쓰면 되지 않냐 라고 하는데 힙 정렬은 다른 정렬들관 달리 한 위치에 있는 요소를 해당 요소의 인덱스 두 배 또는 절반인 요소와 반복적으로 비교하는 특성상 캐시 메모리가 예측하기 어려워 거의 참조를 못한다.
다시 말해 C의 크기가 매우 크다.
병합 정렬은 C의 크기가 작지만 또 메모리를 크게 잡아먹는 단점, 퀵 정렬은 피벗 주변에서 데이터의 위치 이동이 빈번하게 발생하는 특성상 C의 크기도 작고, 메모리도 적게 잡아먹고 시간복잡도도 평균적으로 적지만 피벗을 잘못 잡으면 O(n^2)만큼 걸린다.
그래서 다 갖다쓰기에는 어떤 정렬이 탁월하게 좋다고 선택할 수가 없었다. 여기서 우리의 히어로
'Tim Peters'라는 개발자가 'Tim sort'를 들고 나타났다.
Tim sort의 sort()
대부분의 상황에서 정렬 알고리즘을 쓸 수가 없어 슬퍼하던 sort()는 Tim 선생님을 만나 가르침을 받아 삽입 정렬과 병합 정렬을 합한 알고리즘을 배웠다. 두 정렬이 만나서 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는 O(nlogn)을 이뤘고, 메모리를 추가로 사용하지만 병합 정렬보단 적게 사용해 기존 O(nlogn)를 가진 정렬 알고리즘들의 뺨들을 후려버렸다.
Tim sort의 원리
참고
- 병합 정렬: 두 덩어리로 반복해서 나누고 정렬한 뒤 모으는 정렬, 하나의 덩어리로 만드는 과정에서 n의 추가 메모리와 두 덩어리의 크기의 합만큼의 시간이 소요
- 삽입 정렬: 순회하며 그 수가 전 인덱스 값들을 보며 어느 위치에 있어야하는지 판단 후 삽입, 정렬할 수가 클수록 시간이 비교적 더 많이 늘어남
기본적인 것만 간단하게 설명하자면 RUN이라는 Tim sort만의 용어가 있고, 병합 정렬처럼 덩어리를 나눈 것들을 뜻하는데 병합관 달리 증가하는 RUN, 감소하는 RUN으로 나눠 삽입 정렬을 진행하고 최적화된 병합을 통해 새 정렬을 탄생시켰다.
한마디로 특징을 정리하자면,
- 작은 단위에서는 최고의 효율을 내는 삽입 정렬, 큰 단위는 병합 정렬로 쪼개 좋은 효율 내게 사용한다.
- 병합 정렬을 하기 위해서 분리하는 단위인 RUN은 크기가 가변적.
- Tim 정렬의 병합의 문제(병합에 소비되는 메모리, 크기가 가변적이라 안정성을 유지하기 위해 크기를 비슷하게 만들어야하는 병합 정렬과 충돌)해결 위해 최적화(Galloping, 크기가 비슷하게끔 합차기 반복)를 요했다.
- 삽입 정렬은 이진 탐색으로 삽입(Binary Insertion sort)을 하여 더 빠른 삽입 정렬이 가능하다.
- 삽입해야 할 위치를 찾을 때까지 비교하는 대신, 앞의 원소들은 모두 정렬되어 있다는 전제를 기반으로 이분 탐색을 진행하여 위치를 찾는다.
이러한 정렬의 장점 조합과 최적화 기법을 통한 단점 커버로 정렬의 모범을 만들어냈고, 많은 언어에서 표준 정렬 알고리즘으로 채택하여 사용하고있다! 고마워요 팀!
참고 사이트: Tim sort에 대해 알아보자
