Data Structure - Sorting ( Several Keys && Radix Sort && External Sort )

MSD vs LSD

모든 예제는 A deck of card에서 시작해 보도록 하겠습니다.

이 카드를 순서대로 정렬하는데 쓰이는 정렬에는 2가지 방법이 있습니다. (Key -> (기준이 되는) 가 여러개)

< MSD sort >

Most-significat-digit-first(MSD) sort입니다.

이는 K1에 대해서 먼저 정렬하고 -> K2에 대해서 정렬을 하는 방법입니다.

 

unordered list (170, 45, 65, 60, 802, 4, 2, 66)

• [045, 065, 060, 004, 002, 066], [170], [802]
• [004, 002], [045], [065, 060, 066], [170], [802]
• 002 004 045 060 065 066 170 802

< LSD sort >

Least-significant-digit-first(LSD) sort입니다.

이는 K2에 해당하는 것 먼저 정렬하고 K1에 대해서 정렬하는 방법입니다. 여기K1을 정렬할 때 무조건 stable한 sort를 사용해야 합니다. LSD가 더 간단하고, 더 적은 오버헤드를 발생시킵니다.

 

unordered list (170, 45, 65, 60, 802, 4, 2, 66)

• 170, 060, 802, 002, 004 045 065 066
• 802, 002, 004, 045, 060, 065, 066, 170
• 002, 004, 045, 060, 065, 066, 170, 802

Radix Sort

MSD와 LSD는 bin sort에서 사용됩니다.

다음과 같은 예시에서, 우리는 bin sort에서 10개의 bins를 사용해서 정렬할 수 있습니다. 아래와 같이 말이죠 

• 이러한 정렬 방식을 radix sort라고 합니다.
• 이러한 radix sort는 radix r에 의해 어떻게 분해될지 결정됩니다.
  • 만약 r 이 10이라면 우리는 10진수로 분해하면 됩니다.
  • 만약 r이 2라면 우리는 2진수로 분해하면 됩니다.



Example

만약 아래와 같은 초기 input이 있었다고 해 봅시다.

그 다음에 first-pass queuest and resulting chain을 그려보면 아래와 같게 됩니다. ( LSD 사용 )

이 과정을 2번만 더 반복해 주면 정렬이 끝나게 됩니다. 매우 간단하죠? 여기서 LSD sort의 예시를 보았는데, LSD sort는 진행 상황을 확인하기 어렵다는 단점이 있습니다. 다만 구현이 매우 쉽게 됩니다. multiple queues를 구현하고 K3에 대해차례대로 넣은 다음에 배열에 넣고 다시 K2, K1에 대해 위 과정을 반복하면 구현이 완료됩니다. 

 

다만 MSD sort는 반드시 끝까지 가지 않아도 중간이 정렬이 완료될 수 있다는 것이 장점이긴합니다. 다만 중간이 데이터를 점검해야 합니다. 이러한 코드를 추가로 작성해 줘야 하기 때문에 구현이 복잡해 지게 됩니다.

 

Summary of Internal Sorting

위에서 살펴 본 것처럼 컴퓨터의 주 메모리에서 수행되는 sorting을 internal sorting이라고 합니다. 이러한 internal sorting의 특징을 다시한 번 정리해 보도록 하겠습니다.

• Insertion sort
  • 부분적으로 정렬되어 있는 배열에서 좋습니다.
  • 작은 크기의 배열에서 유리합니다.
• merge sort
  • best worst-case behaviors즉 최악의 상황에서도 O(nlogn)이 보장된다는 장점이 있습니다.
  • 하지만 이는 heap sort보다 더 많은 storage를 필요로 합니다.
• quick sort
  • quick sort는 평균적으로 가장 좋은 성능을 내는 정렬 알고리즘입니다.
  • 하지만 이는 worst-case ( 정렬 되어 있는 경우 ) O(n^2)입니다 (이러한 경우는 드뭅니다)
• radix sort
  • radix sort는 key의 크기와 r의 값에 따라 시간 복잡도와 계산 량이 변합니다.

이 그래프를 보면 insertion sort는 작은 크기에 대해서는 좋은 것을 볼 수 있습니다. 또한 merge sort는 heap sort보다 평균적으로 좋은 속도를 내지만 더 많은 storage( 저장 공간 ) 즉 Space Complexity가 heap sort보다 높음을 유추할 수 있습니다. 또한 평균적으로 가장 좋은 알고리즘은 quick sort라는 것을 위 그래프가 쭉 커지면서 확인해 볼 수 있습니다.

 

External Sort

외부 정렬은 입력 크기가 매우 커 읽고 쓰기가 오래 걸리는 보조 기억장치에 저장할 수 밖에 없는 상황에서 수행되는 정렬방식 입니다. 통상적으로 주기억장치에서 다룰 수 있는 크기의 데이터를 다루던 기존의 정렬은 내부정렬로 분류합니다.

 

예를 들어, 주기억 장치 용량이 1GB라면, 데이터의 크기가 극단적으로 128GB라고 합시다. 이런 경우에는 주기억 장치에 데이터를 모두 올릴 수는 없는 상황이라 어떤 내부 정렬 알고리즘으로도 직접 정렬할 수는 없어 보조기억장치(HDD, SDD)를 이용해야 합니다.

 

입력을 분할해 주기억 장치가 수용 가능한 만큼의 데이터에 대해 내부 정렬을 수행하고 다시 이를 저장하는 방법을 반복하여, 점진적으로 크기를 늘려나가는 방식을 고려해야 합니다. 내부정렬은 성능이 좋은 퀵정렬을 사용하면 될것입니다. 주기억장치 보조기억장치 엑세스 속도가 극단적으로 차이가 나기 때문에, 최대한 보조기억장치에 접근하는 횟수를 최소화하는 것을 우선사항으로 두어야 합니다.

다음과 같이 주 기억장치의 capablity가 750records할 때 이를 3block으로 잘라서 수행하는 것이 일반적입니다.