DA :: 번지계산에 의한 정렬

Address Calculatioin Sort

키에 주소생성하는 함수를 적용하여 생성된 주소에 키 값을 저장한 다음, 주어진 주소범위를 순서대로 읽어서 정렬된 상태를 얻는 방식을 말한다.
주소생성함수는 키 값에 비례하여 생성되도록 정해야 한다. 즉, 두 키 x와 y에 대해 x<=y이면, f(x)<=f(y)가 성립해야 한다.
주소생성함수는 키 값을 어떤 수로 나누어 정수값을 취하는 것이 보편적인 방식이다.
이때 나누어야 할 수 K는 최대 키 값과 최소 키 값의 차에 파일의 크기, 메모리 사용비율에 따라 결정해야 한다. 만일 하나 이상의 키 값이 동일한 주소로 변환되는 경우에는 키 값이 큰 것이 다음 주소로 이동되어야 한다.

n=9, 최대/최소값 차이 = (74-11), 가용 메모리를 파일 크기의 2배로 사용한다면

K = (최대키 - 최소키) / (2*n) = (74-11) / (2*9) ≒ 4

만일 두 개의 키가 동일한 주소로 변환되는 경우를 가정해 보기로 하자. 아래의 그림에서 주어진 9개의 키 가운데 2개가 동일한 주소인 6번지로 변환된다. 6번지로 변환된 키 값 중에 보다 큰 키값이 27이 다음 주소지인 7번지로 이동하게 되고 7번지에 이미 다른 키가 자리잡고 있다면 또 다시 비교를 하여 보다 큰 키값이 다음 주소로 연속적으로 이동해 가게 된다.

n=9, 최대/최소 값 차이 = (74-11), 가용메모리를 파일크기의 1.2배로 사용한다면

K = (최대키 - 최소키) / (1.2*n) = (74-11) / (1.2*9) ≒ 6

위의 예제에서 가용 메모리를 1.2배로 했을 경우에도 동일한 번지로의 충돌이 생성되지는 않았다. 그러나 이것은 주어진 키 값의 패턴에 따라서 달라질 수 있다.

번지계산에 의한 정렬의 수행시간

메모리가 여유있는 경우, 중복이 일어나지 않으며 정렬시간은 주어진 데이터의 수에 비례하므로 O(n)이 된다. 그러나 메모리가 작거나, 키 값의 분포가 일정치 않은 파일의 경우 정렬시간은 O(n²)로 커지므로 안정적인 정렬방식으로 보기 어렵다.