データ構造における基数ソートアルゴリズム

基数ソートアルゴリズムとは何ですか?

基数ソートは、非比較ソートアルゴリズムです。これは、並べ替える要素の個々の桁をグループ化することによって機能します。次に、安定した並べ替え手法を使用して、基数に基づいて要素を整理します。これは線形ソートアルゴリズムです。

ソートプロセスには次のプロパティが関係します。

最大の要素を見つけて、その要素の桁数を取得します。これにより、並べ替えプロセスの反復回数がわかります。
各反復で同じ有効位置にある要素の個々の桁をグループ化します。
グループ化プロセスは、最下位桁から開始され、最上位桁で終了します。
有効な位置の数字に基づいて要素を並べ替えます。
同じキー値を持つ要素の相対的な順序を維持します。基数ソートのこの特性により、基数ソートは安定したソートになります。

最後の反復では、完全にソートされたリストが得られます。

基数ソートアルゴリズムの仕組み

基数ソートアルゴリズムを使用して、上図の整数のリストを昇順に並べ替えてみます。

基数ソートプロセスを実行する手順は次のとおりです。

ステップ1） リスト内の最大値を持つ要素を特定します。この場合は 835 です。

ステップ2） 最大要素の桁数を計算します。 835はちょうど3桁です。

ステップ3） 手順 2 に基づいて反復回数を決定します。835 は 3 桁なので、反復回数は 3 になります。

ステップ4） 要素の基底を決定します。 10進数なので底はXNUMXになります。

ステップ5） 最初の反復を開始します。

a) 最初の反復

最初の反復では、各要素の単位位の値を考慮します。

ステップ1） 整数を 10 で変更して、要素の単位の位を取得します。たとえば、623 mod 10 では値 3 が得られ、248 mod 10 では値 8 が得られます。

ステップ2） 計数ソートまたはその他の安定したソートを使用して、最下位桁に従って整数を整理します。図からわかるように、248 が 8 番目のバケツに落ちます。 623 は 3 番目のバケツに落ちます。

最初の反復の後、リストは次のようになります。

上に示した図からわかるように、リストはまだソートされていないため、完全にソートするにはさらに反復が必要です。

b) XNUMX 回目の反復

この反復では、10 の位の数字を考慮します。^th 仕分け作業を行う場所。

ステップ1） 整数を 10 で割ります。248 を 10 で割ると 24 になります。

ステップ2） ステップ 1 の出力を 10 で変更します。24 mod 10 は 4 を返します。

ステップ3） 前回の反復のステップ 2 に従います。

XNUMX 回目の反復の後、リストは次のようになります。

上に示した図から、リストはまだ昇順になっていないため、完全にはソートされていないことがわかります。

c) XNUMX 回目の反復

最後の反復では、最上位桁を取得する必要があります。この場合は100です^thリスト内の各整数を配置します。

ステップ1） 整数を 100 で割ると… 415 を 100 で割ると 4 になります。

ステップ2） ステップ 1 の結果を 10 で変更します。4 mod 10 により、再び 4 が得られます。

ステップ3） 前回の反復のステップ 3 に従います。

ご覧のとおり、リストは昇順にソートされています。最後の反復が完了し、並べ替えプロセスが終了しました。

基数ソートアルゴリズムの擬似コード

これは基数ソートアルゴリズムの疑似コードです。

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 j^th 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 j^thplace
   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]

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

考慮すべき複雑さには、空間複雑さと時間複雑さの 2 種類があります。

空間計算量: O(n+b)。ここで、n は配列のサイズ、b は考慮される基数です。
時間計算量: O(d*(n+b))。ここで、d は配列内の最大要素の桁数です。

基数ソートの空間計算量

空間複雑性に焦点を当てる2つの機能

配列内の要素の数、 n.
要素を表現するためのベース、 b.

場合によっては、この基数が配列のサイズよりも大きくなることがあります。

したがって、全体的な複雑さは O(n+b) になります。

リスト内の要素の次の特性により、基数ソートのスペースが非効率になる可能性があります。

桁数の多い要素。
要素の基数は 64 ビットの数値のように大きくなります。

基数ソートの時間計算量

各反復には時間がかかるため、カウントソートをサブルーチンとして使用できます。e O(n+b) 時間。 d 回の反復が存在する場合、合計実行時間は次のようになります。 O(d*(n+b))。 ここで、「O」は複雑度関数を意味します。

基数ソートの直線性

基数ソートは次の場合に線形です。

d は定数で、d は最大要素の桁数です。
b に比べてそれほど大きくない n.

基数ソートと他の比較アルゴリズムの比較

これまで見てきたように、Radix ソートの複雑さは単語または数字のサイズに基づいています。平均の場合も最良の場合も同じ複雑さになります。これは O(d*(n+b)) です。また、中間で使用するソート手法によっても異なります。たとえば、Radix ソート内の中間ソートアルゴリズムには、カウンティングソートまたはクイックソートを使用できます。

基数ソートアルゴリズムの応用

基数ソートの重要な用途は次のとおりです。

基数ソートは、広範囲の値が使用される位置検索アルゴリズムとして使用できます。
これは、DC3 アルゴリズムでサフィックス配列を構築する際に使用されます。
これは、レコードがキー入力される一般的なコンピューターに搭載されている順次ランダムアクセスマシンで使用されます。

よろしければ：

基数ソート アルゴリズムとは何ですか?