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

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

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

ソートプロセスには以下が含まれますwing プロパティ:

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

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

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

基数ソートアルゴリズムの仕組み
ソートする整数のリスト

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

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

ステップ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 回目の反復

基数ソートアルゴリズムの仕組み
XNUMXの位の数字に基づくソート

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

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

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

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

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

基数ソートアルゴリズムの仕組み
XNUMX 回目の反復後のリスト

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

c) XNUMX 回目の反復

基数ソートアルゴリズムの仕組み
数百桁の数字に基づいて並べ替える

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

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

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

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

基数ソートアルゴリズムの仕組み
XNUMX回目の反復後のリスト

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

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

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

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]

とplexRadix Sort の性質分析

コムにはXNUMX種類ありますplex考慮すべき点、スペースコムplexシティアンドタイムコムplexity。

  • スペースコムplexity: O(n+b) ここで、n は配列のサイズ、b は考慮される基数です。
  • とチームを組むplexity: O(d*(n+b)) ここで、d は配列内の最大要素の桁数です。

スペースコムplex基数ソートの数

space com で注目すべき XNUMX つの機能plexITY

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

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

コム全体plexしたがって、ity は O(n+b) になります。

次のことwing リスト内の要素のプロパティにより、基数ソート スペースが非効率になる可能性があります。

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

タイムコムplex基数ソートの数

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

基数ソートの直線性

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

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

Radix Sort と他の比較アルゴリズムとの比較

これまで見てきたように、基数ソートの complex性は単語または数値のサイズに基づきます。 同じコムになりますplex平均的なケースと最良のケースの場合。 それは O(d*(n+b)) です。 また、途中で使用する並べ替え手法によっても異なります。 たとえば、基数ソート内の中間ソート アルゴリズムとしてカウント ソートまたはクイック ソートを使用できます。

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

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

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