Forum - C/C++
- Bubble Sort e scambi virtuali...
MagoAntò (Normal User)
Rookie
Messaggi: 42
Iscritto: 07/02/2009
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++
#include <stdio.h>
#include <stdlib.h>
#define sizearray 10
struct dato {
char chiave;
short info;
} ;
typedef struct dato DATO;
void bubble_sort_it_sv ( DATO array [ ] ) ;
void main ( )
{
DATO array [ sizearray] ;
short i;
for ( i= 0 ; i< sizearray; i++ )
{
printf ( "Digita la chiave del %hd-simo elemento: " , i+ 1) ;
fflush ( stdin ) ;
scanf ( "%c" , & array[ i] .chiave ) ;
printf ( "Digita l'informazione del %hd-simo elemento: " , i+ 1) ;
fflush ( stdin ) ;
scanf ( "%hd" , & array[ i] .info ) ;
printf ( "\n " ) ;
}
system ( "CLS" ) ;
printf ( "Le informazioni inserite sono:\n CHIAVE\t \t INFO\n " ) ;
for ( i= 0 ; i< sizearray; i++ )
{
printf ( "%c\t \t %hd\n " , array[ i] .chiave , array[ i] .info ) ;
}
printf ( "\n " ) ;
system ( "PAUSE" ) ;
bubble_sort_it_sv ( array) ;
printf ( "\n L'array ordinato e':\n CHIAVE\t \t INFO\n " ) ;
for ( i= 0 ; i< sizearray; i++ )
{
printf ( "%c\t \t %hd\n " , array[ i] .chiave , array[ i] .info ) ;
}
printf ( "\n " ) ;
}
void bubble_sort_it_sv ( DATO array [ ] )
{
DATO * punt [ sizearray] ; // array di puntatori
DATO temp;
short i, scambio;
for ( i= 0 ; i< sizearray; i++ )
{
punt[ i] = & array[ i] ; /* ogni i-sima componente dell'array punt contiene l'indirizzo di memoria dell'i-sima
componente dell'array i */
}
scambio = 0 ;
while ( scambio < sizearray- 1 ) /* L'ultima componente non verrà analizzata poichè, dopo il primo for, sarà già in posizione */
{
for ( i= 0 ; i< sizearray- 1 ; i++ ) /* Dopo il primo for, il massimo sarà già alla fine dell'array */
{
if ( ( punt[ i] ) - > chiave > ( punt[ i+ 1] ) - > chiave)
{
temp = * punt[ i] ;
* punt[ i] = * punt[ i+ 1] ;
* punt[ i+ 1] = temp;
}
}
scambio ++ ;
}
}
Così com'è, l'algoritmo funziona. Secondo voi, può essere migliorato? Ho qualche dubbio sui puntatori...
Grazie in anticipo per la risposta!
Poggi Marco (Member )
Guru
Messaggi: 969
Iscritto: 05/01/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++
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++
#include <stdio.h>
#include <stdlib.h>
#define sizearray 10
struct dato {
char chiave;
short info;
} ;
typedef struct dato DATO;
void bubble_sort_it_sv ( DATO [ ] , int ) ;
int main ( int argc, char * argv[ ] )
{
DATO array [ sizearray] ;
short i;
for ( i= 0 ; i< sizearray; i++ )
{
printf ( "Digita la chiave del %hd-simo elemento: " , i+ 1) ;
array[ i] .chiave = getchar ( ) ;
while ( getchar ( ) ! = '\n ' ) ; // svuota il buffer
printf ( "Digita l'informazione del %hd-simo elemento: " , i+ 1) ;
scanf ( "%hd" , & array[ i] .info ) ;
while ( getchar ( ) ! = '\n ' ) ; // svuota il buffer
printf ( "\n " ) ;
}
system ( "CLS" ) ;
printf ( "Le informazioni inserite sono:\n CHIAVE\t \t INFO\n " ) ;
for ( i= 0 ; i< sizearray; i++ )
{
printf ( "%c\t \t %hd\n " , array[ i] .chiave , array[ i] .info ) ;
}
printf ( "\n " ) ;
system ( "PAUSE" ) ;
bubble_sort_it_sv ( array, sizearray) ;
printf ( "\n L'array ordinato e':\n CHIAVE\t \t INFO\n " ) ;
for ( i= 0 ; i< sizearray; i++ )
{
printf ( "%c\t \t %hd\n " , array[ i] .chiave , array[ i] .info ) ;
}
printf ( "\n " ) ;
return 0 ;
}
void bubble_sort_it_sv ( DATO array [ ] , int fine)
{
DATO * punt [ fine] ; // array di puntatori
DATO temp;
short i, scambio;
for ( i= 0 ; i< fine; i++ )
{
punt[ i] = & array[ i] ; /* ogni i-sima componente dell'array punt contiene l'indirizzo di memoria dell'i-sima
componente dell'array i */
}
scambio = fine- 1 ; /* L'ultima componente non verrà analizzata poichè, dopo il primo for, sarà già in posizione */
while ( scambio > 1 )
{
for ( i= 0 ; i< scambio; i++ ) /* Dopo il primo for, il massimo sarà già alla fine dell'array */
{
if ( ( punt[ i] ) - > chiave > ( punt[ i+ 1] ) - > chiave)
{
temp = * punt[ i] ;
* punt[ i] = * punt[ i+ 1] ;
* punt[ i+ 1] = temp;
}
}
scambio-- ;
}
}