logo

TechCodeview

기수 정렬 – 데이터 구조 및 알고리즘 자습서

기수 정렬 요소를 숫자 단위로 처리하여 정렬하는 선형 정렬 알고리즘입니다. 고정 크기 키를 사용하는 정수 또는 문자열에 대한 효율적인 정렬 알고리즘입니다.

요소를 직접 비교하는 대신 Radix Sort는 각 숫자의 값을 기준으로 요소를 버킷에 배포합니다. Radix Sort는 유효 숫자를 기준으로 요소를 반복적으로 정렬하여 가장 중요한 숫자부터 가장 중요한 숫자까지 최종 정렬 순서를 달성합니다.



기수 정렬 알고리즘

Radix Sort의 핵심 아이디어는 자리값 개념을 활용하는 것입니다. 숫자를 숫자별로 정렬하면 결국 완전히 정렬된 목록이 생성된다고 가정합니다. 기수 정렬은 LSD(최하위 숫자) 기수 정렬 또는 MSD(최상위 숫자) 기수 정렬과 같은 다양한 변형을 사용하여 수행할 수 있습니다.

기수 정렬 알고리즘은 어떻게 작동합니까?

배열 [170, 45, 75, 90, 802, 24, 2, 66]에 대해 기수 정렬을 수행하려면 다음 단계를 수행합니다.

기수 정렬 알고리즘은 어떻게 작동합니까? 1 단계



1 단계: 배열에서 가장 큰 요소인 802를 찾습니다. 세 자리 숫자이므로 각 중요한 위치에 대해 한 번씩 세 번 반복합니다.

2 단계: 단위 자리 숫자(X=0)를 기준으로 요소를 정렬합니다. 우리는 카운팅 정렬과 같은 안정적인 정렬 기술을 사용하여 각 중요한 위치의 숫자를 정렬합니다.

Java에서 null 검사

단위 위치에 따른 정렬:



  • 단위 자릿수를 기준으로 배열에 대한 계수 정렬을 수행합니다.
  • 단위 위치를 기준으로 정렬된 배열은 [170, 90, 802, 2, 24, 45, 75, 66]입니다.

기수 정렬 알고리즘은 어떻게 작동합니까? 2 단계

3단계: 십의 자리 숫자를 기준으로 요소를 정렬합니다.

10자리 기준으로 정렬:

  • 10자리 숫자를 기준으로 배열에 대한 계산 정렬을 수행합니다.
  • 십의 자리를 기준으로 정렬된 배열은 [802, 2, 24, 45, 66, 170, 75, 90]입니다.

기수 정렬 알고리즘은 어떻게 작동합니까? 3단계

4단계: 백 자리 숫자를 기준으로 요소를 정렬합니다.

수백 자리 기준으로 정렬:

  • 백 자리 숫자를 기준으로 배열에 대한 계산 정렬을 수행합니다.
  • 백 자리를 기준으로 정렬된 배열은 [2, 24, 45, 66, 75, 90, 170, 802]입니다.

기수 정렬 알고리즘은 어떻게 작동합니까? 4단계

5단계: 이제 배열이 오름차순으로 정렬되었습니다.

자바 예외 발생

기수 정렬을 사용하여 최종 정렬된 배열은 [2, 24, 45, 66, 75, 90, 170, 802]입니다.

기수 정렬 알고리즘은 어떻게 작동합니까? 5단계

다음은 위 그림의 구현입니다.

