정렬 알고리즘에 대한 마지막 장입니다. 마지막 장이니 만큼 다른 관점에서 정렬 문제를 바라보는 기회를 가져보기로 합니다.컴퓨터 내부에서 숫자는 0과 1의 상태를 가지는 비트(bit)로 표현됩니다. 8비트가 보여 1바이트가 되고, 2바이트는 하나의 워드가 되며, 요즘 정수형은 4바이트로 구성되니 32비트입니다.
최근까지도 32비트 CPU가 널리 쓰였는데 이는 데이터를 32비트 단위로 처리할 수 있어 효율적이었기 때문입니다.
각설하고 이렇게 컴퓨터 내부에서 비트로 처리되는 데에 착안하여 고안된 정렬 알고리즘이 기수 정렬(Radix Sort)입니다. 여기서 기수(Radix)는 숫자를 표현하는 기본 단위라고 보면 되겠습니다. 수치를 비트 단위로 보면 0과 1 두가지 수로 표현하므로 기수는 2가 되고, 10진법의 경우 기수가 10이 됩니다. 이 외에도 이 장에서 소개하는 정렬법에는 기수가 4가 되기도, 8이 되기도 합니다.
비트 조작을 통한 정렬이라는 건 여러모로 제한 사항이 필연적으로 따라옵니다. 양의 정수형에 대해서만 정렬이 가능하다는 점입니다. 음수도 안되고, 부동소수점 표기를 하는 Float, Double형도 안됩니다. 이런 제한이 있지만 적어도 양의 정수에 대해서만은 매우 효율적인 성능을 보여주는 기수 정렬 알고리즘입니다.
마지막 부분에는 지금까지 배워 온 여러가지 정렬법에 대해서 전체적으로 성능을 서로 비교해 봅니다. 과연 어떤 정렬법이 1등을 했을지 찾아 보시기 바랍니다.
강의 자료
강의 동영상
13.0 기수 정렬(Radix Sort) - 시작 : 이번 장에서 다룰 정렬 알고리즘들은 숫자의 비트 표현을 이용하여 정렬하는 방법으로 매우 독특한 접근법입니다. 숫자형 데이터에만 사용할 수 있다는 제한이 있지만 O(N) 성능의 정렬 알고리즘이 나옵니다.
13.1 분포수 세기(Distribution Counting) : 동일한 키의 중복이 많은 순서 집합을 정렬할 때 유리한 "분포수 세기" 알고리즘에 대해 알아봅니다.
13.2 기수교환 정렬(Radix Exchange Sort)의 개념 : 기수교환 정렬은 퀵 정렬과 유사하게 분할(Partition)을 재귀적으로 반복하여 정렬하는 법입니다. 단 분할의 기준은 비트 값이 0이냐 1이냐 입니다. 기수교환 정렬의 개념에 대해 공부해 봅니다.
13.3 기수교환 정렬의 구현 : 기수교환 정렬은 비트를 다루기 때문에 구현하기가 좀 까다롭습니다. 하지만 비트를 조작하는 기본 함수를 먼저 잘 정의해 두면 해결책이 생깁니다.
13.4 기수교환 정렬의 분석 : 기수교환 정렬은 분할해서 점령(Divide and Conquer)하는 재귀적인 알고리즘으로 O(NlogN)의 성능을 보입니다. 퀵 정렬과 유사하지만 최악의 경우에도 O(NlogN)이라는 점이 틀립니다. 기수교환 정렬의 성능 분석과 양태에 대해 알아봅니다.
13.5 직접기수 정렬(Straight Radix Sort)의 개념 : 직접기수 정렬은 비트를 쪼개어 분포수 세기(Distribution Counting)을 하는 정렬 방법입니다. 그 개념에 대해 알아봅니다.
13.6 직접기수 정렬의 구현 : 직접기수 정렬은 분포수 세기법을 사용하므로 앞서 배운 분포수 세기의 구현을 활용할 수 있습니다. 몇 비트 단위로 구분할 것인가를 정할 수 있게 하면 더 좋습니다.
13.7 직접기수 정렬의 분석 : 직접기수 정렬의 성능은 O(N)으로 독보적입니다. 그리고 단위 비트수를 늘리면 성능은 좋아지지만 필요한 메모리량은 늘어납니다. 그래서 이 정렬법은 공간과 성능의 협상(Trade-off)을 제대로 보여줍니다.
13.8 기수 정렬의 성능 분석 : 이번 장에서 배운 기수교환 정렬과 직접기수 정렬의 성능을 실제로 돌려보며 검증해 봅니다. 두 정렬법 모두 비트 조작을 기반으로 해 입력 자료의 순서에 무관하게 동일한 성능을 보여 줍니다. 직접 기수 정렬의 높은 성능이 돋보입니다.
13.9 정렬 알고리즘 총 정리 : 지금까지 배워 온 여러가지 정렬 알고리즘들의 총 정리를 합니다. 공간복잡도, 시간복잡도, 안정성 등을 평가하고, 실제 난수 집합에 대해 각 정렬법들을 실행시켜 수행 시간을 비교합니다. 우승 후보는 퀵 정렬, 쉘 정렬, 병합 정렬, 직접기수 정렬 입니다.
관련글 |
- C++로 배우는 알고리즘
- 12장 : 쉘 정렬, 병합 정렬 (Shell Sort & Merge Sort)
- 14장 : 기본 검색 알고리즘들
댓글 없음:
댓글 쓰기