Understanding Special Alignment in Computer Algorithms (2/3)

Contents

1️⃣ 기수 정렬 (radix sort)
2️⃣ 계수 정렬 (counting sort)
3️⃣ 버킷 정렬 (bucket sort)

---

1️⃣ 기수 정렬 (radix sort)

기수 정렬(radix sort)의 개념

• **기수 정렬(Radix Sort)**은 정수나 문자열을 자리수별로 비교하여 정렬하는 알고리즘이다.

• 주어진 원소들을 가장 낮은 자릿수부터 차례대로 큐를 이용하여 재배열하고, 자릿수별로 정렬을 반복함으로써 전체 원소를 정렬한다.

기수 정렬의 적용 조건:

• 원소들이 모두 상수 k개 이하의 자릿수를 가진 자연수 또는 알파벳 등 문자일 경우:

  • 기수 정렬은 주어진 원소들이 특정한 자릿수를 가지는 경우에 유효하다.

  • 예를 들어, 자릿수가 3자리 이하인 정수들이나 일정한 길이의 문자열 정렬에 적합하다.

예제 설명:

• 첫 번째 자리(First digit): 4

• 두 번째 자리: 5

• 세 번째 자리: 3

• 네 번째 자리: 1

이렇게 자릿수를 기준으로 각 자리의 값을 비교하면서 정렬을 수행하는 것이 기수 정렬의 방식이다.

기수 정렬의 작동 예시

기수 정렬은 각 자릿수를 차례로 비교하여 재배열하는 방식으로, 낮은 자릿수부터 높은 자릿수까지 정렬을 수행하여 최종적으로 전체 원소가 정렬된다. 이미지를 자세히 살펴보자.

이미지 설명:

1. 첫 번째 자릿수로 재배열:

   • 가장 낮은 자릿수(1의 자리) 기준으로 정렬을 수행한다.

   • 결과적으로 1의 자릿수가 작은 순서대로 재배열되었다.

2. 두 번째 자릿수로 재배열:

   • 두 번째 자릿수(10의 자리)를 기준으로 재배열한다.

   • 첫 번째 자릿수의 순서를 유지하며, 두 번째 자릿수가 작은 순서대로 재정렬되었다.

3. 세 번째 자릿수로 재배열:

   • 세 번째 자릿수(100의 자리)를 기준으로 정렬한다.

   • 앞서 정렬된 순서를 유지하면서 100의 자릿수가 작은 순서대로 재배열되었다.

4. 네 번째 자릿수로 재배열:

   • 네 번째 자릿수(1000의 자리)를 기준으로 정렬한다.

   • 모든 자릿수를 기준으로 정렬이 완료되었기 때문에 최종적으로 정렬된 상태가 된다.

기수 정렬의 의사코드(pseudocode)

의사코드 설명:

1. radixSort(A[], n, k):

   • A[]: 정렬할 배열을 뜻한다.

   • n: 배열의 크기, 즉 원소의 개수이다.

   • k: 각 원소가 가질 수 있는 최대 자릿수를 뜻한다.

2. 알고리즘 설명:

   • 첫 번째 조건:

     • 원소들이 최대 k 자릿수 이하인 배열 A[0...n-1]을 정렬한다.

   • 두 번째 조건:

     • 가장 낮은 자릿수를 1번째 자릿수로 간주하고, 이 자릿수부터 시작하여 정렬을 진행한다.

3. for 루프:

   • for i = 1 to k

     • i번째 자릿수에 대해 배열 A[0...n-1]을 정렬한다.

     • 이때 안정성을 유지하면서 정렬해야 한다.

     • 안정성(Stability)이란 동일한 자릿수를 가진 원소들이 정렬 후에도 기존 순서를 유지하는 것을 의미한다. 이를 통해 각 자릿수의 정렬이 이전 자릿수의 정렬에 영향을 미치지 않는다.

기수 정렬에서 각 자리수의 정렬

기수 정렬은 일반 정렬 알고리즘보다 효율적으로 동작할 수 있으며, 각 자릿수를 기준으로 데이터를 재배열하여 전체 배열을 정렬한다. 각 자릿수 정렬 시 큐를 사용함으로써 안정성을 유지하고 복잡도를 줄이는 것이 핵심이다.

내용 요약:

