Linear Sorting Algorithm

오늘도 신나게 알고리즘을 해봅니다. 6006의 Lecture 5의 주제는 Linear Sort Algorithm입니다.

Linear Sort란 정렬을 \(O(n)\)으로 해결하는 것을 뜻합니다. 원본 자료는 스토리가 있습니다. Direct Access Array Sort => Counting Sort => Tuple Sort => Radix Sort순서로 구성되어 있습니다. 이해하긴 참으로 힘들지만 그래도 열심히 노력해봅니다.

 

Direct Access Array Sort

Array를 이용해 정렬을 수행하는 알고리즘. \(O(u) \text{ where u is max key of array}\)

한 Array를 정렬하는 방법 중 단순하게 떠올릴 수 있는 방법은, Array의 모든 아이템의 key값이 정수라 할때, 해당 정수에 대응되는 메모리 주소에 각 아이템을 놓고, 다시 이를 순서대로 traverse하는 것 입니다. 글로 쓰면 이해가 되지 않으니 오늘도 그림으로 이해해 봅니다.

위와 같은 Array가 있다고 가정해 봅시다. 이 친구들을 Merge Sort를 통해 정렬할 수 있습니다.하지만 알다시피 \(O(nlogn)\)시간이 걸립니다. 이를 개선하기 위한 첫 시도로 Direct Access Array sort를 수행해 볼 수 잇습니다. 위 Array를 traverse해서 가장 큰 key값을 찾은 후, 그 값만큼 새로운 array를 만든 후 대응되는 위치에 각 아이템을 넣는 것입니다. 이때 최대 key 값을 \(u\)로 표현하면 \(u\) 크기의 새로운 array를 만들고 대응되는 위치에 넣어주면 됩니다.

그 후 filtering을 통해 None을 떨궈주면 아래와 같이 정렬된 Array를 얻을 수 있습니다.

우리가 알고싶은 것은 Complexity이기 때문에 각 과정의 complexity를 표현해봅시다.

1. 가장 큰 Key 값을 찾는다 => 최초 Array를 처음부터 끝까지 탐색한다. 이때 Array의 크기를 \(n\), 가장 큰 key를 \(u\)라 하자  \(\therefore O(n)\)
2. \(u\)크기의 array를 만든다 => \(O(u)\)
3. 기존 Array의 각 item의 key값을 이용 새로 만든 Array의 각 index에 item을 놓는다 => \(O(n)\)
4. None 을 떨군다 => \(O(u)\)

여기서 볼 수 있듯 \(u\)에 따라 시간 복잡도가 결정됩니다. 그리고 두가지 질문거리가 생깁니다

Direct Access Array Sort의 한계

1. 만약 key 값이 같다면 어떻게 처리하는가?
2. \(O(u)\)를 \(O(n)\)으로 어떻게 만들 것인가?

위 1번의 문제를 해결하기 위해 Counting Sort가 나옵니다

 

Counting Sort

Chain을 이용해 중복 key 문제를 해결하는 알고리즘 \(O(u)\)

앞에서 살펴봤듯 Direct Access Array Sort를 이용하면, Sort를 수행할 수 있었습니다. 그러나 같은 key가 있다면 어떻게 될까요. 머리속으로 상상해보면 같은 Index에 두번 덮어쓰며 기존 array와 길이가 맞지 않을 것 입니다. 그렇다면 각 key가 중복되어도 작동하도록 바꿔줘야 합니다. 어떻게? nested array를 만들어 주면 됩니다.

중복키가 존재하는 것을 볼 수 있습니다. 그럼 max key 값인 300 크기의 nested array를 만들어 줍니다.

그럼 이제 각 item을 대응되는 위치에 넣어줍니다. 이때 기존 순서를 지키면서 넣어줍니다. 즉, 중복되는 key가 있으면 원본 array에서 앞에 위치한 친구를 먼저 놓고 그 뒤에 오는 친구를 그 다음에 넣는 것입니다. 이를 stable하게 sort를 한다고 표현합니다. tuple sort를 할때 중요하게 쓰이니 꼭 알아두도록 합시다. 글로 표현이 잘 안되면 그림으로 표현합니다.

위 그림처럼 원본에 있는 순서를 지켜주는 것이 stable입니다. "5"를 예로 들면 원본 array의 0번째와 2번째에 "5"가 있습니다. 이들을 sort할때 우너본의 order를 지켜주는 것이 핵심입니다. 자 그럼 Direct Access Array Sort에서 가졌던 질문에서 해결된 것과 여전히 남은 것을 나열해 봅시다.

Counting Sort가 가진  장점과 한계

1. 만약 key 값이 같다면 어떻게 처리하는가? -> Chain을 이용해서 해결
2. \(O(u)\)를 \(O(n)\)으로 어떻게 만들 것인가?

그렇습니다. 여전히 \(u\)가 특정 범위 내로 떨어지는지 알 수 없습니다. Tuple Sort를 알면 여기에 대한 힌트를 얻을 수 있습니다

Tuple Sort

