Рассмотрим следующий код:
#define SIZE 12
void randomize(int* array, int array_size);
void print(int* array, int array_size);
void counting_sort(int* array, int array_size);
int get_max(int* array, int array_size);
void construct(int* sorted, int sorted_array_size, int* values);
int main(void)
{
srand(time(NULL));
int* array = (int*)malloc(sizeof(int) * SIZE);
randomize(array, SIZE);
print(array, SIZE);
counting_sort(array, SIZE);
free(array);
return 0;
}
void randomize(int* array, int array_size) {...}
void print(int* array, int array_size) {...}
void counting_sort(int* array, int array_size) {
int minVal, maxVal;
int* sorted = (int*)malloc(sizeof(int) * SIZE);
maxVal = get_max(array, array_size);
int* values = (int*)malloc(maxVal * sizeof(int));
memset(values, 0, maxVal * sizeof(int));
for (int i = 0; i < array_size; i++) {
values[array[i]]++;
}
construct(sorted, SIZE, values);
free(values);
free(sorted);
}
int get_max(int* array, int array_size) {...}
void construct(int* sorted, int array_size, int* values) {
for (int i = 0, j = 0; i < array_size; i++) {
while (!values[++j]);
sorted[i] = j;
--values[j];
}
print(sorted, SIZE);
}
main() объявляет массив, размер которого контролируется макросом SIZE. Затем есть несколько функций для рандомизации, печати и поиска максимального значения этого массива. После этого идет реализация самой Counting Sort, которая использует функцию construct(..) для создания отсортированного массива. Я проверял это несколько раз и не мог найти никаких ошибок. Однако это то, что меня беспокоит.
for (int i = 0, j = 0; i < array_size; i++) {
while (!values[++j]);...
У нас есть 2 внутренних цикла, и переменные в этих циклах увеличиваются. Это означает, что временная сложность функции construct(...) становится квадратичной, а не линейной. Проблема в том, что я не могу найти хороший способ отбросить все 0 в values[]. Линейные решения приветствуются.
Добавлен полный код:
#include <stdlib.h>
#include <cassert>
#include <time.h>
#include <limits.h>
#include <string.h>
#define SIZE 160
void randomize(int* array, int array_size);
void print(int* array, int array_size);
void counting_sort(int* array, int array_size);
int get_max(int* array, int array_size);
void construct(int* sorted, int sorted_array_size, int* values);
int main(void)
{
srand(time(NULL));
int* array = (int*)malloc(sizeof(int) * SIZE);
randomize(array, SIZE);
print(array, SIZE);
counting_sort(array, SIZE);
free(array);
return 0;
}
void randomize(int* array, int array_size) {
for (int i = 0; i < array_size; i++) {
array[i] = rand() % array_size;
}
}
void print(int* array, int array_size) {
for (int i = 0; i < array_size; i++) {
printf("%4d ", array[i]);
}
putchar('\n');
}
void counting_sort(int* array, int array_size) {
int minVal, maxVal;
int* sorted = (int*)malloc(sizeof(int) * SIZE);
maxVal = get_max(array, array_size);
int* values = (int*)malloc(maxVal * sizeof(int));
memset(values, 0, maxVal * sizeof(int));
for (int i = 0; i < array_size; i++) {
values[array[i]]++;
}
construct(sorted, SIZE, values);
free(values);
free(sorted);
}
int get_max(int* array, int array_size) {
int max = INT_MIN;
for (int i = 0; i < array_size; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
void construct(int* sorted, int array_size, int* values) {
for (int i = 0, j = 0; i < array_size; i++) {
while (!values[j]) {
++j;
}
sorted[i] = j;
--values[j];
}
print(sorted, SIZE);
}