[Algorithm] Sorting Algorithm(정렬 알고리즘) - Non Comparison

이전에 정렬 알고리즘에 대한 글을 작성했었는데 이는 상호 원소의 크기를 비교해가며 정렬을 하는 알고리즘이였다.

[Algorithm] Sorting Algorithm(정렬 알고리즘) - Comparison

그리고 비교를 통한 정렬 알고리즘은 시간 복잡도가 최대 O(n log n)~O(n^2)를 가진다는 것을 알 수 있었다.

 

하지만 비교를 통한 정렬 알고리즘이 아닌 특수한 방식을 통한 정렬 알고리즘이 존재하는데,

이는 특정 조건을 충족하면 비교를 통한 알고리즘보다 빠르게 정렬을 할 수 있다는 것이다.

 

 

1. Bucket Sort(버킷 정렬)

버킷 정렬이란, 배열에서 원소가 가지는 크기의 범위를 확인한 후,

그 범위 N개로 나누고 나뉜 범위를 가진 버킷을 생성하여 담는 방식을 통해 정렬하는 방식이다.

 

버킷 정렬에 필요한 특수 조건은 다음과 같다.

1. 정렬할 값은 최소에서 최대까지 일부 범위에 고르게 분포되어야 한다.
2. 범위를 각각 크기가 k인 N개의 동일한 부분으로 나뉠 수 있어야 한다.

 (조건 2와 3은 숫자 값에 적용이 되고 문자 값에는 적용이 안될 수 있다)

 

 

버킷 정렬 절차 :

 

1. 크기가 N인 버킷의 보조 배열을 사용

 

2. 값의 범위는 각각 크기가 k인 N개의 동일한 부분으로 분할

  - 첫 번째 버킷(첫 번째 배열 요소)은 범위의 첫 번째 부분(min ~ min+k-1)의 값을 보유

  - 두 번째 버킷은 범위의 두 번째 부분(min+k에서 min+2k-1까지)의 값을 보유

  - 위의 기준을 기반으로 마지막 버킷까지 값의 범위를 설정

 

3. 나뉘어진 배열과 그 범위에 알맞은 값을 적절한 버킷에 삽입

각 버킷 내에서 값을 정렬된 순서로 유지(예를 들어 버킷 배열의 각 요소는 정렬된 순서로 유지되는 연결 목록일 수 있습니다.)

 

4. 각 버킷의 값을 기존 배열로 이동

 

소요 시간 :

 

  - 3번은 기존 배열을 통과하여 각 값을 적절한 버킷에 넣는 것인데, 값이 적절히 분포되어 있으면 버킷당 하나의 값만 있기 때문에 각 값을 버킷에 삽입하는 시간은 O(1)이고 총 시간은 O(N)이 된다. 

 

  - 그러나 값이 고르게 분포되지 않은 경우 버킷에 값을 삽입하는 시간은 사용되는 데이터 구조에 따라 다르게 되는데, 연결된 목록을 사용하는 경우 모든 값이 동일한 버킷으로 이동하는 경우 3번의 총 시간은 O(n^2 )이 될 수 있다.

 

참조 : https://ko.wikipedia.org/wiki/%EB%B2%84%ED%82%B7_%EC%A0%95%EB%A0%AC

버킷 정렬 - 위키백과, 우리 모두의 백과사전

---

2. Counting Sort(계수 정렬)

계수 정렬은 말 그대로 원소가 배열에서 몇 번 나왔는지 체크하고 원소의 크기 순으로 새로운 배열을 만드는 것이다.

 

계수 정렬은 평균적으로 시간 복잡도가 O(n+k)을 가지는 매우 빠른 알고리즘이다.

하지만 사용할 수 있는 상황이 제한적이기 때문에 일반적으로 사용되고 있지 않다는 것이다.

 

계수 정렬의 특수 조건은 다음과 같다.

1. 메모리를 초과하지 않는 내에서 정렬을 할 수 있다.

 

계수 정렬 절차 :

 

1. 모든 숫자의 개수를 체크하고 그 수의 개수를 배열에 저장한다.

 - [1, 5, 3, 4, 0, 9, 5, 1, 3] 의 배열 -> 최대값 9를 기준으로 빈 배열 생성 후 개수를 저장

 - [1, 2, 0, 2, 1, 2, 0, 0, 0, 1] 순서대로, 0:1개, 1:2개, 3:2개, 4:1개, 5:2개, 9:1개, 나머지는 0개이다.

 

2. 빈 배열에서 사용할 숫자들의 누적합을 구한다.

 - [1, 2, 0, 2, 1, 2, 0, 0, 0, 1] -> [1, 3, 3, 5, 6, 8, 8, 8, 8, 9]

 

3. 빈 배열에 누적합을 바탕으로 값을 삽입해준다.

[ , , , , , , , , ]라는 빈 어레이에 첫 번째 값(0이 1개)부터 삽입 -> 누적합 인덱스 [:1]까지 배열을 채워주면 된다.

[0, , , , , , , , ] -> [0, 1, 1, , , , , , ]  -> [0, 1, 1, 3, 3, , , ,] ...으로 동일한 방식으로 마지막까지 진행

 

 

소요 시간 :

 

  - 계수 정렬은 배열을 탐색하는 시간과 가장 큰 수를 기준으로 빈 배열을 탐색하기 때문에  O(n + k)라는 시간 복잡도를 가진다.

 

  - 여기서 k는 정렬할 수 중 가장 큰 값인데, k가 커질수록 시간도 늘어나고 메모리 또한 많이 필요하기 때문에 제한적인 상황에서만이 계수 정렬이 유리하다고 볼 수 있다.

 

참조 : https://www.geeksforgeeks.org/counting-sort/

Counting Sort - GeeksforGeeks

---

3. Radix Sort(기수 정렬)

기수 정렬은 가장 낮은 자리수부터 비교하여 정렬하는 특수한 개념을 가지고 있다.

비교연산을 하지 않고 0~9의 자리수를 토대로 분류를 하여 정렬을 하기 때문에 정렬 속도는 빠르지만 많은 메모리를 필요로 한다.

 

기수 정렬의 특수 조건은 계수 정렬과 같다.

1. 메모리를 초과하지 않는 내에서 정렬을 할 수 있다.

기수 정렬은 데이터 전체 크기와 그 테이블의 크기만큼 메모리가 더 필요하기 때문이다.

 

기수 정렬 절차 :

 

1. 0~9의 숫자를 담당하는 버켓을 생성한다.

 

2. 모든 데이터에 대하여 가장 낮은 자리수(1의 자리)에 해당하는 버켓에 데이터를 넣는다.

 

3. 0부터 해당 버켓들의 자료를 가져오고 대조한다.

 

4. 2번 과정에 돌아가서 자릿 수를 하나 높여서(ex. 1의 자리 ->10의 자리) 2~4과정을 반복한다.

 

 

소요 시간 :

 

  - 정수의 자릿 수(크기)에 따라 반복되는 횟수가 늘어나기 때문에 시간복잡도는 O(dn)이라고 볼 수 있다.

 

  - 세부적으로 들어가면 O(d*(n+b))로 나타낼 수 있고, b는 k(최대값)의 10의 진수, d는 log b(k)로 나타낼 수 있다.

 

참조 : https://www.geeksforgeeks.org/radix-sort/

Radix Sort - GeeksforGeeks