logo

TechCodeview

基数ソート – データ構造とアルゴリズムのチュートリアル

ソート基数 要素を桁ごとに処理して並べ替える線形並べ替えアルゴリズムです。これは、固定サイズのキーを持つ整数または文字列の効率的な並べ替えアルゴリズムです。

基数ソートは要素を直接比較するのではなく、各桁の値に基づいて要素をバケットに分配します。基数ソートでは、要素を有効数字で最下位から最上位へ繰り返し並べ替えることで、最終的な並べ替え順序が得られます。



基数ソートアルゴリズム

Radix Sort の背後にある重要なアイデアは、位の値の概念を活用することです。数値を桁ごとに並べ替えると、最終的には完全に並べ替えられたリストが得られると想定しています。基数ソートは、最下位桁 (LSD) 基数ソートや最上位桁 (MSD) 基数ソートなど、さまざまなバリエーションを使用して実行できます。

基数ソートアルゴリズムはどのように機能しますか?

配列 [170, 45, 75, 90, 802, 24, 2, 66] で基数ソートを実行するには、次の手順に従います。

基数ソート アルゴリズムはどのように機能するのか |ステップ1



ステップ1： 配列内の最大の要素である 802 を見つけます。これは 3 桁なので、有効桁ごとに 1 回ずつ、3 回繰り返します。

ステップ2： 単位の位の桁 (X=0) に基づいて要素を並べ替えます。カウンティングソートなどの安定したソート手法を使用して、有効桁ごとに数字をソートします。

Javaでスローを投げる

単位の位置に基づいて並べ替える:



  • 単位桁の桁に基づいて配列に対してカウントソートを実行します。
  • 単位の位に基づいてソートされた配列は [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

Pythonリデュース

以下は、上記の図の実装です。

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 Output[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];  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 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を返します。  } // arr[] を // exp で表される桁に応じてカウントソートする関数。  static void countSort(int arr[], int n, int exp) { int Output[] = new int[n]; // 出力配列 int i;  int count[] = 新しい int[10];  Arrays.fill(count, 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];  count[(arr[i] / exp) % 10]--;  } // 出力配列を arr[] にコピーします。これで、arr[] には // 現在の桁に従ってソートされた数値が含まれます。 // (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);  } }>
Python3 
# 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 Output[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] # Function Call radixSort(arr) for i in range(len(arr)): print(arr[i], end=' ') # このコードは Mohit Kumra によって寄稿されました # Patrick Gallagher によって編集されました>>
C# 
// 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を返します。  } // arr[] を // exp で表される桁に応じてカウントソートする関数。  public static void countSort(int[] arr, int n, int exp) { int[] 出力 = new 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];  count[(arr[i] / exp) % 10]--;  } // 出力配列を arr[] にコピーします。これで、arr[] には // 現在の桁に従ってソートされた数値が含まれます。 // (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_ }>
JavaScript 
// 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 を返します。 } // arr[] を // exp で表される桁に応じてカウントソートする関数。関数 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 digit = Math.floor(arr[i] / exp) % 10;  出力[カウント[桁] - 1] = arr[i];  カウント[桁]--;  出力を返します。 } // 基数ソート関数を使用して arr[] をソートするメイン関数 radixSort(arr) { // 桁数を知るための最大値を見つけます const maxNumber = getMax(arr);  // ソートされた値が保持される浅いコピーを作成します letsortedArr = [...arr];  // 桁ごとにカウントソートを実行します。 // 桁数を渡す代わりに、exp が渡されることに注意してください。  // exp は 10^i ここで、i は現在の桁数 for (let exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // カウントのソート反復を取得します constsortedIteration = countSort(sortedArr) 、経験値);  ソート済みArr = ソート済み反復;  ソートされたArrを返します。 } /*ドライバーコード*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // 関数呼び出し constsortedArr = 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` [配列] をカウントソートする関数。リスト countSort(リスト 配列、int exp) {最終的な長さ = array.length;  最終出力Arr = List.filled(length, 0);  // インデックスが数字を表し、値が出現回数を表すリスト。 // 最終桁数Count = List.filled(10, 0);  // 出現回数を digitCount[] に格納します for (配列の最後の項目) { 最終桁 = item ~/ exp % 10;  桁数[桁]++;  // digitCount[i] に、outputArr[] 内のこの数字の実際の位置が // 含まれるように、digitCount[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];  最後の桁 = item ~/ exp % 10;  出力Arr[桁数[桁] - 1] = アイテム;  桁数[桁]--;  出力Arrを返します。 } /// 基数ソートリストを使用して `List` [配列] をソートするメイン関数 radixSort(リスト array) { // 桁数を知るための最大値を見つけます Final maxNumber = getMax(array);  // 入力配列の浅いコピー FinalsortedArr = List.of(array);  // 桁ごとにカウントソートを実行します。 // 数値を渡す代わりに、exp が渡されることに注意してください。 exp は 10^i、i は現在の桁数 for (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) {finalsortedIteration = countSort(sortedArr, exp);  ソート済みArr.clear();  sortedArr.addAll(sortedIteration);  ソートされたArrを返します。 void main() { const 配列 = [170, 45, 75, 90, 802, 24, 2, 66];  最終ソート配列 = radixSort(配列);  print(sortedArray); } // このコードは beeduhboodee によって提供されました>>
出力 
2 24 45 66 75 90 170 802>

