Comment mettre en œuvre tri à bulles en C.

Question

Je suis en train de mettre en œuvre l'algorithme de tri à bulles en C. Voici ce que j'ai jusqu'à présent:

#include<stdio.h> 
void bubble_sort(int m, int a[100000]); 
void main() 
{ 
int a[100000], i, m; 
FILE * be; 

be=fopen("be.txt","r"); 
for (i=0; !(feof(be)); ++i) 
    fscanf(be,"%i", a+i); 
m=i-1; 
bubble_sort(m ,a); 
fclose(be); 
} 
void bubble_sort(int m, int a[100000]) 
{ 
int i, ok, v, n=m;; 
for (;!ok;ok=1) 
{ 
    ok=0; 
    for (i=0;i<=m-1;++i) 
    { 
     if (*(a+i)>*(a+i+1)) { v=*(a+i); *(a+i)=*(a+i+1); *(a+i+1)=v; ok=0;} 
    } 
    m=m-1; 
} 

for (i=0; i<n; ++i) 
    printf("%i ", a[i]); 
} 

Mon pseudo code:

Bubblesort2(A) 
m:=length(A) - 1 
repeat 
    OK := true 
    for i := 0 to m-1 do 
     if Ai > Ai+1 then 
      Ai <=>Ai+1 
      OK := false 
    m := m - 1 
until OK 

Cette ne fonctionne pas correctement. Quel est le code pour implémenter le tri à bulles en C?

Answer 1

Essayez ceci:

void bubble_sort(int m, int a[100000]) 
{ 
    int i, ok = 0, v, n = m; 
    while (!ok) 
    { 
     ok = 1; 
     for (i=0; i < m-1; ++i) 
     { 
      if (*(a+i) > *(a+i+1)) 
      { 
       v = *(a+i); 
       *(a+i) = *(a+i+1); 
       *(a+i+1) = v; 
       ok = 0; 
      } 
     } 

     m--; 
    } 

    for (i = 0; i < n; ++i) 
     printf("%i ", a[i]); 
} 

Fondamentalement, on crée un ok (variables locales sont initialisées avec des valeurs de déchets). Vous devez également régler ok = 1 en entrant la boucle et ok = 0 si un swap a eu lieu. Il ne sert à rien d'utiliser une boucle for, une boucle while est plus lisible. m = m - 1 peut être remplacé par m--, c'est la même chose et vous écrivez moins de code.

Answer 2

Vous n'initialisez pas la valeur de ok, le comportement n'est donc pas défini.

Vous semblez mettre la valeur de ok à zéro, quoi qu'il arrive.

De plus, il est inutile d'optimiser le tri des bulles. Simplifiez-vous la tâche et travaillez. Si vous voulez de bonnes performances, vous ne devriez pas utiliser cet algorithme du tout.

Je vous suggère de lire le algorithm description sur Wikipedia, essayez de l'écrire en pseudo-code dans vos propres mots, assurez-vous de le comprendre, puis implémentez-le.

Answer 3

void bubble_sort(int m, int a[]) 
    { 
    int i, ok, v, n=m; 
    for (ok = 0;!ok;) 
    { 
     ok=1; 
     for (i=0;i<=m-1;++i) 
     { 
      if (*(a+i)>*(a+i+1)) { v=*(a+i); *(a+i)=*(a+i+1); *(a+i+1)=v; ok=0; } 
     } 
     m=m-1; 
    } 
    } 

Deux problèmes avec votre code:

1. ok a été undefined au début de sorte que son pas clair si la condition de la boucle sera satisfaite ou non.
2. La clause 3 (clause update) dans l'instruction for est exécutée après que le code entre parenthèses est itéré, mais avant de vérifier à nouveau la condition. Donc vous avez mis ok à 1 puis vérifié que ok = 0. Ainsi, il faisait seulement 1 itération.

Encore ce programme est un gâchis. La boucle for externe doit être une boucle while. Vous devez utiliser les accesseurs de tableau appropriés a[i] plutôt qu'un + i. L'espacement et les sauts de ligne dans votre code source ne coûtent rien.