O（n）ソートアルゴリズム

Question

ここでは、0からsizeの範囲の整数でしか動作しない非常に恐ろしいソートアルゴリズムがあります。私は大量のデータセットに対してこのようなアルゴリズムを使用しません。それは、非常に多くのメモリを必要とするため、大きなアルゴリズムを使用します。つまり、このアルゴリズムは技術的にO（n）時間に実行されないでしょうか？

おかげ

#include <iostream> 
#define size 33 

int main(){ 

    int b[size]; 

    int a[size] = {1,6,32,9,3,7,4,22,5,2,1,0}; 

    for (int n=0; n<size; n++) b[n] = 0; 

    for (int n=0; n<size; n++){ 
     if (size <= a[n]) throw std::logic_error("error"); 
     b[a[n]]++; 
    } 

    int x = 0; 
    for (int n=0; n<size; n++){ 
     for (int t=0; t<b[n]; t++){ 
      a[x] = n; 
      x++; 
     } 
    } 

    for (int n=0; n<size; n++) printf("%d ",a[n]); 
} 

Answer 1

はO（N）あります。具体的にはO（n + k）です。ここで、nは入力配列の要素数、kはケースサイズの入力範囲です。配列内にあるすべての要素を数えています。そして、元の配列に何回も順番に格納します。このアルゴリズムは、カウントソートと呼ばれます。

Answer 2

radix sortのバリエーションを表示しています。 bucket sortに加えて、これらのアルゴリズムは、比較に基づいていないソートの主な例です。これは、O(n logn)よりも優れた複雑さを提供します。

ただし、実装は実際にはO(n + size)です。