logo

TechCodeview

カウンティングソート – データ構造とアルゴリズムのチュートリアル

カウンティングソートとは何ですか?

カウンティングソート です 非比較ベース 入力値の範囲が限られている場合に適切に機能する並べ替えアルゴリズム。これは、入力値の範囲がソート対象の要素の数に比べて小さい場合に特に効率的です。背後にある基本的な考え方 カウンティングソート を数えるということです 頻度 入力配列内の個別の各要素の情報を取得し、その情報を使用して要素を正しい並べ替え位置に配置します。

カウンティングソートアルゴリズムはどのように機能しますか?

ステップ1 ：



  • 調べてください 最大 指定された配列の要素。

inputArray[] 内の最大要素の検索

ステップ2：

  • を初期化します countArray[] 長さの 最大+1 すべての要素を次のようにします 0 。この配列は、入力配列の要素の出現を格納するために使用されます。

countArray[] を初期化します



ステップ 3:

  • の中に countArray[] 、入力配列の一意の各要素の数をそれぞれのインデックスに格納します。
  • 例えば： 要素の数 2 入力配列には 2. それで、保管してください 2 インデックスで 2 の中に countArray[] 。同様に要素数も 5 入力配列には 1 、したがってストア 1 インデックスで 5 の中に countArray[] 。

countArray[] 内の各要素の数を維持します。

ステップ 4:



  • 保管してください 累計 または プレフィックスの合計 の要素の countArray[] することによって countArray[i] = countArray[i – 1] + countArray[i]。 これは、入力配列の要素を出力配列の正しいインデックスに配置するのに役立ちます。

累積合計を countArray[] に格納します

ステップ5:

  • 入力配列の末尾から反復し、入力配列を末尾から走査すると等しい要素の順序が維持されるため、最終的にこのソート アルゴリズムが作成されます。 安定した 。
  • アップデート OutputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] 。
  • また、アップデート countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – –。

5

ステップ6: i = 6 の場合 、

ホストLinux

アップデート OutputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
また、アップデート countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

inputArray[6]をoutputArray[]の正しい位置に配置します

ステップ 7: i = 5 の場合 、

アップデート OutputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
また、アップデート countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

inputArray[5]をoutputArray[]の正しい位置に配置します

ステップ8: i = 4 の場合 、

アップデート OutputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
また、アップデート countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

inputArray[4]をoutputArray[]の正しい位置に配置します

ステップ9: i = 3 の場合 、

アップデート OutputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
また、アップデート countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

inputArray[3]をoutputArray[]の正しい位置に配置します

ステップ 10: i = 2 の場合 、

アップデート OutputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
また、アップデート countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

inputArray[2]をoutputArray[]の正しい位置に配置します

ステップ 11: i = 1 の場合 、

アップデート OutputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
また、アップデート countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

inputArray[1]をoutputArray[]の正しい位置に配置します

ステップ 12: i = 0 の場合、

アップデート OutputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
また、アップデート countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

inputArray[0]をoutputArray[]の正しい位置に配置します

カウンティングソートアルゴリズム:

  • 補助配列を宣言する countArray[] サイズの max(入力配列[])+1 そしてそれを初期化します 0 。
  • トラバース配列 入力配列[] の各要素をマップします 入力配列[] の指標として countArray[] 配列、つまり実行 countArray[inputArray[i]]++ のために 0 <= i < N 。
  • 配列のすべてのインデックスでプレフィックスの合計を計算します 入力配列 []。
  • 配列を作成する 出力配列[] サイズの N 。
  • トラバース配列 入力配列[] 最後から更新して OutputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] 。また、アップデート countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – 。

上記のアルゴリズムの実装を以下に示します。

ジャワ




import> java.util.Arrays;> public> class> CountSort {> >public> static> int>[] countSort(>int>[] inputArray) {> >int> N = inputArray.length;> >int> M =>0>;> >for> (>int> i =>0>; i M = Math.max(M, inputArray[i]); } int[] countArray = new int[M + 1]; for (int i = 0; i countArray[inputArray[i]]++; } for (int i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } int[] outputArray = new int[N]; for (int i = N - 1; i>= 0; i--) {outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; 出力配列を返します。 public static void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9}; int[] 出力配列 = countSort(入力配列); for (int i = 0; i System.out.print(outputArray[i] + ' '); } } }>> 

>

>

C#