1. 복잡도 분석:

   • 알고리즘 1-1에서 첫 번째 자릿수를 정렬할 때, 일반적인 정렬 알고리즘을 사용하면 시간 복잡도는 O(n log n) 이상이 필요하다.

   • 그러나 기수 정렬은 각 자릿수를 기준으로 큐(Queue) 같은 데이터 구조를 사용하여 재배열함으로써, 복잡도를 줄일 수 있게된다.

2. 각 자릿수의 정렬 과정:

   • 이미지의 예시는 각 자릿수의 값을 기준으로 데이터가 어떻게 재배열되는지 보여주고 있다.

   • 예를 들어, 1의 자릿수를 기준으로 데이터를 분류하고, 정렬이 완료되면 10의 자릿수, 100의 자릿수, 그리고 그 이상의 자릿수를 순서대로 정렬한다.

   • 데이터 삽입과 데이터 출력의 과정을 반복하면서 각 자릿수의 값에 따라 데이터가 큐 구조에 저장되고 다시 출력된다.

3. 큐(Queue)를 이용한 정렬:

   • 각 자릿수의 값을 기준으로 데이터가 재배열될 때, 큐를 이용하여 정렬을 수행한다.

   • 큐의 FIFO(First-In, First-Out) 속성 덕분에 각 자릿수 정렬이 안정성을 유지할 수 있다.

4. 결과:

   • 모든 자릿수에 대해 정렬이 끝난 후, 최종적으로 정렬된 데이터는 [03, 16, 18, 23, 24, 77, 80, 88]과 같은 순서로 완성되었다.

   • 이미지에서는 데이터의 최종 정렬 결과를 아래쪽에 표시하여, 각 자릿수별 정렬이 전체 정렬로 어떻게 이어지는지 보여주고 있다.

기수 정렬의 시간 복잡도

1. 각 자릿수의 정렬:

   • 알고리즘 4-20에서 각 자릿수를 큐를 이용하여 재배열한다.

   • 각 자릿수마다 원소들을 정렬하는 데 걸리는 시간 복잡도는 O(n)이다.

     • n은 정렬할 배열의 원소 개수이다.

2. 전체 시간 복잡도:

   • 배열의 모든 자릿수(k개)에 대해 정렬을 수행해야 한다.

   • 따라서 전체 시간 복잡도는 자릿수(k)와 배열의 원소 개수(n)를 곱한 O(kn)이 된다.

요약:

• 각 자릿수의 시간 복잡도: O(n)

• 전체 정렬의 시간 복잡도: O(kn), 여기서 k는 자릿수의 개수, n은 배열의 원소 개수이다.

---

2️⃣ 계수 정렬 (counting sort)

계수 정렬(counting sort)의 개념

• **계수 정렬(Counting Sort)**은 원소들의 값의 빈도수를 세어 이를 기반으로 정렬하는 알고리즘이다.

• 배열의 원소들을 훑어보면서 0부터 k까지 각 값이 몇 번 나타나는지 세고, 이 빈도수를 이용하여 정렬된 배열을 생성하게 된다.

• k 값의 예시로는 2n 이하의 자연수, 상수 1000을 넘지 않는 음이 아닌 정수 등

• 계수 정렬은 값의 범위가 제한된 경우에 효과적인 정렬 알고리즘이다.

• 각 값의 빈도수를 세어 정렬을 수행하므로, 원소의 값이 특정 범위에 속하는 경우 O(n + k)의 시간 복잡도를 가지게 된다.

계수 정렬의 작동 예시

위 예시는 계수 정렬이 값의 빈도수를 세고, 누적합을 통해 정렬 위치를 계산한 후, 최종적으로 정렬된 배열을 생성하는 과정을 시각적으로 보여주고 있다.

1. 입력 배열:

   • 입력 배열은 A[0...14]로, 15개의 원소로 구성되어 있다.

   • 각 원소는 0부터 12 사이의 값을 가질 수 있다.

2. 카운팅 배열 생성 (b 단계):

   • **카운팅 배열 C[0...12]**를 생성하여, 각 값이 몇 번 나타났는지를 세어 저장한다.

   • 예시에서는 C[i]에 i값이 나타난 빈도수가 저장된다.

     • 예: C[0] = 1, C[2] = 4 (즉, 0은 1번, 2는 4번 나타났음을 의미한다).

