출처 -> http://sweeper.egloos.com/921858
정렬 알고리즘 정리
1. 비교 정렬 리스트
아래 테이블에서 n은 개체수이고 k는 키들의 평균적인 길이이다. 클릭해서
보도록...
연결 리스트를 머지 소트할 경우는 메모리 차지가 O(1)로 줄어들게 된다.
2. !비교 정렬 리스트
n = 개체수
k = 각 key의 크기
s = 구현에 사용된 chunk 크기
비교 정렬이 아닌 알고리즘들은
O(n(log n))의 lower bound 제한에 걸리지 않는다. 즉, O(n(log n))보다 더 좋은 성능을 낼 수도 있다. 하지만 기수
정렬(Radix sort)을 예로 설명하면 키의 크기가 제한적일 때 성능이 좋아지는 등, 여러 가지 제약이
있다.
3. Memory usage patterns and index
sorting
정렬해야 될 데이터가 물리 메모리의 한계를 넘어서면 디스크 스왑을 사용해야 하는데, 이 경우 RAM
영역에서 효과적으로 정렬되던 방식들이 사실상 비현실적일 정도로 성능을 내지 못할 수 있다. 이 상황에서는 비교 횟수 보다 swap 등 데이터의
이동 회수가 훨씬 중요하게 여겨져 복사나 값 교환 작업이 알고리즘의 성능을 좌우하게 된다.
예를 들어 가장 인기있는 퀵 소트
알고리즘은 RAM 영역에서 상당히 만족스러운 성능을 제공하지만 리스트의 일부를 복사하는 순환 방식 때문에 디스크 상에서는 상당히 비효율적인
알고리즘이 된다. 고로 더 많은 비교 회수를 요구하더라고 좀 더 적합한 알고리즘을 사용해야 한다.
위 같은 상황을 극복할 수 있는
방법을 살펴보자.
(관계형 데이터베이스에서와 같은) 복합 레코드들을 key 값으로 정렬하듯이, 리스트 자체를 정렬하지 말고 인덱스를
만들어 그 인덱스로 정렬을 하는 방법이 있다. 인덱스는 전체 리스트보다 훨씬 작으므로 전체 물리 메모리에 못 들어갈 데이터들을 RAM 영역에서
정렬할 수 있으며 효과적으로 디스크 스와핑을 없앨 수 있다. 이 과정은 종종 "tag sort"라 불리기도 한다.
메모리 한계를
극복하는 또 다른 방법은 전체적인 성능 향상을 위해 두 알고리즘의 강점을 조합하는 것이다. 예를 들어 배열은 RAM 영역에 쉽게 포함될 수 있는
크기 단위로 나뉘어 질 수 있을 것이고 나뉘어진 분할 리스트들을 각기 퀵 소트나 힙 소트로 정렬한다. 그리고 정렬된 분할 리스트들을 머지 소트로
병합하는 것이다. 이렇게 하면 머지 소트만 하는 것보다 성능이 뛰어나며 퀵 소트만 하는 것 보다 작은 물리 메모리를 필요로 하게 된다.