using> System;> using> System.Collections.Generic;> class> GFG> {> >static> List<>int>>カウントソート(リスト<>int>>inputArray)>>' {> >int> N = inputArray.Count;> >// Finding the maximum element of the array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = Math.Max(M, inputArray[i]); // Initializing countArray[] with 0 List countArray = 新しいリスト (新しい int[M + 1]); // inputArray[] の各要素をインデックスとしてマッピング // countArray[] 配列の for (int i = 0; i countArray[inputArray[i]]++; // 配列 countArray のすべてのインデックスでプレフィックスの合計を計算します // [] for (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List OutputArray = 新しいリスト (新しい int[N]); for (int i = N - 1; i>= 0; i--) {outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; 出力配列を返します。 } // ドライバーコード static void Main() { // 入力配列 List inputArray = 新しいリスト { 4、3、12、1、5、5、3、9 }; // 配列リストを出力する 出力配列 = CountSort(入力配列); for (int i = 0; i Console.Write(outputArray[i] + ' '); Console.WriteLine(); } }>> 

>

>

JavaScript




function> countSort(inputArray) {> >const N = inputArray.length;> >// Finding the maximum element of inputArray> >let M = 0;> >for> (let i = 0; i M = Math.max(M, inputArray[i]); } // Initializing countArray with 0 const countArray = new Array(M + 1).fill(0); // Mapping each element of inputArray as an index of countArray for (let i = 0; i countArray[inputArray[i]]++; } // Calculating prefix sum at every index of countArray for (let i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } // Creating outputArray from countArray const outputArray = new Array(N); for (let i = N - 1; i>= 0; i--) {outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; 出力配列を返します。 } // ドライバー コード const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // 入力配列のソート const OutputArray = countSort(inputArray); // ソートされた配列を出力します console.log(outputArray.join(' ')); //このコードは Utkarsh によって提供されました>>

関係です 

>

>

C++14




#include> using> namespace> std;> vector<>int>>countSort(ベクトル<>int>>& inputArray)>> {> >int> N = inputArray.size();> >// Finding the maximum element of array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = max(M, inputArray[i]); // Initializing countArray[] with 0 vector countArray(M + 1, 0); // inputArray[] の各要素をインデックスとしてマッピング // countArray[] 配列の for (int i = 0; i countArray[inputArray[i]]++; // 配列 countArray のすべてのインデックスでプレフィックスの合計を計算します // [] for (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector 出力配列(N); for (int i = N - 1; i>= 0; i--) {outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; 出力配列を返します。 } // ドライバーコード int main() { // 入力配列ベクトル inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // 配列ベクトルを出力します 出力配列 = countSort(入力配列); for (int i = 0; i cout<< outputArray[i] << ' '; return 0; }> 

>

>

Python3




def> count_sort(input_array):> ># Finding the maximum element of input_array.> >M>=> max>(input_array)> ># Initializing count_array with 0> >count_array>=> [>0>]>*> (M>+> 1>)> ># Mapping each element of input_array as an index of count_array> >for> num>in> input_array:> >count_array[num]>+>=> 1> ># Calculating prefix sum at every index of count_array> >for> i>in> range>(>1>, M>+> 1>):> >count_array[i]>+>=> count_array[i>-> 1>]> ># Creating output_array from count_array> >output_array>=> [>0>]>*> len>(input_array)> >for> i>in> range>(>len>(input_array)>-> 1>,>->1>,>->1>):> >output_array[count_array[input_array[i]]>-> 1>]>=> input_array[i]> >count_array[input_array[i]]>->=> 1> >return> output_array> # Driver code> if> __name__>=>=> '__main__'>:> ># Input array> >input_array>=> [>4>,>3>,>12>,>1>,>5>,>5>,>3>,>9>]> ># Output array> >output_array>=> count_sort(input_array)> >for> num>in> output_array:> >print>(num, end>=>' '>)> 

>

>

出力 

1 3 3 4 5 5 9 12>

カウンティングソートの複雑さの分析:

  • 時間計算量 : O(N+M)、ここで N そして M のサイズです 入力配列[] そして countArray[] それぞれ。
    • 最悪の場合: O(N+M)。
    • 平均的なケース: O(N+M)。
    • 最良の場合: O(N+M)。
  • 補助スペース: O(N+M)、ここで N そして M が占めるスペースは 出力配列[] そして countArray[] それぞれ。

カウンティングソートの利点:

  • 一般に、入力範囲が入力数程度の場合、カウント ソートは、マージ ソートやクイックソートなどのすべての比較ベースの並べ替えアルゴリズムよりも高速に実行されます。
  • カウントソートのコーディングは簡単です
  • カウンティングソートとは、 安定したアルゴリズム 。

カウンティングソートの欠点:

  • カウントソートは 10 進数値では機能しません。
  • ソートする値の範囲が非常に大きい場合、ソートのカウントは非効率的です。
  • カウントソートは、 インプレース並べ替え アルゴリズムでは、配列要素を並べ替えるために余分なスペースが使用されます。