3. 누적합 계산 (c 단계):

   • 카운팅 배열 C[]의 값을 누적합으로 바꾼다.

   • 누적합을 통해 특정 값이 정렬된 배열에서 어느 위치에 배치될지 알 수 있다.

     • 예: C[2] = 4는 값 2가 정렬된 배열에서 4번째 위치까지 나타난다는 것을 의미한다.

4. 정렬된 배열 생성 (d 단계):

   • B[] 배열을 생성하여 정렬된 값을 저장한다.

   • A 배열의 값을 뒤에서부터 확인하며, C[] 배열의 값을 참고하여 B[]에 값을 배치한다.

     • 예: A 배열의 마지막 원소 0은 B 배열의 0번째 위치에 배치되고, C[0]의 값은 1에서 0으로 감소하게 된다.

   • 이 과정을 반복하여 B 배열에 정렬된 값들이 저장된다.

정렬 과정 요약:

• (b) 단계에서 빈도수를 세어 C 배열에 저장하고,

• (c) 단계에서 누적합을 계산하여 C 배열의 값을 업데이트한 후,

• (d) 단계에서 B 배열에 정렬된 값을 저장함으로써 전체 정렬이 완료된다.

결과:

최종적으로, B 배열에는 [0, 1, 2, 2, 5, 6, 7, 8, 8, 8, 10, 10, 11, 11, 12]와 같이 정렬된 값들이 저장된다.

---

계수 정렬의 의사코드

1. 초기화: for i ← 0 to k: // C[i] ← 0

   • C[] 배열을 0으로 초기화하였다.

   • C[i]는 값 i가 몇 번 나타나는지 기록하는 배열이다.

2. 값의 빈도수 계산: for j ← 0 to n-1; // C[A[j]]++

   • 입력 배열 A[0...n-1]의 각 원소값을 확인하며, 해당 값의 빈도수를 C[] 배열에 저장한다.

   • 예를 들어, A 배열에 값 2가 3번 나타난다면 C[2]의 값은 3이 된다.

3. 누적합 계산: for i ← 1 to k: // C[i] ← C[i] + C[i-1]

   • C[] 배열의 값을 누적합으로 변환한다.

   • C[i]는 i 값이 정렬된 배열에서 몇 번째 위치까지 나타나는지를 나타낸다.

   • 누적합을 통해 i 값이 B 배열의 어느 위치에 배치될지를 알 수 있다.

4. 정렬된 배열 생성

   • 입력 배열 A를 뒤에서부터 순회하며, C[] 배열의 값을 참고하여 정렬된 배열 B에 값을 배치한다.

   • 예: A[j]가 2라면, C[2]의 값이 4일 때 B[3] 위치에 2를 배치하고, C[2]의 값을 1 감소시킨다.

5. 배열 B에 값 저장 및 인덱스 감소:

   • A[j]의 값을 B[C[A[j]]-1]에 저장하고, C[A[j]]의 값을 감소시킨다.

   • 이는 A 배열의 값을 B 배열에 올바른 순서로 배치하기 위한 과정이다.

6. 정렬된 배열 B 반환:

   • 최종적으로 정렬된 배열 B를 반환한다.

---

계수 정렬의 각 배열의 관계

이미지는 **계수 정렬(Counting Sort)**의 카운팅 배열(C[])과 결과 배열(B[])의 관계를 시각적으로 설명하고 있다.

이미지 설명:

1. 입력 배열 A[0...n-1]:

   • A 배열은 정렬할 원소들을 담고 있는 입력 배열이다.

   • 배열의 각 요소는 y와 같은 특정 값으로 표현된다.

2. 카운팅 배열 C[0...k]:

   • C 배열은 A 배열의 각 값이 몇 번 나타나는지 빈도수를 저장한 배열이다.

   • 예시에서 y의 빈도수는 q로 표시되어 있다.

   • 이 배열의 값을 누적합으로 변환하면 A 배열의 원소들이 B 배열에 배치될 위치를 계산할 수 있다.

3. 결과 배열 B[0...n-1]:

   • B 배열은 정렬된 결과를 담는 배열이다.

   • 예시에서는 x, y, z와 같은 값들이 정렬된 순서로 나타나 있다.

   • 예를 들어, y가 3번 나타났다면 B 배열의 연속된 세 칸에 y가 차례로 저장되게 된다.

