데이터 구조의 기수 정렬 알고리즘

작성자 : 사라 첸 사라 첸
Hours 업데이트

기수 정렬 알고리즘이란 무엇입니까?

기수 정렬은 비비교 정렬 알고리즘입니다. 정렬할 요소의 개별 숫자를 그룹화하여 작동합니다. 그런 다음 안정적인 정렬 기술을 사용하여 기수를 기준으로 요소를 구성합니다. 선형 정렬 알고리즘입니다.

정렬 과정에는 다음과 같은 속성이 포함됩니다.

  • 최대 요소를 찾고 해당 요소의 자릿수를 얻습니다. 이는 정렬 프로세스가 따르는 반복 횟수를 제공합니다.
  • 각 반복에서 동일한 유효 위치에 있는 요소의 개별 숫자를 그룹화합니다.
  • 그룹화 프로세스는 최하위 숫자부터 시작하여 최상위 숫자에서 끝납니다.
  • 해당 중요한 위치의 숫자를 기준으로 요소를 정렬합니다.
  • 동일한 키 값을 갖는 요소의 상대적 순서를 유지합니다. 기수 정렬의 이러한 속성으로 인해 안정적인 정렬이 가능해집니다.

최종 반복에서는 완전히 정렬된 목록이 제공됩니다.

기수 정렬 알고리즘의 작동

기수 정렬 알고리즘의 작동
정렬할 정수 목록

Radix Sort 알고리즘을 사용하여 위 그림의 정수 목록을 오름차순으로 정렬해 보겠습니다.

기수 정렬 프로세스를 수행하는 단계는 다음과 같습니다.

단계 1) 목록에서 최대값을 가진 요소를 식별합니다. 이 경우에는 835입니다.

단계 2) 최대 요소의 자릿수를 계산합니다. 835는 정확히 3자리 숫자입니다.

단계 3) 2단계를 기준으로 반복 횟수를 결정합니다. 835는 3자리이므로 반복 횟수는 3이 됩니다.

단계 4) 요소의 기본을 결정합니다. 이것은 십진법이므로 밑은 10이 됩니다.

단계 5) 첫 번째 반복을 시작합니다.

a) 첫 번째 반복

기수 정렬 알고리즘의 작동
마지막 숫자로 정렬

첫 번째 반복에서는 각 요소의 단위 자리값을 고려합니다.

단계 1) 요소의 단위 위치를 얻으려면 정수를 10으로 수정하세요. 예를 들어 623 mod 10은 값 3을 제공하고 248 mod 10은 8을 제공합니다.

단계 2) 계수 정렬 또는 기타 안정적인 정렬을 사용하여 최하위 숫자에 따라 정수를 구성합니다. 그림에서 볼 수 있듯이 248은 8번째 버킷에 떨어집니다. 623은 세 번째 버킷에 떨어지게 됩니다.

첫 번째 반복 후 목록은 이제 다음과 같습니다.

기수 정렬 알고리즘의 작동
첫 번째 반복 후 나열

위 그림에서 볼 수 있듯이 목록은 아직 정렬되지 않았으며 완전히 정렬하려면 더 많은 반복이 필요합니다.

b) 두 번째 반복

기수 정렬 알고리즘의 작동
십의 자리 숫자를 기준으로 정렬

이번 반복에서는 10의 숫자를 고려해 보겠습니다.th 분류 과정을 위한 장소입니다.

단계 1) 정수를 10으로 나눕니다. 248을 10으로 나누면 24가 됩니다.

단계 2) 1단계의 출력을 10으로 수정합니다. 24 mod 10은 4를 제공합니다.

단계 3) 이전 반복의 2단계를 수행합니다.

두 번째 반복 후 목록은 이제 다음과 같습니다.

기수 정렬 알고리즘의 작동
두 번째 반복 후 나열

위의 그림을 보면 목록이 아직 오름차순이 아니기 때문에 완전히 정렬되지 않은 것을 볼 수 있습니다.

