이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
정렬알고리즘 [2012-08-12 04:22] lifthrasiir 새로 만듦 |
정렬알고리즘 [2012-10-04 09:10] (현재) lifthrasiir 실수로 뒤집어 써 놓은 부분 고침 ... |
||
---|---|---|---|
줄 41: | 줄 41: | ||
전통적인 정렬 알고리즘은 비교 숫자를 최적화하는데 집중한다. 하지만 비교가 충분히 싸다면 비교 숫자보다 복사 숫자, 즉 메모리 상에서 원소가 옮겨다니는 시간이 더 중요할 수 있다. 이 때문에 비교 수와는 별개로 복사 수를 세는 경우도 있다. | 전통적인 정렬 알고리즘은 비교 숫자를 최적화하는데 집중한다. 하지만 비교가 충분히 싸다면 비교 숫자보다 복사 숫자, 즉 메모리 상에서 원소가 옮겨다니는 시간이 더 중요할 수 있다. 이 때문에 비교 수와는 별개로 복사 수를 세는 경우도 있다. | ||
- | 대부분의 기준에서 매우 최적에 속하는 [[병합정렬]]이 드물게 최적이 아닌 분류로, 병합정렬은 제자리 정렬을 하면 성능이 나빠지기 때문에 원소를 복사하는 숫자로 따지면 불리할 수 밖에 없다. 반면 [[퀵정렬]]에서 pivot을 구하는데 쓰는 보편적인 알고리즘은 복사 수를 줄이는 데 최적화되어 있다. 그래서 [[JDK]]의 경우 ''Comparable'' 인터페이스가 구현되어 있는, 즉 비교가 느릴 가능성이 큰 경우에는 퀵정렬의 변종을 사용하고, 숫자 같이 비교가 값싼 경우에는 병합정렬의 변종인 [[팀정렬]]을 사용한다. | + | 대부분의 기준에서 매우 최적에 속하는 [[병합정렬]]이 드물게 최적이 아닌 분류로, 병합정렬은 제자리 정렬을 하면 성능이 나빠지기 때문에 원소를 복사하는 숫자로 따지면 불리할 수 밖에 없다. 반면 [[퀵정렬]]에서 pivot을 구하는데 쓰는 보편적인 알고리즘은 복사 수를 줄이는 데 최적화되어 있다. 그래서 [[JDK]]의 경우 ''Comparable'' 인터페이스가 구현되어 있는, 즉 비교가 느릴 가능성이 큰 경우에만 병합정렬의 일종인 [[팀정렬]]을 사용하고, 숫자 같이 비교가 값싼 경우에는 퀵정렬의 변종을 사용한다. |
==== 공간복잡도 ==== | ==== 공간복잡도 ==== |