C++ 
// C++ implementation of Radix Sort #include  using namespace std; // A utility function to get maximum // value in arr[] int getMax(int arr[], int n) {  int mx = arr[0];  for (int i = 1; i < n; i++)  if (arr[i]>mx) mx = arr[i];  mx를 반환합니다. } // exp가 나타내는 숫자에 따라 // arr[] // 계수를 수행하는 함수입니다. void countSort(int arr[], int n, int exp) { // 출력 배열 int 출력[n];  int i, count[10] = { 0 };  // 발생 횟수를 // count[]에 저장합니다. for (i = 0; i< n; i++)  count[(arr[i] / exp) % 10]++;  // Change count[i] so that count[i]  // now contains actual position  // of this digit in output[]  for (i = 1; i < 10; i++)  count[i] += count[i - 1];  // Build the output array  for (i = n - 1; i>= 0; i--) { 출력[개수[(arr[i] / exp) % 10] - 1] = arr[i];  개수[(arr[i] / exp) % 10]--;  } // 출력 배열을 arr[]에 복사합니다. // 이제 arr[]에는 // 현재 숫자에 따라 정렬된 숫자가 포함됩니다. for (i = 0; i< n; i++)  arr[i] = output[i]; } // The main function to that sorts arr[] // of size n using Radix Sort void radixsort(int arr[], int n) {  // Find the maximum number to  // know number of digits  int m = getMax(arr, n);  // Do counting sort for every digit.  // Note that instead of passing digit  // number, exp is passed. exp is 10^i  // where i is current digit number  for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // 배열을 인쇄하는 유틸리티 함수 void print(int arr[], int n) { for (int i = 0; i< n; i++)  cout << arr[i] << ' '; } // Driver Code int main() {  int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  radixsort(arr, n);  print(arr, n);  return 0; }>
자바 
// Radix sort Java implementation import java.io.*; import java.util.*; class Radix {  // A utility function to get maximum value in arr[]  static int getMax(int arr[], int n)  {  int mx = arr[0];  for (int i = 1; i < n; i++)  if (arr[i]>mx) mx = arr[i];  mx를 반환합니다.  } // exp가 나타내는 숫자에 따라 // arr[]의 종류를 계산하는 함수입니다.  static void countSort(int arr[], int n, int exp) { int 출력[] = new int[n]; // 출력 배열 int i;  int count[] = 새로운 int[10];  Arrays.fill(count, 0);  // (i = 0; i에 대해 count[]에 발생 횟수를 저장합니다.< n; i++)  count[(arr[i] / exp) % 10]++;  // Change count[i] so that count[i] now contains  // actual position of this digit in output[]  for (i = 1; i < 10; i++)  count[i] += count[i - 1];  // Build the output array  for (i = n - 1; i>= 0; i--) { 출력[개수[(arr[i] / exp) % 10] - 1] = arr[i];  개수[(arr[i] / exp) % 10]--;  } // 출력 배열을 arr[]에 복사하여 이제 arr[]에는 // 현재 숫자에 따라 // 정렬된 숫자가 포함됩니다. for (i = 0; i< n; i++)  arr[i] = output[i];  }  // The main function to that sorts arr[] of  // size n using Radix Sort  static void radixsort(int arr[], int n)  {  // Find the maximum number to know number of digits  int m = getMax(arr, n);  // Do counting sort for every digit. Note that  // instead of passing digit number, exp is passed.  // exp is 10^i where i is current digit number  for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp);  } // 배열을 인쇄하는 유틸리티 함수 static void print(int arr[], int n) { for (int i = 0; i< n; i++)  System.out.print(arr[i] + ' ');  }  // Main driver method  public static void main(String[] args)  {  int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };  int n = arr.length;  // Function Call  radixsort(arr, n);  print(arr, n);  } }>
파이썬3 
# Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to # the digit represented by exp. def countingSort(arr, exp1): n = len(arr) # The output array elements that will have sorted arr output = [0] * (n) # initialize count array as 0 count = [0] * (10) # Store count of occurrences in count[] for i in range(0, n): index = arr[i] // exp1 count[index % 10] += 1 # Change count[i] so that count[i] now contains actual # position of this digit in output array for i in range(1, 10): count[i] += count[i - 1] # Build the output array i = n - 1 while i>= 0: index = arr[i] // exp1 출력[count[index % 10] - 1] = arr[i] count[index % 10] -= 1 i -= 1 # 출력 배열을 arr[]에 복사 , # 이제 arr에 정렬된 숫자 i = 0이 포함됩니다. for i in range(0, len(arr)): arr[i] = output[i] # 기수 정렬을 수행하는 방법 def radixSort(arr): # 최대값을 구합니다. 자릿수를 알 수 있는 숫자 max1 = max(arr) # 모든 자릿수에 대해 계수 정렬을 수행합니다. 전달되는 숫자 대신에 exp가 전달됩니다. exp는 10^i # 여기서 i는 현재 숫자 exp = 1 while max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # 드라이버 코드 arr = [170, 45, 75, 90, 802, 24 , 2, 66] # 함수 호출 radixSort(arr) for i in range(len(arr)): print(arr[i], end=' ') # 이 코드는 Mohit Kumra가 기여 # 편집자: Patrick Gallagher>
씨# 
// C# implementation of Radix Sort using System; class GFG {  public static int getMax(int[] arr, int n)  {  int mx = arr[0];  for (int i = 1; i < n; i++)  if (arr[i]>mx) mx = arr[i];  mx를 반환합니다.  } // exp가 나타내는 숫자에 따라 // arr[]의 종류를 계산하는 함수입니다.  public static void countSort(int[] arr, int n, int exp) { int[] 출력 = 새로운 int[n]; // 출력 배열 int i;  int[] 개수 = 새로운 int[10];  // count의 모든 요소를 ​​0으로 초기화 for (i = 0; i< 10; i++)  count[i] = 0;  // Store count of occurrences in count[]  for (i = 0; i < n; i++)  count[(arr[i] / exp) % 10]++;  // Change count[i] so that count[i] now contains  // actual  // position of this digit in output[]  for (i = 1; i < 10; i++)  count[i] += count[i - 1];  // Build the output array  for (i = n - 1; i>= 0; i--) { 출력[개수[(arr[i] / exp) % 10] - 1] = arr[i];  개수[(arr[i] / exp) % 10]--;  } // 출력 배열을 arr[]에 복사하여 이제 arr[]에는 // 현재 숫자에 따라 // 정렬된 숫자가 포함됩니다. for (i = 0; i< n; i++)  arr[i] = output[i];  }  // The main function to that sorts arr[] of size n using  // Radix Sort  public static void radixsort(int[] arr, int n)  {  // Find the maximum number to know number of digits  int m = getMax(arr, n);  // Do counting sort for every digit. Note that  // instead of passing digit number, exp is passed.  // exp is 10^i where i is current digit number  for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp);  } // 배열을 인쇄하는 유틸리티 함수 public static void print(int[] arr, int n) { for (int i = 0; i< n; i++)  Console.Write(arr[i] + ' ');  }  // Driver Code  public static void Main()  {  int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };  int n = arr.Length;  // Function Call  radixsort(arr, n);  print(arr, n);  }  // This code is contributed by DrRoot_ }>
자바스크립트 
// Radix sort JavaScript implementation 'use strict'; // A utility function to get maximum value in arr[] function getMax(arr) {  const length = arr.length;  let mx = arr[0];  for (let i = 1; i < length; i++) {  if (arr[i]>mx) mx = arr[i];  } mx를 반환합니다; } // exp가 나타내는 숫자에 따라 // arr[]의 종류를 계산하는 함수입니다. function countSort(arr, exp) { const length = arr.length;  출력 = 배열(길이); // 배열 출력 let count = Array(10).fill(0, 0);  // 발생 횟수를 count[]에 저장합니다. for (let i = 0; i< length; i++) {  const digit = Math.floor(arr[i] / exp) % 10;  count[digit]++;  }  // Change count[i] so that count[i] now contains  // actual position of this digit in output[]  for (let i = 1; i < 10; i++) {  count[i] += count[i - 1];  }  // Build the output array  for (let i = length - 1; i>= 0; i--) { const 숫자 = Math.floor(arr[i] / exp) % 10;  출력[개수[숫자] - 1] = arr[i];  개수[숫자]--;  } 출력을 반환합니다. } // Radix Sort를 사용하여 arr[]을 정렬하는 주요 함수 radixSort(arr) { // 자릿수를 알 수 있는 최대 수를 구합니다. const maxNumber = getMax(arr);  // 정렬된 값이 유지될 얕은 복사본을 만듭니다. let sortedArr = [...arr];  // 모든 자릿수에 대해 계수 정렬을 수행합니다. // 숫자 숫자를 전달하는 대신 exp가 전달됩니다.  // exp는 10^i입니다. 여기서 i는 현재 숫자입니다. for (let exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Count 정렬 반복을 가져옵니다. const sortedIteration = countSort(sortedArr , 특급);  sortedArr = sortedIteration;  } return sortedArr; } /*드라이버 코드*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // 함수 호출 const sortedArr = radixSort(arr); console.log(sortedArr.join(' ')); // 이 코드는 beeduhboodee가 제공한 것입니다.>
PHP 
 // PHP implementation of Radix Sort  // A function to do counting sort of arr[]  // according to the digit represented by exp.  function countSort(&$arr, $n, $exp) { $output = array_fill(0, $n, 0); // output array  $count = array_fill(0, 10, 0); // Store count of occurrences in count[]  for ($i = 0; $i < $n; $i++) $count[ ($arr[$i] / $exp) % 10 ]++; // Change count[i] so that count[i]  // now contains actual position of  // this digit in output[]  for ($i = 1; $i < 10; $i++) $count[$i] += $count[$i - 1]; // Build the output array  for ($i = $n - 1; $i>= 0; $i--) { $output[$count[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $count[ ($arr[$i] / $exp) % 10 ]--; } // 출력 배열을 arr[]에 복사하므로 // arr[]에는 // 현재 숫자에 따라 // 정렬된 숫자가 포함됩니다. for ($i = 0; $i< $n; $i++) $arr[$i] = $output[$i]; } // The main function to that sorts arr[]  // of size n using Radix Sort  function radixsort(&$arr, $n) { // Find the maximum number to know // number of digits  $m = max($arr); // Do counting sort for every digit. Note  // that instead of passing digit number,  // exp is passed. exp is 10^i where i is  // current digit number  for ($exp = 1; $m / $exp>0; $exp *= 10) countSort($arr, $n, $exp); } // 배열을 인쇄하는 유틸리티 함수 function PrintArray(&$arr,$n) { for ($i = 0; $i< $n; $i++) echo $arr[$i] . ' '; } // Driver Code  $arr = array(170, 45, 75, 90, 802, 24, 2, 66); $n = count($arr); // Function Call radixsort($arr, $n); PrintArray($arr, $n); // This code is contributed by rathbhupendra ?>>