c) 세 번째 반복

기수 정렬 알고리즘의 작동
수백 곳의 숫자를 기준으로 정렬

최종 반복에서는 가장 중요한 숫자를 얻고 싶습니다. 이 경우에는 100입니다.th 목록의 각 정수를 배치합니다.

단계 1) 정수를 100으로 나누면… 415를 100으로 나누면 4가 됩니다.

단계 2) 1단계의 결과를 10으로 수정합니다. 4 mod 10은 다시 4를 제공합니다.

단계 3) 이전 반복의 3단계를 수행합니다.

기수 정렬 알고리즘의 작동
세 번째 반복 후 나열

보시다시피 이제 목록이 오름차순으로 정렬되었습니다. 최종 반복이 완료되어 이제 정렬 프로세스가 완료되었습니다.

관련 기사

기수 정렬 알고리즘의 의사 코드

Radix Sort 알고리즘의 의사 코드는 다음과 같습니다.

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the jth place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the jthplace
   arr = sorted elements

C++ 기수 정렬을 구현하는 프로그램

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

출력:

162 248 415 623 835

Python 기수 정렬 알고리즘 프로그램

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

출력:

[162,248,415,623,835]

Radix Sort의 복잡도 분석

고려해야 할 복잡성에는 공간 복잡성과 시간 복잡성이라는 두 가지 유형이 있습니다.

  • 공간 복잡도: O(n+b) 여기서 n은 배열의 크기이고 b는 고려되는 기준입니다.
  • 시간 복잡도: O(d*(n+b)) 여기서 d는 배열에서 가장 큰 요소의 자릿수입니다.

Radix Sort의 공간 복잡도

공간 복잡성에 초점을 맞춰야 할 두 가지 기능

  • 배열의 요소 수 n.
  • 요소를 표현하기 위한 기반, b.

때로는 이 기본이 배열 크기보다 클 수 있습니다.

따라서 전반적인 복잡도는 O(n+b)입니다.

목록의 요소에 대한 다음과 같은 속성은 기수 정렬 공간을 비효율적으로 만들 수 있습니다.

  • 자릿수가 많은 요소.
  • 요소의 기본은 64비트 숫자처럼 큽니다.

Radix 정렬의 시간 복잡도

각 반복이 수행되므로 계산 정렬을 서브루틴으로 사용할 수 있습니다.전자O(n+b) 시간. D 반복이 존재하는 경우 총 실행 시간은 다음과 같습니다. O(d*(n+b)). 여기서 “O”는 복잡도 함수를 의미합니다.

기수 정렬의 선형성

기수 정렬은 다음과 같은 경우 선형입니다.

  • d 여기서 d는 가장 큰 요소의 자릿수입니다.
  • b 비해 규모가 그리 크지는 않습니다. n.

Radix Sort와 다른 비교 알고리즘의 비교

우리가 보았듯이 Radix 정렬의 복잡도는 단어나 숫자 크기에 기반합니다. 평균 및 최상의 경우에 동일한 복잡도를 갖습니다. 그리고 그것은 O(d*(n+b))입니다. 또한, 중간에 사용하는 정렬 기술에 따라 다릅니다. 예를 들어, Radix 정렬 내부의 중간 정렬 알고리즘에 대해 카운팅 정렬이나 퀵 정렬을 사용할 수 있습니다.

기수 정렬 알고리즘의 응용

기수 정렬의 중요한 응용 분야는 다음과 같습니다.

  • Radix Sort는 넓은 범위의 값이 사용되는 위치 찾기 알고리즘으로 사용할 수 있습니다.
  • DC3 알고리즘에서 접미사 배열을 구성하는 데 사용됩니다.
  • 일반적인 컴퓨터에서 레코드를 키로 입력하는 순차적이고 임의 접근이 가능한 기계에서 사용됩니다.