Есть задача c курса CS50
Your implemenation must sort, from smallest to largest, the array of numbers that it’s passed.
Assume that each of the array’s numbers will be non-negative and less than 65,536. But the array might contain duplicates.
The running time of your implementation must be in O(n), where n is the array’s size. Yes, linear! Keep in mind that 65,536 is a constant.
You may not alter the function’s declaration. Its prototype must remain:
void sort(int values[], int n);
Я написал реализацию задания следующим образом:
void sort(int values[], int n)
{
const int max = 65536;
int array[max];
//Заполняем массив нулями
for(int i = 0; i < max; i++)
array[i]=0;
//Прибавляем еденицу к ячейке массива array, у которой индекс соответсвует значению values[i]
for(int i = 0; i<n; i++)
array[values[i]]++;
//По порядку находим ненулевые ячейки, и по порядку присваиваем массиву values[] значения их индексов
for(int i=0, j=0; i< max; i++)
//учитываем так же вариант, в котором значения в массиве дублируются
while(array[i]>0)
{
values[j]=i;
j++;
array[i]--;
}
return;
}
Как мне теперь убедится в том, что мой алгоритм действительно выполняется за время O(n) ?
Потому что интуитивно мне он кажется сложнее чем сортировка вставками, которая занимает времени O(n^2):
for(int i=0; i<n-1; i++)
for(int j=i+1; j>0 && values[j]<values[j-1]; j--)
{
int temp=values[j-1];
values[j-1]=values[j];
values[j]=temp;
}
П.с. Есть ли тут какой-нибудь лимит задавания вопросов? А то мне кажется я уже начинаю надоедать своими нубскими вопросами тут :)