다트 
// Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List 배열) { int max = 배열[0];  for (배열의 최종 it) { if (it> max) { max = it;  } } 최대값을 반환합니다. } /// [exp]가 나타내는 /// 숫자에 따라 `List` [array]의 계수 정렬을 수행하는 함수입니다. 목록 countSort(목록 array, int exp) { 최종 길이 = array.length;  최종 출력Arr = List.filled(length, 0);  // index가 숫자를 나타내고 value가 발생 횟수를 나타내는 // 리스트 final digitsCount = List.filled(10, 0);  // digitsCount[]에 발생 횟수를 저장합니다. for (배열의 마지막 항목) { 마지막 숫자 = 항목 ~/ exp % 10;  숫자카운트[숫자]++;  } // digitsCount[i]가 이제 //outputArr[]에서 이 숫자의 실제 위치를 포함하도록 digitsCount[i]를 변경합니다. for (int i = 1; i< 10; i++) {  digitsCount[i] += digitsCount[i - 1];  }  // Build the output array  for (int i = length - 1; i>= 0; i--) { 최종 항목 = 배열[i];  마지막 숫자 = 아이템 ~/ exp % 10;  outputArr[digitsCount[digit] - 1] = 항목;  숫자개수[숫자]--;  } 출력Arr을 반환; } /// Radix 정렬 목록을 사용하여 `List` [배열]을 정렬하는 주요 함수 radixSort(목록 array) { // 자릿수를 알기 위해 최대 수를 구함 final maxNumber = getMax(array);  // 입력 배열의 얕은 복사본 final sortedArr = List.of(array);  // 모든 숫자에 대해 계수 정렬을 수행합니다. 숫자 // 숫자를 전달하는 대신 exp가 전달됩니다. exp는 10^i입니다. 여기서 i는 현재 숫자입니다. for (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp);  sortedArr.clear();  sortedArr.addAll(sortedIteration);  } return sortedArr; } void main() { const 배열 = [170, 45, 75, 90, 802, 24, 2, 66];  final sortedArray = radixSort(array);  인쇄(sortedArray); } // 이 코드는 beeduhboodee가 제공한 것입니다.>
산출 
2 24 45 66 75 90 170 802>

