Discussione:Bubble sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 42:
*** Il programma in C così com'è non funziona. Basta applicarlo al seguente array : [2,1] oppure a [3,2,1] . Un bug banale dipende dal fatto che l'elemento 0 non viene mai toccato. Anche correggendo questo piccolo bug però il programma non funzionerebbe comunque poichè il primo elemento verrebbe scambiato al più una sola volta. IMHO i due cicli devono essere opposti, anche se devo ammettere che sono anni che non leggo libri di informatica. bye [[Utente:DanGarb|DanGarb]] 11:31, Lug 21, 2005 (CEST)<br/>
****Sulla cella 0 avevi chiaramente ragione, sui cicli invertiti posso dirti... fidati! Spiego il bubblesort in corsi di C da anni, ce ne sono N varianti equivalenti da tutti i punti di vista. Vero che forse sarebbe piu' chiaro che tutti gli esempi di codice si rifacessero alla stessa versione (cosa che adesso non e'), e magari potrei aggiungere una sezione ''varianti e ottimizzazioni''... che ne dite?[[Utente:Moongateclimber|Moongateclimber]]
***** Scusate se insisto, fidarsi è bene ma non fidarsi è meglio :-]. Insisto perchè dal mio punto di vista è palese che il programma in C non faccia il suo dovere, ovvero non ordini i vettori. Per una verifica certa occorrerebbe implementarlo e testarlo. Qui proverò con qualche ragionamento e con un controesempio a convincervi: (anche se contrariamente a quanto ho detto prima, il programma può essere implementato con entrambi i cicli crescenti; in questa maniera :'''for (b=0; b<elemN-a-1; ++b)'''). Il ragionamento che confuta l'attuale versione: per ''a=0'' il primo elemento dell'array è confrontato col secondo ed eventualmente scambiato; per i successivi valori di ''a'' il primo elemento non viene più toccato... quindi ==> se l'elemento minore del sistema non è in prima o seconda posizione ne consegue che non potrà mai arrivare in prima posizione. Il controesempio : array = (2,3,1) a=0 b=0 --> (''2'',''3'',1) a=0 b=1 (2,''1'',''3'') --> a=1 b=1 (2,''1'',''3'') --> fine programma . Bye [[Utente:DanGarb|DanGarb]] 13:40, Lug 21, 2005 (CEST)
******Scusami, hai assolutamente ragione anche questa volta. Il problema e' che se entrambi i cicli vanno in avanti, quello + interno dovrebbe avere una forma del tipo: "for(b=0; b<nElem-1; b++)", o ancora meglio (ottimizzato) "for(b=0; b<nElem-1-a; b++)", cioe' l'indice deve partire da 0 (non da a). Ho avuto un po' fretta nel risponderti, chiedo venia :-((
Prego, accomodati. se la pagina viene esageratamente lunga, si fa un articolo a parte, tipo [[Varianti del Bubblesort in C]], e si inserisce prima del codice la nota
:''Il codice riportato è a fini didattici. Per una descrizione completa e approfondita, mirata anche all'ottimizzazione, vedi l'articolo [[Varianti del Bubblesort in C]]''
| |||