카운팅 정렬과 기수 정렬

카운팅 정렬 

배열 A = {4 8 3 2 1 10} 이 있다고 할때

Arr 0 1 2 3 4 5 6 7 8 9 10 <- 배열 인덱스

     0 1 1 1 1 0 0 0 1 0 1

이런식으로 각 숫자가 몇번 나왔는지 체크한다음에 한번더 Arr배열을 순회 하면서 인덱스를 출력하게 되면

1 2 3 4 8 10 이런식으로 정렬이 완료 되게 된다.

카운팅 정렬의 빅오는 O(n+k)이며 k는 원래 배열에 있는 가장 큰수이다.

왜 빅오가 이렇게 나오냐면,

우선 원래 배열 A에 있는 n개의 원소들을 한번씩 방문하면서 Arr배열에 빈도수를 체크해야 한다.

이때 n 시간이 걸리며

또한 원소를 모두 체크한 다음에, 이번에는 Arr배열을 순회하면서 배열의 인덱스를 빈도수 만큼 차례대로 출력해야 한다.

이때 만약에 배열 A가 0,2,0,10000이라고 해보자.

그럼 10000이라는 뜬금없는 큰 수 떄문에 배열의 크기를 1만으로 잡아야 하고 배열의 순회도 0~1만까지 의미없는 순회를 해야 한다.

그래서 카운팅 정렬은 비교기반 정렬의 최소 빅오인 O(nlogn)을 뛰어 넘는 O(N+K)의 시간 복잡도를 갖지만, 추가 공간을 써야 하고, K가 배열의 원소 개수 N에 비해 엄청 큰 경우 이 정렬을 사용하면 안된다. 

->N이 1만이고 K가 1억이라고 해보자. 그럼 이 알고리즘은 그냥 1억짜리 알고리즘이다.

그러니까 N과 K가 비슷하거나 비례할때만 사용하는것이 좋은 알고리즘이다.

기수 정렬 (Radix sort)

기수 정렬은 각 배열의 원소의 1의 자리를 기준으로 정렬을 쭉 해주고 그다음은 10의자리를 기준으로, 그다음 100의자리..

이런식으로 배열 내의 원소중 가장 길이가 긴 원소까지 반복해서 정렬을 해야 하는 알고리즘이다.

무슨 말이냐면

100 4 5 20 30 4000 20 1 3 이런 배열이 있다고 하자. (A)

이 배열에서 기수 정렬을 하려고 할때 먼저 1의 자리를 기준으로 정렬한다.

그럼 첫번째 정렬을 하고 나면 

100 20 30 4000 20 1 3 4 5 이렇게 될 것이다.

이번엔 각 배열 원소의 10의 자리를 기준으로 정렬해보자.

100 4000 1 3 4 5 / 20 20 30 이런식으로 될 것이다.

이번엔 100의 자리를 기준으로 정렬해보자.

4000 1 3 4 5 20 20 30 100 이 될것이고

마지막으로 1000의 자리를 기준으로 정렬해보자.

1 3 4 5 20 20 30 100 4000 이 되고, 정렬이 마무리 된다.

여기서 1의 자리~ 1000의 자리 까지 정렬을 했는데, 1000의 자리 까지 하게 된 이유는 배열의 원소중 4000이 있었기 때문이다. 4000이라는것은 자리수가 4개이므로, 자리수 4개까지 모두 확인해 봐야 한다.

이 알고리즘의 시간 복잡도를 계산해보자.

배열에 N개의 원소가 있고 각 원소를 1,10,100등의 자리수를 기준으로 버킷에 넣었다가 다시 빼서 배열에 넣는 작업을 해야한다.

위에서 봤듯이, 배열의 원소중에 자리수가 가장 큰 원소만큼 반복을 해줘야 한다.(위에서 4000이라는 원소 때문에 4번을 정렬했었다.)

따라서 시간 복잡도는 O(N*K)이다. K는 배열 내의 원소중 가장 큰 숫자의 자리수이다.

INT가 42억정도를 표현할수 있으므로 대략 10자리? 까지 있다고 했을때, O(10*N)이 되기 떄문에 거의 선형 시간이라고 할 수 있다.

하지만 이것도 카운팅 정렬과 마찬가지로 추가적인 메모리 공간이 필요하다.

만약에 배열이 N개의 원소를 갖고 각 원소가 0~N^2-1까지의 범위를 갖는 다면 이 배열을 오름차순으로 O(N)만에 정렬 하는 방법이 있을까?