'병합정렬'에 해당되는 글 1건

  1. 2008.03.31 java.util.Arrays의 정렬 알고리즘 (2)
2008.03.31 20:04
Arrays는 7 미만의 작은 배열의 경우 insertion sort를 하고,
integer 등의 정수는 merge sort를
float 등의 부동 소수점 수는 quick sort를 합니다.

시작은 Collections.sort(List<T> lis즘t, Comparator<? supter T>) 에서 하겠습니다.
Collections class의 소스코드를 보시면
사용자 삽입 이미지
Arrays.sort()를 호출하고 있습니다.
이제 그럼 Arrays.sort로 가보겠습니다.
Arrays class의 api를 보시면, byte, char, double, float, int, long,  short, Object 그리고 Generic T의 배열에 대해 Sort method를 정의해 놓은 것을 확인하실 수 있습니다.

우선 위에서 사용된 Arrays.sort(Object[], Comparator)를 먼저 살펴보겠습니다.
이 method의 API를 읽어보면,
정렬의 결과가 stable하며, 수정된 merge sort를 사용한다고 되어 있습니다.
작은 쪽 리스트의 가장 큰 값이 큰 쪽 리스트의 가장 작은 값보다 작으면 merge를 생략하도록 수정되어 있다고 나와 있습니다.그리고 merge sort가 그렇듯, n*log(n) performance를 보장한다고 되어 있습니다.

자 그럼 ArrayList.sort(Object[], Comparator) method의 source code를 살펴보겠습니다.
사용자 삽입 이미지
바로 mergeSort를 하고 있습니다. 자 그럼 바로 mergeSort(Object[] src, Object[] dest, int low, int high, int off) 의 declaration이 있는 곳으로 가겠습니다.
사용자 삽입 이미지
흠. 이제 재밌는 부분이 나왔네요.
작은 배열은 Insertion Sort를 하게 되어 있습니다.
INSERTIONSORT_THRESHOLD 값은 static final int 타입으로 7이 선언되어 있습니다.
왜 7인지는 잘 모르겠습니다. 어쨌거나 7보다 작으면 Insertino Sort를 하게 되어 있습니다.

제일 먼저 정렬할 배열의 크기를 확인하고, 충분히 작으면 Insertion Sort를 하고 return; 이 호출됩니다. 그렇지 않을 경우, Merge Sort를 하게 되며, 배열을 반으로 나누어 Merge Sort를 하게 됩니다.
그런데 잘 사용하지 않은 operator가 나왔습니다.
>>>  이 operator를 뭘하는 걸까요. 찾아보니 unsigned bit shift right이네요. 응? 그게 모지..
java spec을 읽어봐야 할 것 같아서 패스하겠습니다.
일단 floor( the greatest integer less thatn or equal to )의 의미로 알고 넘어가겠습니다.

recursive 하게 mergeSort를 호출한다음,
merge하거나 그냥 Destination Array에 복사하거나 입니다.

그런데 Arrays class에는 정말 재밌어 보이는 method들이 많네요.
천천히 계속 살펴봐야겠습니다.
이런 소스가 그냥 공개되어 있다는 것이 신기할 뿐입니다. ^^:;;;
Posted by 나야

댓글을 달아 주세요

  1. 에이쥬어 2009.01.28 18:18  댓글주소  수정/삭제  댓글쓰기

    컴퓨터에서 정수는 2진수로 표현되죠. 한 2진수를 오른쪽으로 한 칸 밀고 맨 오른쪽 자리를 버린다는 것은 곧 2로 나누는 것을 뜻합니다. 나누기 연산보다 시프트가 더 빠르기 때문에 이용됩니다.

  2. 나야 2009.01.29 08:31 신고  댓글주소  수정/삭제  댓글쓰기

    아 그렇군요. 감사합니다. ^^