From 8c44116a9b634bea71f1526a72540baade817f7f Mon Sep 17 00:00:00 2001 From: Jerome Benoit Date: Sat, 4 Mar 2017 18:18:19 +0100 Subject: [PATCH] TP3: Implement the generic merge sort algorithm. Signed-off-by: Jerome Benoit --- TP3/tp3.c | 25 ++++++++++++++----------- 1 file changed, 14 insertions(+), 11 deletions(-) diff --git a/TP3/tp3.c b/TP3/tp3.c index 75c3195..7fa3dd7 100644 --- a/TP3/tp3.c +++ b/TP3/tp3.c @@ -7,22 +7,24 @@ void AfficheTab(int T[], int n) { } } -/** This merge sort implementation only work with 2^n array size */ void TriFusion(int T[], int n) { int i = 0, j = 0, k = 0; + int milieu = n/2; int* T1; int* T2; if (n > 1) { - T1 = malloc(n/2*sizeof(int)); - T2 = malloc(n/2*sizeof(int)); - for (int i = 0; i < n/2; i++) { + T1 = malloc(milieu*sizeof(int)); + T2 = malloc(((n - milieu)*sizeof(int))); + for (int i = 0; i < milieu; i++) { T1[i] = T[i]; - T2[i] = T[i + n/2]; } - TriFusion(T1, n/2); - TriFusion(T2, n/2); - while (k < n/2 && j < n/2) { + for (int i = milieu; i < n; i++) { + T2[i - milieu] = T[i]; + } + TriFusion(T1, milieu); + TriFusion(T2, n - milieu); + while (k < milieu && j < (n - milieu)) { if (T1[k] <= T2[j]) { T[i] = T1[k]; i++; @@ -33,12 +35,12 @@ void TriFusion(int T[], int n) { j++; } } - while (k < n/2) { + while (k < milieu) { T[i] = T1[k]; i++; k++; } - while (j < n/2) { + while (j < n - milieu) { T[i] = T2[j]; i++; j++; @@ -49,7 +51,8 @@ void TriFusion(int T[], int n) { } int main() { - int T[] = {2, 7, 2, 3, 4, 1, 5, 5}; + //int T[] = {2, 7, 2, 3, 4, 1, 5, 5}; + int T[] = {6, 2, 3, 1, 9, 10, 15, 13, 12, 17}; int tabSize = sizeof(T)/sizeof(T[0]); AfficheTab(T, tabSize); -- 2.34.1