java array sort
자바의 Array와 Collection 등 다수의 데이터를 다루는 자료형에서는 대부분 간편하게 데이터를 정렬 할 수 있도록 sort기능을 제공하고 있습니다.
버블소트, 카운팅소트, 인서트소트, 퀵소트, 머지소트 등 많은 유명한 정렬 알고리즘들이 있는데요 자바에서는 과연 어떤 알고리즘으로 데이터를 정렬하는지 직접 자바 코드를 열어 확인해보도록 하겠습니다.
(해당 코드는 Java8 기준입니다.)
먼저, 배열을 정렬할때 많이 쓰는 Arrays.sort() 입니다.
// java.util.Arrays
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
...
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
...
내부 구현 코드를 보면 수많은Arrays.sort(...)가 파라미터 타입에 따라 overloading 되어 사용되어 지고 있는것을 보실 수 있습니다. 그 중 대표적으로 int와 Object 타입을 보면 차이가 존재하는것을 확인하실 수 있습니다.
primitive 타입의 경우 Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch 의 DualPibotQuicksort 알고리즘을 이용해 정렬되어 지고 Object type 및 Comparator 구현 객체의 경우 TimSort 알고리즘으로 정렬되고 있습니다.
DualPivotQuicksort
// DualPibotQuicksort
Sorts the specified array into ascending numerical order. Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations. Params: a – the array to be sorted
먼저 DualPibotQuicksort의 내부 구현 코드를 확인해보겠습닏나.
// java.util.DualPivotQuicksort
final class DualPivotQuicksort {
private DualPivotQuicksort() {}
/**
* The maximum number of runs in merge sort.
*/
private static final int MAX_RUN_COUNT = 67;
/**
* The maximum length of run in merge sort.
*/
private static final int MAX_RUN_LENGTH = 33;
/**
* If the length of an array to be sorted is less than this
* constant, Quicksort is used in preference to merge sort.
*/
private static final int QUICKSORT_THRESHOLD = 286;
/**
* If the length of an array to be sorted is less than this
* constant, insertion sort is used in preference to Quicksort.
*/
private static final int INSERTION_SORT_THRESHOLD = 47;
/**
* If the length of a byte array to be sorted is greater than this
* constant, counting sort is used in preference to insertion sort.
*/
private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
/**
* If the length of a short or char array to be sorted is greater
* than this constant, counting sort is used in preference to Quicksort.
*/
private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
...
// java.util.DualPivotQuicksort
static void sort(int[] a, int left, int right,
int[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
/*
* Index run[i] is the start of i-th run
* (ascending or descending sequence).
*/
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) { // ascending
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // descending
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
// Check special cases
// Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
// Determine alternation base for merge
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
// Use or create temporary array b for merging
int[] b; // temp array; alternates with a
int ao, bo; // array offsets from 'left'
int blen = right - left; // space needed for b
if (work == null || workLen < blen || workBase + blen > work.length) {
work = new int[blen];
workBase = 0;
}
if (odd == 0) {
System.arraycopy(a, left, work, workBase, blen);
b = a;
bo = 0;
a = work;
ao = workBase - left;
} else {
b = work;
ao = 0;
bo = workBase - left;
}
// Merging
for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
b[i + bo] = a[p++ + ao];
} else {
b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i + bo] = a[i + ao]
);
run[++last] = right;
}
int[] t = a; a = b; b = t;
int o = ao; ao = bo; bo = o;
}
}
소팅알고리즘을 구현하기 위한 코드들이 있지만, 이번 포스팅의 목적은 어떤 소팅 알고리즘을 사용하는가를 알아보는 것 이기 때문에 위 멤버변수와 주석에 집중을 해보도록 하겠습니다.
/**
* If the length of a byte array to be sorted is greater than this
* constant, counting sort is used in preference to insertion sort.
*/
private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
/**
* If the length of an array to be sorted is less than this
* constant, insertion sort is used in preference to Quicksort.
*/
private static final int INSERTION_SORT_THRESHOLD = 47;
/**
* If the length of an array to be sorted is less than this
* constant, Quicksort is used in preference to merge sort.
*/
private static final int QUICKSORT_THRESHOLD = 286;
/**
* If the length of a short or char array to be sorted is greater
* than this constant, counting sort is used in preference to Quicksort.
*/
private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
정리해 보자면, 소팅알고리즘이 복잡도에 있어서 정렬 대상의 크기에 따라 장단점이 있기 때문에 상황에따라 다른 알고리즘을 통해 정렬을 할 수 있도록 구현되어있습니다.
인서트 소트: 47개 이하퀵 소트: 286개 이하머지 소트: 286개 초과카운팅 소트: 20개 초과 (byte 자료형 sort시) / 3200개 초과 (short, char 자료형 sort시)
정정내용)
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) { // ascending
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // descending
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
- 상수로 지정된
Threashold의 사이즈로만 나누어sort알고리즘이 결정되는것은 아니고,정렬상태를 판별해 알고리즘을 결정해주는 로직이 함께 포함 되어있습니다.
TimSort
// Timsort
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort. Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays. The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array. The implementation was adapted from Tim Peters’s list sort for Python ( TimSort ). It uses techniques from Peter McIlroy’s “Optimistic Sorting and Information Theoretic Complexity”, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.
Object type의 sort 코드를 다시 자세히 보면, userRequest 설정에 따라 LegacyMergeSort 으로 수행 하도록 설정도 가능합니다.
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
userRequest는 '-Djava.util.Arrays.useLegacyMergeSort=true' 자바 환경변수 설정을 통해 사용설정을 할 수 있습니다.
Timsort코드를 보면 DualPibotQuicksort와 비슷한것을 보실 수 있습니다.
class TimSort<T> {
/**
* This is the minimum sized sequence that will be merged. Shorter
* sequences will be lengthened by calling binarySort. If the entire
* array is less than this length, no merges will be performed.
*
* This constant should be a power of two. It was 64 in Tim Peter's C
* implementation, but 32 was empirically determined to work better in
* this implementation. In the unlikely event that you set this constant
* to be a number that's not a power of two, you'll need to change the
* {@link #minRunLength} computation.
*
* If you decrease this constant, you must change the stackLen
* computation in the TimSort constructor, or you risk an
* ArrayOutOfBounds exception. See listsort.txt for a discussion
* of the minimum stack length required as a function of the length
* of the array being sorted and the minimum merge sequence length.
*/
private static final int MIN_MERGE = 32;
/**
* The array being sorted.
*/
private final T[] a;
/**
* The comparator for this sort.
*/
private final Comparator<? super T> c;
/**
* When we get into galloping mode, we stay there until both runs win less
* often than MIN_GALLOP consecutive times.
*/
private static final int MIN_GALLOP = 7;
/**
* This controls when we get *into* galloping mode. It is initialized
* to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for
* random data, and lower for highly structured data.
*/
private int minGallop = MIN_GALLOP;
/**
* Maximum initial size of tmp array, which is used for merging. The array
* can grow to accommodate demand.
*
* Unlike Tim's original C version, we do not allocate this much storage
* when sorting smaller arrays. This change was required for performance.
*/
private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
...
}
TimSort 또한 인서트 소트와 병합 소트를 병합 사용해 최적화하여 사용되어지고 있습니다.
TimSort에 대한 내용은 네이버 D2 기술블로그에서 자세히 설명해주신 내용이 있어 링크를 첨부합니다. (https://d2.naver.com/helloworld/0315536)
Legacy merge sort
// Arrays.java
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
...
// To be removed in a future release.
private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
T[] aux = a.clone();
if (c==null)
mergeSort(aux, a, 0, a.length, 0);
else
mergeSort(aux, a, 0, a.length, 0, c);
}
...
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
Java8 기준으로, legacyMergeSort는 Deprecated된 상태 인것을 주석을 통해 확인하실수 있습니다.
구현 로직은 DualPivotQuickSort와 마찬가지로 MergeSort 내부에 INSERTIONSORT_THRESHOLD를 통해 상황에 따라 효율적인 정렬 알고리즘을 사용 할 수 있도록 선언되어 있는것을 알 수 있습니다.
Java list sort
java에서 또 빼놓을수 없는게 List 인터페이스의 sort 메서드 입니다.
내부 코드를 보면 다음과 같습니다.
// List.java
public interface List<E> extends Collection<E> {
...
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
...
}
우선, List.sort 메서드는 interface에 default method로 선언되어 있는것을 확인 하실 수 있고, 내부적으로는 위에서 알아보았던 Arrays.sort()를 사용하는것을 확인하실 수 있습니다.
마무리
사실 크게 신경 안쓰고 편리하게 사용했던 Java sort 메서드 들이, 내부적으로는 최대한 효율적으로 계산 할 수 있도록 다양한 알고리즘을 통해 구현되어 있음을 확인하는 시간이었습니다.