Bonjour tout le monde ! J'essaye d'implémenter un algorithme quick sort mais je suis bloqué, mon code fonctionne seulement pour les tableaux de longueur inférieur ou égale à 5, au delà le programme rentre dans une boucle infinie. Si une personne voyait et pouvait m'expliquer mon erreur je lui en serait reconnaissant. Merci !
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void QuickSort(int* T, int g, int d)
{
int p = T[g+(d-g)/2];
int k1 = g;
int k2 = d;
int val;
if (g < d)
{
while (k1 < k2)
{
while (T[k1] < p)
{
k1++;
}
while (T[k2] > p)
{
k2--;
}
if (k1 < k2)
{
val = T[k1];
T[k1] = T[k2];
T[k2] = val;
}
}
QuickSort(T, g, k2-1);
QuickSort(T, k2+1, d);
}
}
int main()
{
int *t;
int N;
printf("Saisir la taille de N : ");
scanf("%d", &N);
t = malloc(N*sizeof(int));
srand(time(NULL));
for (int i = 0; i < N; i++)
{
t[i] = rand()%100;
printf("%d ", t[i]);
}
QuickSort(t, 0, N-1);
printf("\n");
for(int i = 0; i < N; i++)
{
printf("%d ", t[i]);
}
free(t);
printf("Memory free ! \n");
return 0;
}
Bonjour ! Je viens de regarder cinq minutes en ajoutant des 'printf' partout, ça a l'air assez aléatoire... Souvent, ça boucle à partir de 5 valeurs, mais pas toujours. J'ai réussi à le faire tourner avec 11 valeurs (c'est mon record).
C'est un algorithme que tu as écrit toi même ou recopié ?
En tout cas, ça boucle dans le « while (k1 < k2) » lorsqu'on n'a ni « T[k1] < p » ni « T[k2] > p », du coup il ne modifie pas k1 et k2 : on ne peut pas sortir de la boucle.
J'ai un cas où k=1, k2=5, et T[1] = T[5] = 20. Eh bien p=20 aussi, du coup les deux conditions ne sont pas réalisées :
- Est-ce que T[k1] < p ? Non : T[1] = 20 = p.
- Est-ce que T[k2] < p ? Non : T[2] = 20 = p.
k1 et k2 ne sont donc pas incrémentés (ou décrémentés) et ça boucle.
Je soupçonne que ça arrive chaque fois qu'un élément est en double dans le tableau (mais je ne suis pas sûr). Ça expliquerait que ça boucle plus souvent quand N est grand : il y a plus de chances d'avoir des doublons.
Et si on remplace les inégalités strictes par des inégalités larges (< par <=) ? Non, ça ne va pas.
Il faut probablement revoir l'algorithme.
Je poste un extrait du programme avec les affichages rajoutés. Je te recommande d'en faire autant pour bien comprendre ce qui se passe (ou d'utiliser un débogueur avec des points d'arrêt) :
documenter ses fonctions, ce n'est pas un luxe. Et c'est sympa pour ceux qui doivent relire, par exemple ceux à qui on demande de l'aide...
Par exemple on pourrait avoir
/*
Ordonne le tableau T entre les indices g et d compris
(ordre croissant ?)
*/
void QuickSort(int* T, int g, int d)
Ca coûte pas cher et ça permet de ne pas se poser la question de savoir si on veut que l'indice d soit compris, ou pas. A partir de là ça explique la bizarrerie éventuelle de l'appel dans le main (N-1).
---
Les tests sur des tableaux aléatoires, c'est bien joli, mais ça ne fait pas le boulot. Ton programme ne marche pas même pour un tableau de 2 éléments égaux. Essaie avec le main :
int main()
{
int t[] = {1, 1};
QuickSort(t, 0, 1);
printf("fini\n");
return 0;
}
=> ça boucle.
Comme quoi la déclaration "ça marche pour moins de 5 éléments", c'est un peu optimiste.
C'est ta méthode pour partager le tableau qui ne va pas.
---
Comme maintenant tu as un contre-exemple avec deux éléments seulement, je te conseille de faire tourner ton algorithme à la main (tout le monde déteste faire ça, je sais, mais y a que 2 éléments c'est une affaire de quelques secondes) en confrontant honnêtement
ce que tu aurais voulu qu'il fasse
ce qu'il fait réellement.
Comme ça tu vois précisément à quel moment ça déraille.
---
Encore un conseil : sortir le code qui s'occupe de partager le tableau dans une fonction à part. Comme ça
1. le code de QuickSort est plus simple
void QuickSort(int* T, int g, int d)
{
if (g < d) {
int m = Partager(T, g, d);
QuickSort(T, g, m-1);
QuickSort(T, m+1, d);
}
}
2. Avec
/*
permute les éléments du tableau T, entre les
indices g et d compris,
et retourne un indice m entre g et d tel que
si g <= i <= m alors T[i] <= T[m]
si m <= i <= d alors T[i] >= T[m]
*/
int Partager(int T[], int g, int d)
{
...
}
Ca permettra aussi d'écrire du code qui ne teste que la fonction de partage.
- Edité par michelbillaud 9 décembre 2023 à 19:08:15
Coder l'algorithme trouvé quelque part n'a que très peu d'intérêt.
Ce qui est formateur, c'est de retrouver un algo et de le coder à partir du *principe général* :
Bouger les éléments du tableau pour avoir les petits d'un côté, les grands de l'autre
Ordonner les petits
Ordonner les grands
La première étape laisse des possibilités de variantes. Si on décide d'utiliser un "pivot", on peut choisir la première valeur du tableau, celle du milieu, une prise au hasard, la plus proche de la moyenne, etc
- Edité par michelbillaud 9 décembre 2023 à 20:24:12
Bonjour ! Je viens de regarder cinq minutes en ajoutant des 'printf' partout, ça a l'air assez aléatoire... Souvent, ça boucle à partir de 5 valeurs, mais pas toujours. J'ai réussi à le faire tourner avec 11 valeurs (c'est mon record).
C'est un algorithme que tu as écrit toi même ou recopié ?
En tout cas, ça boucle dans le « while (k1 < k2) » lorsqu'on n'a ni « T[k1] < p » ni « T[k2] > p », du coup il ne modifie pas k1 et k2 : on ne peut pas sortir de la boucle.
J'ai un cas où k=1, k2=5, et T[1] = T[5] = 20. Eh bien p=20 aussi, du coup les deux conditions ne sont pas réalisées :
- Est-ce que T[k1] < p ? Non : T[1] = 20 = p.
- Est-ce que T[k2] < p ? Non : T[2] = 20 = p.
k1 et k2 ne sont donc pas incrémentés (ou décrémentés) et ça boucle.
Je soupçonne que ça arrive chaque fois qu'un élément est en double dans le tableau (mais je ne suis pas sûr). Ça expliquerait que ça boucle plus souvent quand N est grand : il y a plus de chances d'avoir des doublons.
Et si on remplace les inégalités strictes par des inégalités larges (< par <=) ? Non, ça ne va pas.
Il faut probablement revoir l'algorithme.
Je poste un extrait du programme avec les affichages rajoutés. Je te recommande d'en faire autant pour bien comprendre ce qui se passe (ou d'utiliser un débogueur avec des points d'arrêt) :
Le Tout est souvent plus grand que la somme de ses parties.