Vous devez vous connecter pour exécuter votre code.
Tri polymorphe (qsort-like)
B 10.5 — Implémentez la fonction merge_sort qui trie un tableau générique, sur le modèle de qsort. Utilisez memcpy de
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void merge(void *base, size_t lo, size_t mid, size_t hi, size_t size,
int (*compar)(const void *, const void *)) {
size_t n1 = mid - lo + 1, n2 = hi - mid;
void *left = malloc(n1 * size), *right = malloc(n2 * size);
memcpy(left, (char*)base + lo*size, n1*size);
memcpy(right, (char*)base + (mid+1)*size, n2*size);
size_t i = 0, j = 0, k = lo;
while (i < n1 && j < n2) {
if (compar((char*)left+i*size, (char*)right+j*size) <= 0)
memcpy((char*)base+k*size, (char*)left+i*size, size), i++;
else
memcpy((char*)base+k*size, (char*)right+j*size, size), j++;
k++;
}
while (i < n1) memcpy((char*)base+k*size, (char*)left+i*size, size), i++, k++;
while (j < n2) memcpy((char*)base+k*size, (char*)right+j*size, size), j++, k++;
free(left); free(right);
}
static void merge_sort_r(void *base, size_t lo, size_t hi, size_t size,
int (*compar)(const void *, const void *)) {
if (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
merge_sort_r(base, lo, mid, size, compar);
merge_sort_r(base, mid + 1, hi, size, compar);
merge(base, lo, mid, hi, size, compar);
}
}
void merge_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *)) {
if (nmemb > 1) merge_sort_r(base, 0, nmemb - 1, size, compar);
}
int main() {
int n;
scanf("%d", &n);
int arr[1000];
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
merge(arr, n);
return 0;
}