Problema Bubblesort Vettore C++

di
markolino1997
il
9 risposte
M
markolino1997
Pochi posts
Iscritto da
dic, 2013
Messaggi:
30

Problema Bubblesort Vettore C++

Salve ragazzi, ho un problema con il bubblesort ottimizzato. Algoritmo pari pari al libro, applicato su un vettore di 10 elementi. Come potete vedere, non fa altro che "smistarli", eppure mi chiedo dove sia l'errore, visto che sembra essere scritto bene sotto il profilo logico. Voi che ne pensate? 

#include <iostream>
#include <cstdlib>
using namespace std;

int main(){
	int i,k,s,n=10;
	int V[n];
	for(i=0;i<n;i++){
		cout<<"Inserisci elemento "<<i<<": ";
		cin>>V[i];
	}
	
	do{
		s=0;
		for(i=0;i<n-1;i++){
			if(V[i]>V[i+1]){
				k=V[i];
				V[i]=V[i+1];
				V[i+1]=k;
				s=i;
			}
		}
		if(s>0){
			n=s;
		}
	}while(s!=0);

	for(i=0;i<10;i++){
		cout<<V[i]<<endl;
	}
	
	system("pause");
	return 0;
}

9 Risposte

  • S
    smalldragon
    Molto attivo
    Iscritto da
    nov, 2008
    Messaggi:
    895

    Re: Problema Bubblesort Vettore C++

    Allora il problema stà nel ciclo do
    in quanto l'algoritmo prevede che solo quando non ci sono più scambi deve terminare.
    cosi come fai tu invece una volta che ha fatto qualche scambio il programma termina.
    usa un ciclo while
    adesso apporta le modifiche
    se hai problemi posta le modifiche che hai fatto e ti daro una mano
  • W
    Worht
    Pochi posts
    Iscritto da
    mar, 2014
    Messaggi:
    47

    Re: Problema Bubblesort Vettore C++

    Per far funzionare l'algoritmo basta cancellare l' "if(s>0){ n=s;}"if dopo il for che scambia i valori.
    Tu devi immaginare la variabile "s" come un valore booleano, con 0=FALSE e qualunque altro valore= TRUE. Quando il programma entra nel ciclo for, cambia il valore di "s" da 0 a "i" solo se fa almeno uno scambio, nel caso contrario "s"=0, quindi non ci sono valori da ordinare, quindi esci dal do...while e stampi l'array.
    Ond'evitare confusione ti consiglio di cambiare l'assegnazione "s=i" in "s=1", di modo che 0=FALSE e 1=TRUE, e non dai adito ad equivoci.
  • M
    markolino1997
    Pochi posts
    Iscritto da
    dic, 2013
    Messaggi:
    30

    Re: Problema Bubblesort Vettore C++

    Ma così facendo diventerà un semplice bubblesort, molto poco efficiente. Quell'n=s serve a fare in modo che al prossimo ciclo il controllo verrà effettuato dalla prima posizione fino a quella in cui è stato effettuato l'ultimo scambio, sfruttando il fatto che col bubblesort gli elementi più grandi vanno man mano giù.
  • W
    Worht
    Pochi posts
    Iscritto da
    mar, 2014
    Messaggi:
    47

    Re: Problema Bubblesort Vettore C++

    markolino1997 ha scritto:

    Ma così facendo diventerà un semplice bubblesort, molto poco efficiente. Quell'n=s serve a fare in modo che al prossimo ciclo il controllo verrà effettuato dalla prima posizione fino a quella in cui è stato effettuato l'ultimo scambio, sfruttando il fatto che col bubblesort gli elementi più grandi vanno man mano giù.
    Perdonami, non avevo letto il "migliorato", in tal caso basta che fai "n=s+1", ricordati che nella condizione del for i<n-1.
    Ah, un piccolo consiglio di forma: 
    cout<<"Inserisci elemento "<<i+1<<": ";
  • M
    markolino1997
    Pochi posts
    Iscritto da
    dic, 2013
    Messaggi:
    30

    Re: Problema Bubblesort Vettore C++

    Fatto, ora funziona Però potresti spiegarmi il perchè dell'n=s+1?
  • W
    Worht
    Pochi posts
    Iscritto da
    mar, 2014
    Messaggi:
    47

    Re: Problema Bubblesort Vettore C++

    markolino1997 ha scritto:

    Fatto, ora funziona Però potresti spiegarmi il perchè dell'n=s+1?
    Te l'ho scritto, perchè nel for c'è la condizione i<n-1. Ora, essendo che non puoi cambiarla, o avresti un errore nel primo ciclo di scambi in quanto tenteresti di scambiare con array[10] che non esiste, l'unica soluzione è quello di incrementare di un unità l'assegnazione del nuovo n. Se difatti l'array è ordinato da 8 in poi, l'ultimo scambio sarà tra array[7] ed array[8], con i=s=n=7. Dunque il ciclo successivo controllerebbe sino ad i<n-1, ovvero sino ad i=5, lasciando l'elemento di indice 7 li dov'è, indipendentemente dal suo valore. Spero di essere stato chiaro xD
    Ps: quando non ti trovi con i programmi, prova a fare un disegno passo passo di quello che accade, stando molto attento alle condizioni, vedrai che l'errore salta subito fuori.
  • M
    markolino1997
    Pochi posts
    Iscritto da
    dic, 2013
    Messaggi:
    30

    Re: Problema Bubblesort Vettore C++

    Hai ragione! Anche per il fatto della tabella di traccia, il bello è che ho avuto a che fare con algoritmi molto più difficili di questo e non ci sono stati problemi. A quanto pare quell'n=s è molto fraintendibile ahah grazie per l'aiuto!
  • W
    Worht
    Pochi posts
    Iscritto da
    mar, 2014
    Messaggi:
    47

    Re: Problema Bubblesort Vettore C++

    markolino1997 ha scritto:

    Hai ragione! Anche per il fatto della tabella di traccia, il bello è che ho avuto a che fare con algoritmi molto più difficili di questo e non ci sono stati problemi. A quanto pare quell'n=s è molto fraintendibile ahah grazie per l'aiuto!
    A quanto ho capito lo hai preso da un libro, immagino che sul libro sia scritto in Pascal o P-Like, quando lo traduci devi sempre stare attento agli indici xD È molto più sempre scriverli da 0 che tradurli secondo me.
  • M
    markolino1997
    Pochi posts
    Iscritto da
    dic, 2013
    Messaggi:
    30

    Re: Problema Bubblesort Vettore C++

    Nono, il libro è proprio scritto in C++ xD
Devi accedere o registrarti per scrivere nel forum
9 risposte