차이점

이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.

차이 보기로 연결

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

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2012-10-04 09:10 | 작성자 lifthrasiir