기수 정렬의 복잡성 분석 :

시간 복잡도:

  • 기수 정렬은 동일한 유효 위치와 값을 공유하는 개별 숫자별로 키를 그룹화하여 정수 키로 데이터를 정렬하는 비비교 정수 정렬 알고리즘입니다. 의 시간복잡도를 갖는다 O(d * (n + b)) , 여기서 d는 자릿수, n은 요소 수, b는 사용되는 숫자 체계의 기본입니다.
  • 실제 구현에서 기수 정렬은 특히 키에 숫자가 많은 경우 대규모 데이터 세트의 경우 퀵 정렬 또는 병합 정렬과 같은 다른 비교 기반 정렬 알고리즘보다 빠른 경우가 많습니다. 그러나 시간 복잡도는 자릿수에 따라 선형적으로 증가하므로 작은 데이터 세트에는 효율적이지 않습니다.

보조 공간:

산술 논리 장치
  • 기수 정렬은 또한 다음과 같은 공간 복잡도를 갖습니다. O(n + b), 여기서 n은 요소의 수이고 b는 숫자 체계의 기본입니다. 이러한 공간 복잡성은 각 숫자 값에 대한 버킷을 생성하고 각 숫자가 정렬된 후 요소를 원래 배열에 다시 복사해야 하기 때문에 발생합니다.

