repositories
/
Algorithmic_C.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
TP3: Implement the generic merge sort algorithm.
[Algorithmic_C.git]
/
TP3
/
tp3.c
diff --git
a/TP3/tp3.c
b/TP3/tp3.c
index 75c31950ff86a0b98200864c0c36c4cd4413ffb7..7fa3dd729b217aed17587a554eb1fab8e1b0262a 100644
(file)
--- 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;
void TriFusion(int T[], int n) {
int i = 0, j = 0, k = 0;
+ int milieu = n/2;
int* T1;
int* T2;
if (n > 1) {
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];
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++;
if (T1[k] <= T2[j]) {
T[i] = T1[k];
i++;
@@
-33,12
+35,12
@@
void TriFusion(int T[], int n) {
j++;
}
}
j++;
}
}
- while (k <
n/2
) {
+ while (k <
milieu
) {
T[i] = T1[k];
i++;
k++;
}
T[i] = T1[k];
i++;
k++;
}
- while (j < n
/2
) {
+ while (j < n
- milieu
) {
T[i] = T2[j];
i++;
j++;
T[i] = T2[j];
i++;
j++;
@@
-49,7
+51,8
@@
void TriFusion(int T[], int n) {
}
int main() {
}
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);
int tabSize = sizeof(T)/sizeof(T[0]);
AfficheTab(T, tabSize);