---

계수 정렬의 시간 복잡도

요약:

• 각 단계의 시간 복잡도:

  • 1단계와 3단계: Θ(k)

  • 2단계와 4단계: Θ(n)

• 전체 시간 복잡도: Θ(n + k)

• 만약 k가 O(n)일 때, 전체 시간 복잡도는 Θ(n)

• 알고리즘 2-1의 1단계와 3단계:

  • 1단계와 3단계에서 사용하는 for 루프의 시간 복잡도는 각각 Θ(k).

  • 여기서 k는 카운팅 배열 C[]의 크기, 즉 입력 배열 A[]의 원소들이 가질 수 있는 최대 값.

  • 1단계: C[] 배열을 0으로 초기화하는 작업이므로 Θ(k) 시간.

  • 3단계: C[] 배열의 값을 누적합으로 변환하는 작업이므로 Θ(k) 시간.

• 알고리즘 2-1의 2단계와 4단계:

  • 2단계와 4단계에서 사용하는 for 루프의 시간 복잡도는 각각 Θ(n)입니다.

  • 여기서 n은 입력 배열 A[]의 크기, 즉 배열에 있는 원소의 개수입니다.

  • 2단계: A[] 배열의 각 원소를 순회하며 C[] 배열에 빈도수를 기록하는 작업이므로 Θ(n) 시간.

  • 4단계: A[] 배열을 뒤에서부터 순회하며 정렬된 배열 B[]에 값을 배치하는 작업이므로 Θ(n) 시간.

• 전체 시간 복잡도:

  • 전체 시간 복잡도는 각 단계의 시간 복잡도의 합으로 계산된다.

  • 1단계 (Θ(k)) + 2단계 (Θ(n)) + 3단계 (Θ(k)) + 4단계 (Θ(n)) = Θ(n + k)

  • 만약 k가 O(n)이라고 가정할 수 있다면, 전체 시간 복잡도는 Θ(n)이 된다.

---

3️⃣ 버킷 정렬 (bucket sort)

버킷 정렬은 원소들이 균등하게 분포되어 있을 때 최적의 성능을 발휘하는 정렬 알고리즘이다. 그래프에서 보여지는 것처럼 값들이 고르게 분포되어 있는 경우, 각 버킷에 원소들이 균일하게 나뉘어지며, 이를 통해 빠른 정렬을 수행할 수 있게된다.

버킷 정렬의 조건

정렬하고자 하는 원소들이 균등 분포를 이룰 때:

• 버킷 정렬은 원소들이 특정 범위 내에서 균등하게 분포되어 있을 때 가장 효율적으로 동작한다.

• 균등 분포(Uniform Distribution)란 원소들이 일정한 범위 내에서 고르게 퍼져 있는 상태를 의미한다.

---

버킷 정렬의 작동 과정

1. 입력 배열 준비:

   • 입력 배열 A[0...14]는 값의 범위가 0에서 1 사이로 균등 분포(Uniform Distribution)를 이루고 있다.

   • 예시에서 A 배열의 원소들은 [0.38, 0.94, 0.48, 0.73, ... , 0.02]와 같이 소수 값을 가진다.

2. 버킷 번호 계산:

   • 각 원소를 버킷에 배치하기 위해, 각 원소의 값에 15를 곱하여 정수부만 취한다.

   • 예: A[0] = 0.38일 때, 15 * 0.38 = 5.7이므로, 정수부는 5이다. 따라서, A[0]은 5번 버킷에 배치된다.

   • 이 과정을 통해 A 배열의 각 원소가 어느 버킷에 들어갈지 결정된다.

   • **(b 단계)**에서는 각 원소가 대응되는 버킷의 번호를 나타내고 있다.

3. 버킷 리스트에 원소 삽입:

   • 각 원소를 계산된 버킷 번호에 따라 **버킷 리스트 B**에 삽입한다.

   • 예: 0.02는 0번 버킷에, 0.38은 5번 버킷에, 0.48은 7번 버킷에 삽입된다.