RadixSort에 대해 자주 묻는 질문

Q1. Quick-Sort와 같은 비교 기반 정렬 알고리즘보다 Radix Sort가 선호됩니까?

로그가 있는 경우2모든 숫자에 대해 n 비트가 있으므로 Radix의 실행 시간은 광범위한 입력 숫자에 대해 Quick Sort보다 나은 것으로 보입니다. 점근적 표기법에 숨겨진 상수 요소는 기수 정렬의 경우 더 높으며 Quick-Sort는 하드웨어 캐시를 더 효과적으로 사용합니다. 또한 기수 정렬은 계산 정렬을 서브루틴으로 사용하고 계산 정렬은 숫자를 정렬하는 데 추가 공간을 필요로 합니다.

Q2. 요소가 범위는 1부터 n까지 2 ?

  • 비교 기반 정렬 알고리즘(병합 정렬, 힙 정렬, 빠른 정렬 .. 등)의 하한은 Ω(nLogn)입니다. 즉, 다음보다 더 잘할 수 없습니다. n로그인 . 카운팅 정렬은 요소가 1부터 k까지의 범위에 있을 때 O(n+k) 시간으로 정렬하는 선형 시간 정렬 알고리즘입니다.
  • 계산 정렬에는 O(n)이 소요되므로 계산 정렬을 사용할 수 없습니다.2) 이는 비교 기반 정렬 알고리즘보다 나쁩니다. 이러한 배열을 선형 시간으로 정렬할 수 있나요?
    • 기수 정렬 대답입니다. 기수 정렬(Radix Sort)의 아이디어는 최하위 숫자부터 최상위 숫자까지 숫자별로 정렬하는 것입니다. 기수 정렬은 정렬을 위한 서브루틴으로 계산 정렬을 사용합니다.