main.cpp

#include <chrono>

const int total_objects = 10000;

int group_identifiers[] = {
        123,
        20,
        3,
        41,
        5893,
        12351,
        123,
        54353,
        6532,
        125,
        342367,
        2342,
        12333,
        64645,
        631341
};

struct Object {
    int property_to_sort_by;
    int property_to_group_by;
};

struct Object_Group {
    Object** objects;
    int group_size;
};

int compare_objects(const void* a, const void* b) {
    Object* left = (Object*) a;
    Object* right = (Object*) b;

    return left->property_to_sort_by - right->property_to_sort_by;
}

int compare_object_pointers(const void* a, const void* b) {
    Object* left = *((Object**) a);
    Object* right = *((Object**) b);

    return left->property_to_sort_by - right->property_to_sort_by;
}

Object objects[total_objects];

void fill_objects_with_random_data() {
    for (int i = 0; i < total_objects; i++) {
        Object* object = objects + i;
        object->property_to_group_by = group_identifiers[rand() % ARRAY_SIZE(group_identifiers)];
        object->property_to_sort_by = rand();
    }
}

void group_objects(Object_Group* object_groups) {
    for (int i = 0; i < total_objects; i++) {
        Object* object = objects + i;
        int group_identifier = object->property_to_group_by;

        for (int j = 0; j < ARRAY_SIZE(group_identifiers); j++) {
            if (group_identifiers[j] == group_identifier) {
                Object_Group& group = object_groups[j];

                group.objects = (Object**) realloc(group.objects, (++group.group_size) * sizeof(Object*));
                group.objects[group.group_size - 1] = object;

                break;
            }
        }
    }
}

void sort_group_internals(Object_Group* object_groups) {
    for (int i = 0; i < ARRAY_SIZE(group_identifiers); i++) {
        Object_Group group = object_groups[i];

        qsort(group.objects, group.group_size, sizeof(Object*), compare_object_pointers);
    }
}

double get_avg(double* values, int length) {
    double sum = 0;

    for (double* start = values; start != values + length; start++) {
        sum += (*start);
    }

    return sum / length;
}

int main() {
    const int runs = 1000;
    double t1[runs];
    double t2[runs];

    for (int i = 0; i < runs; i++) {
        auto start = std::chrono::steady_clock::now();

        Object_Group object_groups[ARRAY_SIZE(group_identifiers)];
        memset(object_groups, 0, sizeof(object_groups));

        fill_objects_with_random_data();
        qsort(objects, total_objects, sizeof(Object), compare_objects);
        group_objects(object_groups);

        double millis = std::chrono::duration <double, std::milli> (std::chrono::steady_clock::now() - start).count();

        t1[i] = millis;
    }

    for (int i = 0; i < runs; i++) {
        auto start = std::chrono::steady_clock::now();

        Object_Group object_groups[ARRAY_SIZE(group_identifiers)];
        memset(object_groups, 0, sizeof(object_groups));

        fill_objects_with_random_data();
        group_objects(object_groups);
        sort_group_internals(object_groups);

        double millis = std::chrono::duration <double, std::milli> (std::chrono::steady_clock::now() - start).count();

        t2[i] = millis;
    }


    printf("Avg1: %f\n", get_avg(t1, runs));
    printf("Avg2: %f\n", get_avg(t2, runs));

    return 0;
}