Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Bubble Sort e scambi virtuali...
Forum - C/C++ - Bubble Sort e scambi virtuali...

Avatar
MagoAntò (Normal User)
Rookie


Messaggi: 42
Iscritto: 07/02/2009

Segnala al moderatore
Postato alle 19:51
Mercoledì, 26/05/2010
Ciao a tutti!

Sono alle prese con il seguente programma:

"Implementare in C l'algoritmo Exchange Sort (Bubble Sort) su un array di struttura in versione iterativa mediante scambi virtuali."

Citando la prof, per scambi virtuali intendiamo: "i dati non sono fisicamente spostati perchè si opera tramite puntatori. Scambiamo solo i puntatori".

Questo è il mio codice:

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define sizearray 10
  5.  
  6. struct dato {
  7.        
  8.         char chiave;
  9.         short info;
  10. };
  11.  
  12. typedef struct dato DATO;
  13.  
  14. void bubble_sort_it_sv (DATO array []);
  15.  
  16. void main ()
  17. {
  18.         DATO array [sizearray];
  19.        
  20.         short i;
  21.  
  22.         for (i=0; i<sizearray; i++)
  23.         {
  24.                 printf ("Digita la chiave del %hd-simo elemento: ", i+1);
  25.                 fflush (stdin);
  26.                 scanf ("%c", &array[i].chiave);
  27.                 printf ("Digita l'informazione del %hd-simo elemento: ", i+1);
  28.                 fflush (stdin);
  29.                 scanf ("%hd", &array[i].info);
  30.                 printf ("\n");
  31.         }
  32.  
  33.         system ("CLS");
  34.  
  35.         printf ("Le informazioni inserite sono:\nCHIAVE\t\tINFO\n");
  36.  
  37.         for (i=0; i<sizearray; i++)
  38.         {
  39.                 printf ("%c\t\t%hd\n", array[i].chiave, array[i].info);
  40.         }
  41.  
  42.         printf ("\n");
  43.         system ("PAUSE");
  44.  
  45.         bubble_sort_it_sv (array);
  46.  
  47.         printf ("\nL'array ordinato e':\nCHIAVE\t\tINFO\n");
  48.  
  49.         for (i=0; i<sizearray; i++)
  50.         {
  51.                 printf ("%c\t\t%hd\n", array[i].chiave, array[i].info);
  52.         }
  53.  
  54.         printf ("\n");
  55. }
  56.  
  57. void bubble_sort_it_sv (DATO array [])
  58. {
  59.         DATO *punt [sizearray]; // array di puntatori
  60.         DATO temp;
  61.         short i, scambio;
  62.  
  63.         for (i=0; i<sizearray; i++)
  64.         {
  65.                 punt[i] = &array[i]; /* ogni i-sima componente dell'array punt contiene l'indirizzo di memoria dell'i-sima
  66.                                                          componente dell'array i */
  67.         }
  68.  
  69.         scambio = 0;
  70.  
  71.         while (scambio < sizearray-1) /* L'ultima componente non verrà analizzata poichè, dopo il primo for, sarà già in posizione */
  72.         {
  73.                 for (i=0; i<sizearray-1; i++) /* Dopo il primo for, il massimo sarà già alla fine dell'array */
  74.                 {
  75.                         if ((punt[i])->chiave  > (punt[i+1])->chiave)
  76.                         {
  77.                                 temp = *punt[i];
  78.                                 *punt[i] = *punt[i+1];
  79.                                 *punt[i+1] = temp;
  80.                         }
  81.                 }
  82.  
  83.                 scambio ++;
  84.         }
  85. }



Così com'è, l'algoritmo funziona. Secondo voi, può essere migliorato? Ho qualche dubbio sui puntatori... 8-| Grazie in anticipo per la risposta! :)

PM Quote
Avatar
Poggi Marco (Member)
Guru


Messaggi: 969
Iscritto: 05/01/2010

Segnala al moderatore
Postato alle 22:27
Mercoledì, 26/05/2010
Ciao!

Ho letto il tuo programma, e posso suggerirti due modifiche:

1-> Evita come la peste l' istruzione fflush(stdin) - il suo comportamento, in questi casi può essere imprevedibile.-
Come alternativa, ti suggerisco:
Codice sorgente - presumibilmente C/C++

  1. while (gerchar() != '\n') ;



2-> L' algoritmo d' ordinamento, poò essere migliorato in modo che ad ogni ciclo venga individuato il valore massimo.

Ecco il sorgente:

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define sizearray 10
  5.  
  6. struct dato {
  7.  
  8.     char chiave;
  9.     short info;
  10. };
  11.  
  12. typedef struct dato DATO;
  13.  
  14. void bubble_sort_it_sv (DATO [], int);
  15.  
  16. int main (int argc, char *argv[])
  17. {
  18.     DATO array [sizearray];
  19.  
  20.     short i;
  21.  
  22.     for (i=0; i<sizearray; i++)
  23.     {
  24.         printf ("Digita la chiave del %hd-simo elemento: ", i+1);
  25.         array[i].chiave=getchar();
  26.         while (getchar()!='\n') ; // svuota il buffer
  27.         printf ("Digita l'informazione del %hd-simo elemento: ", i+1);
  28.         scanf ("%hd", &array[i].info);
  29.         while (getchar()!='\n') ;  // svuota il buffer
  30.         printf ("\n");
  31.     }
  32.  
  33.     system ("CLS");
  34.  
  35.     printf ("Le informazioni inserite sono:\nCHIAVE\t\tINFO\n");
  36.  
  37.     for (i=0; i<sizearray; i++)
  38.     {
  39.         printf ("%c\t\t%hd\n", array[i].chiave, array[i].info);
  40.     }
  41.  
  42.     printf ("\n");
  43.     system ("PAUSE");
  44.  
  45.     bubble_sort_it_sv (array, sizearray);
  46.  
  47.     printf ("\nL'array ordinato e':\nCHIAVE\t\tINFO\n");
  48.  
  49.     for (i=0; i<sizearray; i++)
  50.     {
  51.         printf ("%c\t\t%hd\n", array[i].chiave, array[i].info);
  52.     }
  53.  
  54.     printf ("\n");
  55.     return 0;
  56. }
  57.  
  58. void bubble_sort_it_sv (DATO array [], int fine)
  59. {
  60.     DATO *punt [fine]; // array di puntatori
  61.     DATO temp;
  62.     short i, scambio;
  63.  
  64.     for (i=0; i<fine; i++)
  65.     {
  66.         punt[i] = &array[i]; /* ogni i-sima componente dell'array punt contiene l'indirizzo di memoria dell'i-sima
  67.                              componente dell'array i */
  68.     }
  69.  
  70.     scambio = fine-1;  /* L'ultima componente non verrà analizzata poichè, dopo il primo for, sarà già in posizione */
  71.  
  72.     while (scambio > 1 )
  73.     {
  74.         for (i=0; i<scambio; i++) /* Dopo il primo for, il massimo sarà già alla fine dell'array */
  75.         {
  76.             if ((punt[i])->chiave  > (punt[i+1])->chiave)
  77.             {
  78.                 temp = *punt[i];
  79.                 *punt[i] = *punt[i+1];
  80.                 *punt[i+1] = temp;
  81.             }
  82.         }
  83.  
  84.         scambio--;
  85.     }
  86. }


PM Quote