基数ソートの複雑さの分析 :

時間計算量:

  • 基数ソートは、同じ有効位置と値を共有する個々の数字ごとにキーをグループ化することにより、整数キーを使用してデータを並べ替える非比較整数並べ替えアルゴリズムです。時間計算量は次のとおりです O(d * (n + b)) ここで、d は桁数、n は要素の数、b は使用されている記数法の基数です。
  • 実際の実装では、大規模なデータセットの場合、特にキーの桁数が多い場合、基数ソートは、クイックソートやマージ ソートなどの他の比較ベースのソート アルゴリズムよりも高速であることがよくあります。ただし、時間計算量は桁数に応じて直線的に増加するため、小さなデータセットの場合はそれほど効率的ではありません。

補助スペース:

  • 基数ソートの空間計算量も次のとおりです。 O(n + b)、 ここで、n は要素の数、b は数体系の基数です。この空間の複雑さは、各桁の値に対してバケットを作成し、各桁がソートされた後に要素を元の配列にコピーし直す必要があることから生じます。

RadixSort に関するよくある質問

Q1.基数ソートは、クイックソートのような比較ベースのソート アルゴリズムよりも望ましいですか?

ログがあれば2各桁が n ビットであるため、広範囲の入力数値に対して基数の実行時間はクイック ソートよりも優れているようです。漸近表記に隠された定数因数は基数ソートの方が高く、クイックソートはハードウェア キャッシュをより効果的に使用します。また、基数ソートはサブルーチンとしてカウントソートを使用し、カウントソートは数値をソートするために余分なスペースを必要とします。

Q2. 要素が 1からnまでの範囲 2 ?

  • 比較ベースのソート アルゴリズム (マージ ソート、ヒープ ソート、クイック ソートなど) の下限は Ω(nLogn) です。つまり、これより優れた結果は得られません。 nログイン 。カウンティング ソートは、要素が 1 から k までの範囲にある場合に O(n+k) 時間でソートする線形時間ソート アルゴリズムです。
  • カウントソートには O(n がかかるため、カウントソートは使用できません2) これは、比較ベースの並べ替えアルゴリズムよりも劣ります。このような配列を線形時間でソートできるでしょうか?
    • ソート基数 が答えです。基数ソートの考え方は、最下位桁から最上位桁まで順番に桁ごとにソートを実行することです。基数ソートは、ソートのサブルーチンとしてカウントソートを使用します。