repositories
/
Algorithmic_C.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
.gitignore: add more executable names
[Algorithmic_C.git]
/
TP3
/
tp3.c
diff --git
a/TP3/tp3.c
b/TP3/tp3.c
index 9198ad1e15ba4e245b857e124f170b28e609ee4f..52c2a6e398be161c61c1f8af0837bd79bbff265a 100644
(file)
--- a/
TP3/tp3.c
+++ b/
TP3/tp3.c
@@
-7,55
+7,57
@@
void AfficheTab(int T[], int n) {
}
}
}
}
-/** This quick 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;
int* T1;
int* T2;
-
- T1 = malloc(n/2*sizeof(int));
- T2 = malloc(n/2*sizeof(int));
if (n > 1) {
if (n > 1) {
- 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) {
- if (T1[k] <= T2[j]) {
+ 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++;
+ k++;
+ } else {
+ T[i] = T2[j];
+ i++;
+ j++;
+ }
+ }
+ while (k < milieu) {
T[i] = T1[k];
i++;
k++;
T[i] = T1[k];
i++;
k++;
- } else {
+ }
+ while (j < n - milieu) {
T[i] = T2[j];
i++;
j++;
T[i] = T2[j];
i++;
j++;
- }
- }
- while (k < n/2) {
- T[i] = T1[k];
- i++;
- k++;
- }
- while (j < n/2) {
- T[i] = T2[j];
- i++;
- j++;
- }
- free(T1);
- free(T2);
+ }
+ free(T1);
+ free(T2);
}
}
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);
- TriFusion(T,
tabSize);
+ TriFusion(T,
tabSize);
AfficheTab(T, tabSize);
AfficheTab(T, tabSize);