TD4_DEV51_gentil/algo_tri.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Fonction de comparaison utilisée par qsort
int compare_ints(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

// Calcule la somme des éléments d'un bloc donné (dimension 1)
int sum_block(void* base, int block_size, int elem_size) {
    int sum = 0;
    for (int i = 0; i < block_size; i++) {
        sum += *((int*)(base + i * elem_size));
    }
    return sum;
}

// Fonction récursive de tri
void recursive_sort(
    void* data, int* dims, int dim_count, int elem_size
) {
    if (dim_count == 1) {
        // Cas de base : trier un tableau 1D
        qsort(data, dims[0], elem_size, compare_ints);
        return;
    }

    int sub_block_count = dims[0];
    int* sub_dims = dims + 1;

    // Calcul de la taille d'un sous-bloc
    int sub_block_size = 1;
    for (int i = 1; i < dim_count; i++) {
        sub_block_size *= dims[i];
    }

    // Trier récursivement chaque sous-bloc
    for (int i = 0; i < sub_block_count; i++) {
        void* sub_block = (char*)data + i * sub_block_size * elem_size;
        recursive_sort(sub_block, sub_dims, dim_count - 1, elem_size);
    }

    // Création de tableau temporaire pour le tri des blocs
    void** blocks = malloc(sub_block_count * sizeof(void*));
    int* sums = malloc(sub_block_count * sizeof(int));

    for (int i = 0; i < sub_block_count; i++) {
        blocks[i] = (char*)data + i * sub_block_size * elem_size;
        sums[i] = sum_block(blocks[i], sub_block_size, elem_size);
    }

    // Tri des blocs par somme croissante
    for (int i = 0; i < sub_block_count - 1; i++) {
        for (int j = i + 1; j < sub_block_count; j++) {
            if (sums[i] > sums[j]) {
                // Swap sums
                int tmp_sum = sums[i];
                sums[i] = sums[j];
                sums[j] = tmp_sum;

                // Swap blocks
                void* tmp_block = blocks[i];
                blocks[i] = blocks[j];
                blocks[j] = tmp_block;
            }
        }
    }

    // Réorganiser les données selon le nouvel ordre
    void* temp = malloc(sub_block_count * sub_block_size * elem_size);
    for (int i = 0; i < sub_block_count; i++) {
        memcpy((char*)temp + i * sub_block_size * elem_size,
               blocks[i], sub_block_size * elem_size);
    }
    memcpy(data, temp, sub_block_count * sub_block_size * elem_size);

    free(temp);
    free(blocks);
    free(sums);
}

// Fonction pour afficher un tableau 2D
void print_2d_array(int* arr, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%d ", arr[i * cols + j]);
        }
        printf("\n");
    }
}

int main() {
    // Exemple pour un tableau 2D : 3 lignes, 3 colonnes
    int dims[2] = {3, 3}; // 2D : 3x3
    int arr[3][3] = {
        {0, 3, 2},
        {9, 4, 5},
        {4, 1, 3}
    };

    printf("Avant tri :\n");
    print_2d_array((int*)arr, dims[0], dims[1]);

    recursive_sort((void*)arr, dims, 2, sizeof(int));

    printf("\nAprès tri :\n");
    print_2d_array((int*)arr, dims[0], dims[1]);

    return 0;
}