-
[Dart] List.sort() 제대로 알기카테고리 없음 2022. 3. 14. 11:06
List 타입의 내장 함수 List.sort()를 이용해 정수 리스트 data를 내림차순 정렬하려고 한다.
var data = [4,5,2,1,2,3,45,7,8,9,6,4,23,5,]; data.sort((a, b) => a < b ? 1 : 0); print(data); // print 결과: // [45, 23, 9, 8, 7, 6, 5, 5, 4, 4, 3, 2, 2, 1]여기까지는 문제없다. 그런데, data의 크기를 늘려보면 제대로 정렬이 되지 않는다.
var data = [4,5,2,1,2,3,45,7,8,9,6,4,23,5,4,5,2,1,2,3,45,7,8,9,6,4,23,5,4,5,2,1,2,3,45,7,8,9,6,4,23,5,4,5,2,1,2,3,45,7,8,9,6,4,23,5,4,5,2,1,2,3,45,7,8,9,6,4,23,5,]; data.sort((a, b) => a < b ? 1 : 0); print(data); // print 결과: // [9, 23, 9, 45, 23, 9, 45, 45, 23, 9, 9, 45, 23, 23, 2, 4, 5, 4, 6, 8, 4, 7, 8, 4, 6, 4, 5, 5, 4, 5, 7, 5, 4, 45, 4, 7, 8, 6, 6, 4, 8, 5, 5, 5, 4, 5, 6, 5, 7, 7, 8, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1]정확하게는 리스트의 요소 개수가 33개 이하일 때는 정렬이 제대로 동작하지만, 34개 이상일 때는 제대로 동작하지 않는다.
리스트의 크기만 바뀌었을 뿐인데 왜 결과가 다를까? 그리고 왜 하필이면 요소 개수 34개부터 결과가 달라지는 걸까?
세 줄 요약:
List.sort()는 내부적으로 정의된_INSERTION_SORT_THRESHOLD상수보다 리스트 크기가 작으면 Insertion Sort, 크면 Dual-Pivot Quicksort 알고리즘을 사용해 정렬을 수행한다.- Dual-Pivot Quicksort 알고리즘의 실행 과정에서 사용되는 비교 함수는 두 요소
a,b에 대해a < b인 경우 음수를,a > b인 경우 양수를 반환해야 한다. - 위 예제에서 정렬이 제대로 되지 않은 건
List.sort()에 인자로 넣은 비교 함수가 요구사항을 충족하지 못해서다.
List.sort() 함수의 구현 내용을 알아보자.
List.sort()는 헬퍼 클래스 Sort의 Sort.sort()를 사용하고 있다:
void sort([int compare(E a, E b)]) { Sort.sort(this, compare ?? _compareAny); }Sort.sort() 함수는 다시 클래스 내부에 정의된 _doSort()를 호출한다:
static void sort<E>(List<E> a, int compare(E a, E b)) { _doSort(a, 0, a.length - 1, compare); }_doSort()가 하는 일은 _INSERTION_SORT_THRESHOLD 상수를 기준으로 리스트 크기가 작으면 _insertionSort()를, 크면 _dualPivotQuicksort()호출해 주는 것이다:
static void _doSort<E>( List<E> a, int left, int right, int compare(E a, E b)) { if ((right - left) <= _INSERTION_SORT_THRESHOLD) { _insertionSort(a, left, right, compare); } else { _dualPivotQuicksort(a, left, right, compare); } }_INSERTION_SORT_THRESHOLD 상수는 Sort 클래스 내부에 정적 상수로 정의되어있다:
class Sort { // When a list has less then [:_INSERTION_SORT_THRESHOLD:] elements it will // be sorted by an insertion sort. static const int _INSERTION_SORT_THRESHOLD = 32; ..._insertionSort() 에는 간단한 삽입 정렬 알고리즘이 구현되어있다:
static void _insertionSort<E>( List<E> a, int left, int right, int compare(E a, E b)) { for (int i = left + 1; i <= right; i++) { var el = a[i]; int j = i; while ((j > left) && (compare(a[j - 1], el) > 0)) { a[j] = a[j - 1]; j--; } a[j] = el; } }삽입 정렬 과정에서 비교 작업이 일어나는 곳은 다음 한 곳 뿐이다:
(compare(a[j - 1], el) > 0)
인자로 넣어 준 비교 함수의 결과가 0보다 크면 swap 작업을 하도록 되어 있다. 앞선 예제에서 우리가 정렬 함수에 넣어준 비교 함수는 다음과 같다:(a, b) => a < b ? 1 : 0위의 비교 함수 대로라면 a < b 인 경우에 swap 작업이 일어난다. 결과 리스트는 내림차순 정렬이라는 의도에 알맞게 정렬될 것이다.
문제는 리스트의 길이가 _INSERTION_SORT_THRESHOLD 보다 큰 경우다. 이 경우에는 _dualPivotQuicksort()을 호출한다.
Dual-Pivot Quicksort 알고리즘
기본 아이디어는 두 개의 pivot을 기준으로 리스트를 3개의 구획으로 나누어 정렬하는 것이다.
리스트 L에 대해:
두 개의 기준점 요소 pivot1, pivot2를 결정한다. (
pivot1 <= pivot2이 되도록)- 리스트의 양 끝에 pivot들을 위치시킨다. (
L[0] = pivot1; L[L.length - 1] = pivot2;) - pivot 들을 제외한 리스트의 나머지 부분을 각각 다음 조건을 만족시키는 세 구획으로 나눈다:
1)< pivot1
2)>= pivot1 && <= pivot2
3)> pivot2 - pivot 들을 알맞은 위치로 이동시킨다. 이제 리스트 L 은 두 개의 pivot 을 기준으로 정렬되어있다.
// 한 번의 iteration 이 끝난 후 리스트 L 의 모습: // [ < pivot1 | >= pivot1 && <= pivot2 | > pivot2 ] // pivot1은 첫 번째 구획의 마지막에, pivot2는 두 번째 구획의 마지막에 위치한다. - 동일한 작업을 3. 에서 분류한 세 구획에 대해 반복 수행한다.
실제 코드에서는 통계적으로 적절한 pivot 들을 선택하는 과정이나, pivot1, pivot2의 값이 일치할 경우의 예외처리 등이 추가로 구현되어있다.
실제 코드에서 세 개의 구획을 나누는 작업:
// During the loop we have: // [ | < pivot1 | >= pivot1 && <= pivot2 | unpartitioned | > pivot2 | ] // ^ ^ ^ ^ ^ // left less k great right // for (int k = less; k <= great; k++) { var ak = a[k]; // ak: pivot 을 기준으로 정렬할 현재 요소 int comp_pivot1 = compare(ak, pivot1); if (comp_pivot1 < 0) { // < pivot1 를 만족하는 구획으로 요소를 이동 (생략) // less 포인터 한 칸 앞으로 이동 } else { int comp_pivot2 = compare(ak, pivot2); if (comp_pivot2 > 0) { // > pivot2 를 만족하는 구획으로 요소를 이동 (생략) // great 포인터 한 칸 뒤로 이동 } } // 앞의 두 조건에서 요소의 이동이 일어나지 않았으면, // k 포인터가 다음 loop 에서 한 칸 앞으로 이동하면서 // 자연스럽게 현재 요소는 >= pivot1 && <= pivot2 를 만족하는 구획에 들어가게 된다. }여기서 비교 함수가 사용되는 부분은 다음의 두 부분이다:
if (comp_pivot1 < 0) // compare(ak, pivot1) 의 결과if (comp_pivot2 > 0) // compare(ak, pivot2) 의 결과
비교 함수의 결과가 양수이냐, 음수이냐에 따라 알맞은 작업을 수행한다.우리가 넣었던 비교 함수:
(a, b) => a < b ? 1 : 0 // 비교 결과 | 비교 함수 값 // a < b | 1 // a > b | 0 // a == b | 0비교 함수 값이 음수가 되는 경우가 없다. 즉, 첫 번째 if 문인
if (comp_pivot1 < 0)를 만족하는 경우가 생기지 않는다. pivot1 보다 작은 요소들은 정렬이 될 기회가 주어지지 않는다.a == b 인 경우는?
코드에서
a == b의 경우에는 비교 함수가 0을 반환하는것을 전제로 하고 있다:bool pivots_are_equal = (compare(pivot1, pivot2) == 0); if (pivots_are_equal) { var pivot = pivot1; // pivot1 == pivot2 인 정렬과정 수행 // 구현 방식에 약간의 차이 있지만 기본 알고리즘은 동일 ...그러나 실제 비교 함수는 pivot 을 기준으로 작거나 큰 두 가지 경우만 구분할 수 있으면 충분하다. 예를 들어,
< pivot1를 만족하는 구획에 pivot1 과 값이 동일한 요소가 섞여 들어갔다고 하자. 해당 구획에 재귀적으로 정렬 작업이 이루어 질 것이다. 정렬된 구획의 모든 요소들은 pivot1 보다 작거나 같은 값들일 것이다. 결과적으로 전체 리스트는 알맞게 정렬된다.결론
비교 결과에 따라 비교 함수의 값이 양수 또는 음수를 반환하도록 바꿔야 한다.
(a, b) => a < b ? 1 : 0 // 기존 비교 함수 (a, b) => a < b ? 1 : -1 // 수정된 비교 함수다만 위의 비교 함수는 a == b 의 경우를 개별적으로 구분해내지 못한다. 이 경우 정렬 결과에는 문제가 없으나, 실제 코드에서 전제하고 있는 비교 함수의 동작과는 차이가 있다.
게다가 현재로서는 두 개의 pivot 값이 같은 경우의 분기만 타지 않게 될 뿐이지만, 나중에 문제가 있을 여지가 있다. 따라서 a < b, a > b, a == b 세 가지 경우 모두를 개별적으로 표현할 수 있는 비교 함수를 사용하는것이 바람직하겠다.
int? 형 리스트 내림차순 정렬을 위한 비교 함수 추천:
(a, b) => (b ?? 0) - (a ?? 0) (a, b) => (b ?? 0).compareTo(a ?? 0) (a, b) => -(a ?? 0).compareTo(b ?? 0)참조 링크
What is the algorithm used in sort method in dart?: https://stackoverflow.com/questions/60312504/what-is-the-algorithm-used-in-sort-method-in-dart
dart sdk list.dart 파일 깃헙 링크: https://github.com/dart-lang/sdk/blob/b86c6e0ce93e635e3434935e31fac402bb094705/sdk/lib/collection/list.dart
dart sdk sort.dart 파일 깃헙 링크: https://github.com/dart-lang/sdk/blob/a75ffc89566a1353fb1a0f0c30eb805cc2e8d34c/sdk/lib/internal/sort.dart