Discussion :

[shirohige]

Bonjour,

J'essaye de réaliser le tri rapide mais de temps en temps mon programme boucle infini. Je ne suis pas très à l'aise avec la récursion:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
void            my_swap(int *s1, int *s2)
{
  int s = *s1;
 
  *s1 = *s2;
  *s2 = s;
}
 
void            tri_rapide(int nb, int *tab)
{
  if (nb < 2)
    return;
  int           pivot = rand()%nb;
  int           beg = 0;
  int           end = nb-1;
 
 
  pivot = tab[pivot];
  while (beg < end)
    {
      while (tab[beg] < pivot)
        beg++;
      while (tab[end] > pivot)
        end--;
      my_swap(tab + beg, tab + end);
    }
  tri_rapide(beg, tab);
  tri_rapide(nb-end, tab + end);
}

Merci pour votre aide.

Edit:
Je pense que cela arrive lorsque j'ai deux nombre egaux dans ma liste.
Edit 2:
J'ai ajouter cette ligne avant le swap et ça à l'air d'être stable:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
      if ((tab[end] == tab[beg]) && end != beg)
        beg++;
      else
        my_swap(tab + beg, tab + end);

[imperio]

C'est mega dangereux ton affaire !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
while (tab[beg] < pivot)
        beg++;

Gros risque de lecture en memoire la ! Rajoute comme condition que beg doit aussi etre inferieur a la taille de ton tableau pour securiser ca.

T'as marque que ca fonctionnait donc j'ai pas cherche plus loin.