각 자리수를 기준으로 stable한 Sort를 수행하는 알고리즘. 자리수를 \(k\), Array의 길이를 \(n\)이라 하면 \(O(kn)\)

tuple sort는 각 자리수별로 sort를 수행해 나가는 방식입니다. 알고리즘 책에서 나오지 않으며 이해를 돕기위해 수업에서 세분화해서 알려준 내용으로 보입니다. Radix sort에서 쓰이는 핵심 방법론이며 방법은 각 자리수 별로 Stable한 정렬을 진행하는 것입니다. 그림으로 이해해봅니다.

편의상 array에 0을 붙여서 자리수를 맞췄습니다. 여기에 각 자리수에 대해 stable한 sort를 진행하면 다음과 같습니다.

이렇게 한 자리수에 대해 정렬을 한 것을 round를 종료했다고 표현하겠습니다. 그럼 총 3번의 round를 진행하면 됩니다. 이제 2번 round를 해봅니다.

그럼 두번째 자릿수를 기준으로 정렬이 수행된 것을 볼 수 있습니다. 항상 기억해야 할 것은 stable 입니다. 즉, 이전에 정렬한 index를 반영해 완전히 새로하는 것이 아닌 같은 key가 나왔을때 이전에 앞에있던 item은 앞에, 뒤에 나왔던 item은 뒤에 붙이게 됩니다. 위 그림을 예로 들면, 300, 005, 005가 있습니다. 이들이 두번째 자리수에 의해 정렬될때 기존 순서를 지키기 때문에 왼쪽에 모여있는 것을 볼 수 있습니다. 마지막 한번 더 수행합시다.

이렇게 수행되는 것을 볼 수 있습니다. complexity를 구해봅니다

각 자리수에 대해 => \(k\)
1. Array길이(n)만큼 비어있는 array를 선언한다 => \(n\)
2. 새로 선언한 array에 해당 자리수를 사용하며 기존 순서를 지키며 각 위치의 array에 기존 아이템을 넣는다 => \(n\)
3. 1차원 배열로 다시 바꾼다 => \(n\)
\(\therefore O(kn)\)

그럼 이제 문제가 약간은 달라진 것을 볼 수 있습니다. 앞에서 질문이 어디까지 해결되어 있는지 다시 살펴보도록 합니다.

Tuple Sort가 가진  장점과 한계

1. 만약 key 값이 같다면 어떻게 처리하는가? -> Chain을 이용해서 해결
2. \(O(u)\)를 \(O(n)\)으로 어떻게 만들 것인가? -> \(O(u)\)문제가 \(O(kn)\)

여기 까지 이렇습니다. 이제 radix sort로 넘어갑니다.

 

Radix Sort

\(u \le n^c\)이면 \(O(n)\)으로 정렬을 수행 가능

자 이제 다 왔습니다. 자릿수를 뜻하는 k가 특정 범위에 들어오면 이 알고리즘은 쉽게 풀립니다. 다시말해, 원본 Array의 max key값인 \(u\)를 합리적인 범위 안에 들어오게 하며, 특정 속성을 가질 때 Radix sort는 \(O(n)\)으로 정렬을 수행합니다. 

이부분에서 저도 제대로 이해하지 못했습니다. 책을 봐도 잘 모르겠습니다. 하지만 결론적으로 원본 Key 값에 n진법 수로 만들어주면 됩니다. 여기서 n은 원본 array의 길이가 됩니다. 그럼 \(u\)는 어떻게 되느냐. \(\lceil log_nu \rceil\)가 됩니다. 예시를 통해 살펴봅시다

이렇게 있다고 한다면 n=6가 됩니다. 이제 6진수로 바꿔봅시다.

바꾸면 위와같이 변하는 것을 볼 수 있습니다. \(log_6300\)=3.18 =>4가 성립하는 것을 알 수 있습니다.

그럼 complexity를 다시 구해보면 아래와 같습니다.

1. 모든 item을 n진수로 바꾼다 => \(O(n)\)
2. 해당 n진수에 대해 Counting sort(tuple sort)를 수행한다 => \(O(n*log_nu)\)

이렇게 됩니다. 따라서 전체 complexity는 \(O(n*log_nu)\)가 됩니다. 여기서 한단계만 더 나아가면 증명이 끝납니다. \(u\)가 어떤 조건일떄 알고리즘이 \(O(n)\)이 될까요. 바로 \(u \le n^c\) 일때 입니다. 여기서 c는 상수입니다. 간단하게 \(u=n^c\)를 대입하면 다음과 같습니다.

 \(O(n*log_nu)\)

\(u=n^c\)이고 이것을 대입하면

\(O(cn) = O(n)\) 이 성립합니다.

 

증명 중간중간 과정에 구멍이 숭숭 뚫려버렸지만 이와 같이 \(u\)가 \(n^c\)의 관계에 있을때, Radix sort는 linear time이 됩니다.

 

열심히 하는 것보다 중요한 것은 잘하는 것이다
그러나 잘하기 위해서는 열심히 해야 한다
코드아키택트