4. 각 버킷 정렬:

   • 버킷 리스트의 각 버킷 내의 원소들을 삽입 정렬과 같은 간단한 정렬 알고리즘을 이용하여 정렬한다.

   • 예: 5번 버킷에 있는 값 0.38과 0.43은 삽입 정렬을 통해 정렬된 상태로 유지된다.

   • 이 단계에서 **(d)**의 B 배열과 같이 각 버킷에 속한 값들이 정렬된다.

5. 정렬된 원소를 차례로 A 배열에 복사:

   • 각 버킷의 정렬된 원소들을 차례로 꺼내어 최종적으로 A 배열에 배치한다.

   • 예: 0번 버킷의 값 0.02, 1번 버킷의 값 0.10 등이 차례로 A 배열에 복사된다.

   • 최종적으로 (e 단계)의 A 배열에 정렬된 값들이 저장된다.

---

버킷 정렬의 의사코드

주요 포인트:

• B 배열은 리스트로 구성된 배열로, 각 리스트가 하나의 버킷을 의미한다.

• 입력 배열 A의 값은 [0, 1] 범위의 균등 분포된 실수이기 때문에, 이 값들을 적절한 버킷에 나누어 삽입한 후 정렬하게 된다.

• 각 버킷의 내부를 정렬한 후, 정렬된 원소들을 A 배열에 차례대로 복사함으로써 최종 정렬된 배열을 완성할 수 있다.

각 단계 설명:

1. 버킷에 원소 삽입:

   • 입력 배열 A의 각 원소 A[i]를 해당하는 버킷 B[nA[i]]에 삽입한다.

   • 예를 들어, 원소 A[i]의 값이 0.38이라면 n을 15로 가정할 때, B[15 * 0.38] = B[5]에 삽입된다.

   • 여기서 B는 n개의 버킷을 갖는 리스트 배열이다.

2. 각 버킷 내부 정렬:

   • 각 버킷 B[i]의 원소들을 정렬한다.

   • 버킷 내 원소의 개수가 적기 때문에, 삽입 정렬(Insertion Sort)과 같은 간단한 정렬 알고리즘을 사용해도 충분히 효율적이다.

3. 정렬된 원소들을 배열 A로 복사:

   • 정렬된 각 버킷 B[i]의 원소들을 차례대로 배열 A에 복사하여 최종 정렬된 배열을 만든다.

   • 복사할 때는 버킷의 순서를 유지하면서, 모든 버킷의 원소들을 차례대로 배열 A에 추가한다.

---

버킷 정렬의 시간 복잡도 1

요약:

• 각 원소의 버킷 삽입: Θ(1)

• 전체 원소의 버킷 삽입: Θ(n)

• 버킷에 원소 삽입:

  • 알고리즘의 2단계에서, 각 원소를 특정 버킷 B[i]에 삽입하는 작업의 시간 복잡도는 Θ(1)이다.

  • 각 원소를 버킷에 배치하는 것은 단순한 계산(n * A[i])을 통해 수행되므로, 각 삽입 작업은 O(1)의 시간이 소요된다.

  • 예를 들어, A[i]가 0.38이라면, B[5] 버킷에 삽입하는 것은 한 번의 계산으로 이루어지기 때문에 Θ(1) 시간 복잡도를 가진다.

• 전체 원소의 버킷 삽입:

  • 총 n개의 원소를 각기 다른 버킷에 삽입하는 작업의 전체 시간 복잡도는 Θ(n)이다.

  • n개의 원소 각각에 대해 Θ(1)의 작업을 수행하므로, 전체 복잡도는 n * Θ(1) = Θ(n)이 된다.

버킷 정렬의 시간 복잡도 2

이 설명은 버킷 정렬이 n개의 균등 분포된 원소들을 가진 배열에 대해, 각 버킷에서의 정렬 시간 복잡도가 Θ(1)임을 보이고, 이를 기반으로 전체 정렬의 시간 복잡도가 Θ(n)이 된다는 것을 수학적으로 증명하고 있다. 요약은 아래를 살펴보자

요약:

• 각 버킷에 원소가 들어갈 확률: p = 1/n

• 각 버킷의 삽입 정렬 시간 복잡도: Θ(1)

• 전체 버킷의 시간 복잡도: Θ(n)

---

기수, 계수, 버킷 정렬은 O(n)의 복잡도를 가진 알고리즘이다.

---