The problem of ordering a vector by Radix Sort is an example of a complexity algorithm P?
I do not know if it can be NP-Complete or just NP.
void radixsort(int vector[], int size) {
int i;
int *b;
int bigger= vector[0];
int exp = 1;
b = (int *)calloc(size, sizeof(int));
for (i = 0; i < size; i++) {
if (vetor[i] > bigger)
size= vector[i];
}
while (bigger/exp > 0) {
int bucket[10] = { 0 };
for (i = 0; i < size; i++)
bucket[(vetor[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = size- 1; i >= 0; i--)
b[--bucket[(vector[i] / exp) % 10]] = vector[i];
for (i = 0; i < size; i++)
vector[i] = b[i];
exp *= 10;
}
free(b);
}
Of course, it is in P! as its complexity is polynomial. Answer the other questions is related to the relation of these class of complexities. P is in NP. Hence, radix sort is in NP. As we do not know any polynomial agorithm for NP-Complete problems, hence, we do not know it is in NP-Complete or not and it is related to the known problem that is P = NP?