ソートの計算 - 効率

Question

私はソートを数え、それをどのように実装するか、実際にアルゴリズムの仕組みについて考えていました。私は1つの部分で立ち往生している、アルゴリズムは本当に簡単で理解しやすいですが、その一部は必要ではないようです。私は人々が間違っているかもしれないと思っていましたが、同じ方法を使用しているみんなのように見えますので、私はどこかで間違っています。あなたは説明していただけますか？

はここgeeksforgeeks

// C Program for counting sort 
#include <stdio.h> 
#include <string.h> 
#define RANGE 255 

// The main function that sort the given string arr[] in 
// alphabatical order 
void countSort(char arr[]) 
{ 
    // The output character array that will have sorted arr 
    char output[strlen(arr)]; 

    // Create a count array to store count of inidividul 
    // characters and initialize count array as 0 
    int count[RANGE + 1], i; 
    memset(count, 0, sizeof(count)); 

    // Store count of each character 
    for(i = 0; arr[i]; ++i) 
     ++count[arr[i]]; 

    // Change count[i] so that count[i] now contains actual 
    // position of this character in output array 
    for (i = 1; i <= RANGE; ++i) 
     count[i] += count[i-1]; 

    // Build the output character array 
    for (i = 0; arr[i]; ++i) 
    { 
     output[count[arr[i]]-1] = arr[i]; 
     --count[arr[i]]; 
    } 

    // Copy the output array to arr, so that arr now 
    // contains sorted characters 
    for (i = 0; arr[i]; ++i) 
     arr[i] = output[i]; 
} 

// Driver program to test above function 
int main() 
{ 
    char arr[] = "geeksforgeeks";//"applepp"; 

    countSort(arr); 

    printf("Sorted character array is %s\n", arr); 
    return 0; 
} 

クールからソートをカウントするためのコードですが、この部分について：

// Build the output character array 
     for (i = 0; arr[i]; ++i) 
     { 
      output[count[arr[i]]-1] = arr[i]; 
      --count[arr[i]]; 
     } 

なぜ私はこれが必要なのですか？ [OK]を私は私の数字をカウント：

のは、私は配列を持っていたとしましょう - この部分よりも> [1、3、6、3、2、4]

  INDEXES  0 1 2 3 4 5 6 
    I created this -> [0, 1, 1, 2, 1, 0, 1] 

は、この処理を行います。

[0, 1+0, 1+1, 2+2, 4+1, 0+5, 1+5] 
    [0, 1, 2, 4, 5, 5, 6] 

しかし、なぜ ？？

私のアレイはこれまでと同じように使用できませんか？ここに私のアイデアと私のコードは、なぜそれが間違っているか、他の方法がより有用である理由を説明してください。

void countingSort (int *arr) { 

    int countingArray[MAX_NUM] = {0}; 

    for (i = 0 ; i < ARRAY_SIZE ; i++) 
     countingArray[arr[i]]++; 

    int output_Index = 0; 

    for (i = 0 ; i < MAX_NUM ; i++) 
     while (countingArray[i]--) 
      arr[output_Index++] = i; 
} 

Answer 1

整数の配列を並べ替える単純なケースでは、コードはより簡単で優れています。

ただし、カウントソートは、アイテム自体を直接比較するのではなく、ソート対象のアイテムから派生したソートキーに基づいてソートすることができる一般的なソートアルゴリズムです。整数の配列の場合、項目とソートキーは同じものにすることができ、それらを直接比較するだけです。

geeksforgeeksコードは、このような何かをソートキーの使用を可能にする、より一般的な例から採用されてきたかのようにそれは私には見えます

：keyはソート・キーを計算する関数である

// Store count of each item 
for(i = 0; arr[i]; ++i) 
    ++count[key(arr[i])]; 

// Change count[i] so that count[i] now contains actual 
// position of this character in output array 
for (i = 1; i <= RANGE; ++i) 
    count[i] += count[i-1]; 

// Build the output array 
for (i = 0; arr[i]; ++i) 
{ 
    output[count[key(arr[i])]-1] = arr[i]; 
    --count[key(arr[i])]; 
} 

（整数型の場合は、整数そのものを返すことができる）アイテムに基づいています。この場合、MAX_NUMはMAX_KEYに置き換える必要があります。

count（各キーの項目の数のみを含む）の情報ではなく、arrの項目をコピーすることによって最終結果が生成されるため、このアプローチでは余分な出力配列が使用されます。ただし、in-place counting sortが可能です。

アルゴリズムでは、同じソートキーを持つ項目が並べ替えによって保存されるという相対的な順序も保証されています。これは整数をソートする際には意味がありません。

ただし、キーに基づいて並べ替える機能が削除されているため、余分な複雑さが増す理由はありません。

C++のような言語のコードをコピーしている可能性もあります。int型キャスト（配列をインデックスするためにアイテムを使用するときに呼び出される）は、ソートキーを返すためにオーバーロードされる可能性がありますが、

Answer 2

あなたのバージョンは良いアプローチだと思います。私はこのコードサンプルを書いた人がおそらく他のソートアルゴリズムのための類似のコードサンプルを書いていたと考えています。は別の "スクラッチスペース"が必要です - 多くのソートアルゴリズムがあります。

また、「結果を生成する」と「結果を所定の場所に移動する」を区別すると、アルゴリズムが説明しやすくなるかもしれません。もしそうなら、私は同意しませんが、詳細なコメントは彼が教育学を念頭に置いていることを明確にしています。

• あなたはiを宣言するのを忘れ：言わ
  は、お使いのバージョンでいくつかのマイナーな問題があります。
• ハードコードされたARRAY_SIZEを使用するのではなく、配列の長さをパラメータとして使用する必要があります。 （コードサンプルでは、​​この問題は文字列を使用することで回避されるので、終端のヌルバイトまで繰り返すことができます）
• これは主観的かもしれませんが、while (countingArray[i]--)ではなく、for (int j = 0; j < countingArray[i]; ++j)と書くことがより明確です。