1. 왜 이 글을 쓰게 되었는가.
모든 신입 개발자들은 적어도 코딩 테스트를 한 번이라도 들어봤을 거라 생각한다.
나도 코테를 준비하면서 정렬 메소드를 사용하는 일이 많았는데
Arrays.sort()를 들어가 보니 DualPivotQuicksort를 사용하고
Collections.sort()를 들어가보니 TimSort 라는 수정된 병합 정렬 알고리즘을 사용하고 있었다.
여기서 근본적으로 든 왜 서로 다른 알고리즘을 사용할까 라는 궁금증에 기반을 둬 이 글을 작성하게 되었다.
2. 알고리즘에 중요성에 대해
정렬을 프로그래밍에서 빠질 수 없는 알고리즘 중 하나이다,
예를 들어
탐색을 위해서는 Brute-Force Search보다 정렬 후 binary search를 이용하는 방식이 당연히 빠르다.
정렬을 통해 더 빠른 속도의 탐색이 가능해진다
중복제거를 정렬 시에도 매우 쉽게 해결할 수 있다. ( Set 담으면 되다는 건 논외로 치자...!)
외에도 우선순위 큐 , 그래프, DB 인덱스 등에서 정렬 기능을 활용해 효율성을 높일 수 있다.
그러니 어느 정렬 알고리즘을 사용하는 게 좋을지 한 번쯤은 생각해 볼 만한 일인 것 같다.
3. 각각의 정렬 메소드들을 소개
정렬 알고리즘만 해도 수십 가지의 알고리즘이 있다.
시간 복잡도, 공간 복잡도, 안정성, 안정성 보장 여부에 따라 여러 종류의 알고리즘으로 나뉘지만
오늘은 궁금증이 나온 주제인 DualPivotQuicksort 와 Timsort에 대해서만 얘기해보자 한다.
3-1 DualPivotQuicksort
단어를 나눠보자
Dual : 이중
Pivot : 중심점
Quick Sort: 빠른 정렬
단순히 Pivot이 두개 있는 정렬 방식이다.
Pivot이 두개인거에 대해 이해하기 전
필수적인 선수지식으로 Quick Sort에 대한 이해가 필요하다.
DualPivotQuicksort에 대해 말하기전 Quick Sort에 대해 한번 알아보자
Quick Sort는 하나의 pivot을 기준점으로 잡고 보다
작은 데이터는 왼쪽 , 큰 데이터는 오른쪽으로 모으는 메소드를 재귀용법을 활용해
작업을 반복해 정렬하는 정렬 알고리즘 방식이다.
구현예제
public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
if (dataList.size() <= 1) {
return dataList;
}
int pivot = dataList.get(0);
ArrayList<Integer> leftArr = new ArrayList<Integer>();
ArrayList<Integer> rightArr = new ArrayList<Integer>();
for (int index = 1; index < dataList.size(); index++) {
if (dataList.get(index) > pivot) {
rightArr.add(dataList.get(index));
} else {
leftArr.add(dataList.get(index));
}
}
ArrayList<Integer> mergedArr = new ArrayList<Integer>();
mergedArr.addAll(this.sort(leftArr));
mergedArr.addAll(Arrays.asList(pivot));
mergedArr.addAll(this.sort(rightArr));
return mergedArr;
}위 예시는 직접 코드로 구현한 QuickSort 예제다.
순서대로 설명하자면 .
- 호출 시 전달 받은 파라미터의 사이즈를 측정해 더는 분리할 값이 없을 때 반환한다.
- 그 후 index의 첫 번째 value를 pivot으로 지정한다.
- 1번 index부터 값을 꺼내 pivot과 비교 후 작을 때 클 경우의 배열에 저장한다.
- 최종적으로 병합할 Array를 생성한다.
- 작은 값인 leftArr부터 저장해야 하지만 현재 leftArr의 값들은 pivot에 비해 작은 값일 뿐 정렬된 값은 아니기 때문에. 재귀 용법을 이용해 다시 한번 내부를 정렬하는 과정을 거쳐야 한다.
- 그 후 중간값과 rightArr또한 정렬 후 누적해 최종적으로 정렬된 List를 반환하게 된다.
엑셀로 열심히 그려봤다.
단순 QuickSort는 평균적으로 O(nlogN)의 시간 복잡도를 가진다.
하지만 이미지를 보고 약간 느껴질 수도 있지만, pivot에 따라 최대 O(n2)까지 가질 수 있는 상황을 만날 수도 있다.
- 이미 정렬된 값 같은 데이터는 depth가 한쪽 방향으로만 쭉 이어지게 되는 문제가 발생할 것이다.
- 이미지에서도 좌측으로 depth가 기울어진 모습을 보인다. (이런 경우가 극단적일 경우 O(N))
정렬 상태와 pivot에 따라 효율성이 급락하는 문제가 발생할 수 있다
이런 문제를 해결하기 위해 Quick Sort의 변형 알고리즘으로
두 개의 Pivot을 활용하는 DualPivotQuicksort 가
블라디미르 야로슬라프 스키, 존 벤틀리, 조시 블로흐 의해 만들어졌다.
DualPivot은 임의의 pivot을 두개 지정 한 후
- P1의 미만 영역
- P1 과 P2 사이의 이상과 이하 부분
- P2의 초과 영역
(이 때 P2는 항상 P1보다 커야 한다는 전제 조건이 있다. [ pivot 1 < pivot 2 ] )
큰 차이점은 기존 Quick Sort는 두개의 영역으로 나눈다는 점이지만
DualQuickSort는 3개의 영역으로 나눠 재귀 호출한다는 점이다.
이미지과 코드로 한번 확인해보자.
예시 이미지
구현 예제
public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
if (dataList.size() <= 1) {
return dataList;
}
int pivot1 = dataList.get(0);
int pivot2 = dataList.get(dataList.size() - 1);
if (pivot1 > pivot2) {
int temp = pivot1;
pivot1 = pivot2;
pivot2 = temp;
}
ArrayList<Integer> leftArr = new ArrayList<>();
ArrayList<Integer> midArr = new ArrayList<>();
ArrayList<Integer> rightArr = new ArrayList<>();
for (int index = 1; index < dataList.size() - 1; index++) {
int value = dataList.get(index);
if (value < pivot1) {
leftArr.add(value);
} else if (value >= pivot1 && value < pivot2) {
midArr.add(value);
} else {
rightArr.add(value);
}
}
ArrayList<Integer> mergedArr = new ArrayList<>();
mergedArr.addAll(this.sort(leftArr));
mergedArr.addAll(Arrays.asList(pivot1));
mergedArr.addAll(this.sort(midArr));
mergedArr.addAll(Arrays.asList(pivot2));
mergedArr.addAll(this.sort(rightArr));
return mergedArr;
}기존 quciksort와 매우 비슷하다는 걸 확인할 수 있다.
실제로도 엄청 큰 차이는 없고 하나의 분기가 더 생겨 처리하는 원리이다.
물론 이 사이 여러 최적화 기법이 적용될수 있다.
특정 위치의 피벗값이 아닌 랜덤한 위치를 지정하던데 하는 등
혹은 랜덤한 3개의 값중 중간 값을 선택하는 등여러 최적화 기법이 있다.
한번 실제로 비교해보자
public static void main(String[] args) {
Long avg = 0L;
Long low = Long.MAX_VALUE;
Long high = 0L;
int n = 100000;
for (int i = 0; i < 2500; i++) {
ArrayList<Integer> testData1 = new ArrayList<>();
ArrayList<Integer> testData2 = new ArrayList<>();
// 무작위 정수 데이터 생성
for (int index = 0; index < n; index++) {
testData1.add((int) (Math.random() * 1000000));
testData2.add((int) (Math.random() * 1000000));
}
long startTime, endTime;
// QuickSort 속도 측정
startTime = System.nanoTime();
QuickSort qSort = new QuickSort();
ArrayList<Integer> sorted = qSort.sort(testData1);
endTime = System.nanoTime();
long quickSortTime = endTime - startTime;
// Dual Pivot QuickSort 속도 측정
startTime = System.nanoTime();
DualPivotQuickSort dpqSort = new DualPivotQuickSort();
ArrayList<Integer> dualPivotSorted = dpqSort.sort(testData2);
endTime = System.nanoTime();
long dualPivotSortTime = endTime - startTime;
// 정렬 결과 검증
long result = quickSortTime - dualPivotSortTime;
avg += result;
if (low > result)
low = result;
if (high < result)
high = result;
//System.out.println(i + "번째 속도 비교 => " + result + "ns 만큼 빠르다");
System.out.print(".");
}
System.out.println("\n가장 빠를 때는 : " + high + " ns");
System.out.println("가장 느릴 때는 : " + low + " ns");
System.out.println("2500회 동안 평균적으로 : " + (avg / 20) + " ns");
}가장 빠를 때는 : 44495708 ns
가장 느릴 때는 : -29179542 ns
2500회 동안 평균적으로 : 315499497 ns 빠르다왜 이 정도로 차이가 발생할까?
qucik sort는 pivot을 기준으로 배열을 분할을 진행한다.
이때 pivot에 따라서 배열을 불균형한 분열 탓인 성능저하가 발생한다.
이러면 O(N²)까지 복잡도가 증가하게 된다.
하지만 pivot을 두개를 지정하게 되면 . 두 값 사이의 중심 지점이 정해져 보다 훨씬 균등한 분배가 가능하다.
물론 슈퍼볼도 당첨되는 세상에서 매우 드물지만
Dual Pivot 또한 O(N²)의 시간 복잡도를 가지는 상황이 있을수 있다.
( 이미 정렬된 배열 , 모든 값이 정렬된 배열 )
이러한 문제를 해결하기 위해 재귀 호출의 깊이를 제한하거나 ,
pivot을 무작위로 선택한 값들 중 중앙값을 사용하는 등의
여러 최적화 기법이 있지만, 자바의 DualPivotQuicksort는 이러한 최적화 기법을 사용한다.
대표적인 최적화 기법
🌫️ Median of Three: 3개의 원소를 골라 중간값을 사용한다.
🌫️ Bentley-McIlroy 3-way partitioning: pivot과 같은 값도 중간 영역으로 포함시기는 방식
🌫️ Cutoff to insertion sort: 분할된 크기가 일정 크기 이하일 경우 INSERT Sort를 사용한다.Arrays.sort는 왜 다른 알고리즘이 아닌 DualPivotQuicksort를 선택했을까.
-
sort에서 사용되는 알고리즘은 하나가 아니다. 타입이 Object와 같은 경우에는 TimSort를 호출한다.
다만 기본자료형으로 호출 시 DualPivotQuicksort가 제공된다. -
Merge Sort의 겨우 안정적이고 시간 복잡도가 어느 정도 보장되었지만
실제로 사용 시 단순 QucikSort나 Heap Sort보다 느린 경우 다수 있다. -
Collections.sort에서 사용하는 Tim Sort는 7 버전에서는 사용되었지만 8버전부터는 DualPivotQuicksort로 변경되었다. 메모리 사용량 최적화가 목적이 아니었을까 싶다.
- Arrays.parallel Sort()를 사용하면 Tim Sort를 사용할 수 있다.
- 마지막으로 가장 빠르고 효율적인 알고리즘이기 때문이다.
참고로 JAVA 8 기준 배열의 길이가 길이가 짧은
Insertion Sort알고리즘을 사용한다.
이 작다의 기준은 배열의 길이가 47 이하일 경우로 명시한다이 수치 미만은 Dual-Pivot의 방식이 오히려 독으로 작용하기 때문이다.
3-2 Timsort
Collections.sort()는 자바 7 이전까지는 Merge sort를 활용했고.
8버전 이후부터는 Tim Sort를 사용한다.
Timsort는 Tim Peters라는 인물에 의해 탄생하게 된. 안정성이 보장된 알고리즘이다
Merge Sort와 Insert Sort를 결합해 만든 하이브리드 정렬 알고리즘이다
최악의 경우에도 O(n log n)의 시간 복잡도를 가진다.
Tim Sort에 대해 알아보다 네이버에서 제공한 글에서 참조 지역성이라는 새로운 개념을 학습하게 되었다.
이 글을 보시는 분은 저 글도 꼭 한번 읽어봤으면 좋겟다.
알고리즘이 O(n log n)시간 복잡도를 가지게 되면 실제 동작 시 C × nlogn + a 라는 식을 가지게 되는데
C는 하드웨어 환경을 의미하는 상수인데 기본적인 동작 속도와 같은 부분이기 때문에 알고리즘의 수행 속도에 많은 영향을 끼친다.
a는 알고리즘의 복잡도를 결정하는 상수값을 의미한다.
( 들어오는 배열의 구성 등을 의미)
글에서 설명하는 개념으로 C에 큰 영향을 끼치는 것은 참조 지역성인데 이 부분을 보자면
모든 정렬 알고리즘은 각자 장단점이 있어 참조 지역성이 좋은 알고리즘과 복잡도가 낮은 알고리즘을 융합해
실제 데이터의 타입과 상관없이 최적화하기 위해 탄생하게 된 알고리즘이 Tim Sort이다.
최선은 O(n) , 최악은 O(n log n) 으로 공간복잡도는 좀 더 소모되지만, 안정적이고
다른 n log n 효율성의 알고리즘들의 단점을 극복했다.
동작 원리에 대해 순서대로 적어보자면.
- 일정한 크기로 분할을 진행한다. ( 보통 32~64의 블록 범위)
- 분할된 블록들을 Insertion Sort 알고리즘을 이용해 정렬한다.
- 분할된 블록들을 더 작은 단위의 블록들로 묶어 Merge Sort 알고리즘을 이용해 병합한다.
- 병합된 블록들이 하나가 될 때까지 반복적으로 병합과정을 수행한다.
- 병합된 하나의 블록이 전체 데이터를 정렬된 상태로 만든다.
분할된 블록들을 Insertion Sort로 정렬하는 과정을 통해서 블록들 내에서 발생하는 교환 비용을 줄일 수 있다.
Merge Sort를 이용하여 블록들을 병합하는 과정에서 일정한 크기의 블록으로 분할하여 병합하는 방식을
사용해 불필요한 비교 및 복사 작업을 줄여 실행 시간을 최적화할 수 있다.
예시 코드
import java.util.Arrays;
public class TimSort {
static int MIN_MERGE = 32;
public static void main(String[] args) {
int[] arr = {-2, 7, 15, -14, 0, 15, 0, 7,
-7, -4, -13, 5, 8, -14, 12};
int n = arr.length;
System.out.println(Arrays.toString(arr));
timSort(arr, n);
System.out.println(Arrays.toString(arr));
}
}
결과
[-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12]
[-14, -14, -13, -7, -4, -2, 0, 0, 5, 7, 7, 8, 12, 15, 15]
- main method에서 timSort를 호출해 정렬을 수행하게 된다
public static void timSort(int[] arr, int n) {
int minRun = minRunLength(MIN_MERGE);
for (int i = 0; i < n; i += minRun) {
insertionSort(arr, i, Math.min((i + MIN_MERGE - 1), (n - 1)));
}
for (int size = minRun; size < n; size = 2 * size) {
for (int left = 0; left < n; left += 2 * size) {
int mid = left + size - 1;
int right = Math.min((left + 2 * size - 1), (n - 1));
if (mid < right)
merge(arr, left, mid, right);
}
}
}minRunLength()메소드를 실행하여minRun값을 계산한다.
- 배열의 크기를 탐색 해 적정한 수준의 최소 런 크기를 계산한다.
- 효율 적인 병합을 위해 반드시 필요한 과정
-
public static int minRunLength(int n) {
assert n >= 0;
int r = 0;
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}insertionSort()메소드를 실행하여minRun크기만큼 배열 일부분을 정렬한다.- 해당 부분이 이미 정렬된 부분일 경우 추가적인 연산을 최소화하기 때문이다.
- 작은 정렬일 경우 삽입 정렬이 더 빠르므로 이 러한 로직을 수행한다.
-
public static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= left && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}merge()메소드를 실행하여 정렬된 서브 배열들을 병합한다. 이때 병합되는 배열들의 크기는 2배씩 증가한다.- 삽입 정렬되어 이미 정렬된 배열들을 병합하는 과정을 가진다.
- 삽입 정열로 어느정도 정렬된 상태이기 때문에 효율적인 동작을 하게 된다.
- 삽입 정렬되어 이미 정렬된 배열들을 병합하는 과정을 가진다.
public static void merge(int[] arr, int l, int m, int r) {
int len1 = m - l + 1, len2 = r - m;
int[] left = new int[len1];
int[] right = new int[len2];
for (int x = 0; x < len1; x++) {
left[x] = arr[l + x];
}
for (int x = 0; x < len2; x++) {
right[x] = arr[m + 1 + x];
}
int i = 0;
int j = 0;
int k = l;
while (i < len1 && j < len2) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < len1) {
arr[k] = left[i];
k++;
i++;
}
while (j < len2) {
arr[k] = right[j];
k++;
j++;
}
}- 2~3번 과정을 반복하여 전체 배열을 정렬한다.
실행 예시
Tim sort 같은 경우 하나의 글에서만 작성해도 될 정도로 내부의 구현이 예시보다 더 복잡한 느낌이라
어떻게 동작하고 어느 장점이 있는 지선에서 마무리하였다.
다 적진 못했지만 몇몇 블로그에서 매우 많은 도움을 받았는데
다른 사람들도 읽어봤으면 좋겟다.
네이버 D2
st-lab : 팀정렬 (Tim Sort)
결론
글을 다 적고 나니 두 알고리즘의 속도를 비교하는 건
두 알고리즘의 목적이 다르다 보니. 살짝 무의미하다고 생각된다
Arrays.sort 또한 객체가 들어올 경우에는 TimSort를 호출하는데
어느 타입을 정렬하는지 , 속도가 중요한지, 안정성이 중요한지등을 고려해 선택해야 한다.
결론적으로 안정성이 필요하다면 , Tim Sort가 맞고
속도가 중시된다면 Dual Quick Sort가 합당한 것 같다.
비교 예시 코드
public static void main(String[] args) {
Random random = new Random();
int[] array1 = new int[ARRAY_LENGTH];
int[] array2 = new int[ARRAY_LENGTH];
// Generate random integer arrays
for (int i = 0; i < ARRAY_LENGTH; i++) {
int randomInt = random.nextInt(RANDOM_RANGE);
array1[i] = randomInt;
array2[i] = randomInt;
}
long startTime, endTime;
// Sort using TimSort
startTime = System.currentTimeMillis();
Arrays.sort(array1);
endTime = System.currentTimeMillis();
System.out.println("TimSort: " + (endTime - startTime) + "ms");
// Sort using Dual-Pivot QuickSort
startTime = System.currentTimeMillis();
Arrays.parallelSort(array2);
endTime = System.currentTimeMillis();
System.out.println("Dual-Pivot QuickSort: " + (endTime - startTime) + "ms");
}결과
- TimSort: 548ms
- 50회 평균: 507ms- Dual-Pivot QuickSort: 135ms
- 50회 평균: 85ms
참조링크
