Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicit e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - aiuto ottimizzazione bubble sort
Forum - C/C++ - aiuto ottimizzazione bubble sort

Avatar
raeiko (Normal User)
Newbie


Messaggi: 1
Iscritto: 15/02/2009

Segnala al moderatore
Postato alle 14:43
Domenica, 15/02/2009
Salve ragazzi,
ho iniziato a studiare programmazione un mesetto fa e in questo momento sto iniziando a studiare gli arrays.

Uno degli esercizi che devo risolvere mi chiede di modificare l'algoritmo bubble sort per verificare se alla fine di ogni iterazione stato effettuato uno scambio o meno. Se non stato effettuato nessuno scambio il programma termina altrimenti necessaria almeno un'altra iterazione.

Ho provato a scrivere il codice (considerando che non posso usare n variabili booleane n flags xk non le ho ancora studiate) ma proprio non mi riesce.

Non cerco qualcuno che faccia i compiti per me,vorrei sono capire come procedere.

Grazie,
raeiko

Codice sorgente - presumibilmente Delphi

  1. /* Program that modifies the bubble sort array in fig. 6.15 */
  2.  
  3. #include <stdio.h>
  4. #define SIZE 10
  5.  
  6. int main ( void )
  7. {
  8.         int a[ SIZE ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 }; /* declare and initialize array a */
  9.         int pass; /* passes counter */
  10.         int i; /* comparisons counter */
  11.         int hold; /* temporary location used to swap arrays elements */
  12.         int NumOfComparisons = 0;
  13.  
  14.         printf( "Data items in original order:\n\n" );
  15.  
  16.         for ( i = 0; i < SIZE; i++ ){ /* display array output */
  17.                 printf( "%4d", a[ i ] );
  18.         } /* end of for loop */
  19.  
  20.         /* bubble sort */
  21.         for ( pass = 1; pass < SIZE; pass++ ){
  22.                 for ( i = 0; i < SIZE - 1; i++ ){
  23.                         if ( a[ SIZE ] == a[ 1 ] < a[ i + 1] ){
  24.                                 break;
  25.                         }
  26.  
  27.                         else if ( a[ i ] > a[ i + 1] ){
  28.                         hold = a[ i ];
  29.                         a[ i ] = a[ i + 1];
  30.                         a[ i + 1] = hold;
  31.                         pass++;
  32.                         }/* end of if */
  33.  
  34.         NumOfComparisons = NumOfComparisons + 1;
  35.  
  36.                 }/* end of inner for */
  37.  
  38.         }/* end of outer for */
  39.  
  40.         printf( "\nData items in ascending order:\n\n" );
  41.  
  42.         for ( i = 0; i < SIZE; i++ ){ /* output array in ascending order */
  43.                 printf( "%4d", a[ i ] );
  44.         }
  45.        
  46.         printf( "\n\n" );
  47.  
  48.         printf( "Number of comparisons: %d\n", NumOfComparisons );
  49.        
  50.        
  51. return 0;
  52. }


PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6109
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 19:16
Domenica, 15/02/2009
Questa istruzione:

Codice sorgente - presumibilmente C/C++

  1. if ( a[ SIZE ] == a[ 1 ] < a[ i + 1] )



E' logicamente incorretta, stai facendo una comparazione numerica e booleana, che viene eseguita sempre se a[1] < a[i + 1].

L'algoritmo comunque lo puoi esaminare qui: http://it.wikipedia.org/wiki/Bubble_sort



Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote