[C++] Problemi con bubble sort di array di record

[Forzajuve]

Ciao,
ho un problema con il bubble sort di un array di record. Dovrebbe essere una semplice agenda telefonica,i cui contatti dovrebbero essere ordinati per ordine alfabetico, cosa che non accade. Inoltre ci sono problemi con la ricerca (aggiungendo elementi non trova elementi che precedentemente trovava). A quanto pare, ci sono problemi con il bubble sort.

Qui il main:
#include <iostream>
#include "geststringhe.h"
#include "record.h"
#include <cstdlib>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
elenco e;
int r,elementi,utente,c_pos;
anagrafica a1;
stringa c_nome;
inizializza_elenco(r);
cout<<"Premere 1 per inserire un elemento\n";
cout<<"Premere 2 per cercare un elemento\n";
cout<<"Premere 3 per stampare il numero di un contatto (se presente)\n";
cout<<"Premere 4 per stampare tutti i contatti\n";
cout<<"Digitare 0 per uscire\n";
cin>>utente;
while (utente!=0)
{ if (utente==1)
{ cout<<"Quanti elementi vuoi inserire?\n";
cin>>elementi;
for (int i=1; i<=elementi;i++)
inserisci_elemento(e,r,a1);
cin>>utente;
}

else if (utente==2)
{
bubble_sort_nome(e,r);
cout<<"Quale nome vuoi cercare?\n";
cin>>c_nome;
c_pos=ricerca_binaria_record(e,r,c_nome);
if (c_pos!=-1)
cout<<"L'elemento è presente in posizione "<<c_pos<<"\n";
else
cout<<"L'elemento non è presente\n";
cin>>utente;
}
else if (utente==3)
{bubble_sort_nome(e,r);
cout<<"Di quale nome vuoi cercare i numeri?\n";
cin>>c_nome;
c_pos=ricerca_binaria_record(e,r,c_nome);
if (c_pos!=-1)
{
cout<<"Nome: "<<e[c_pos].nome<<"\n";
cout<<"Numero del fisso: "<<e[c_pos].fisso<<"\n";
cout<<"Numero del cellulare: "<<e[c_pos].cellulare<<"\n";
}
else
cout<<"Il contatto non è presente\n";
cin>>utente;

}
else if (utente==4)
{bubble_sort_nome(e,r);
for (int i=0; i<r; i++)
{ cout<<"Nome: "<<e[i].nome<<"\n";
cout<<"Numero del fisso: "<<e[i].fisso<<"\n";
cout<<"Numero del cellulare: "<<e[i].cellulare<<"\n";
}
cin>>utente;
}
else if (utente==0)
return 0;
else
{
cout<<"Inserire un numero tra 0 1 2 3 4\n";
cin>>utente;
}


}






}

Qui l'header dei sottoprogrammi per record
#ifndef record_h
#define record_h
#define R 256
#include <string.h>
typedef struct anagrafica
{stringa nome;
int fisso;
int cellulare;
};
typedef anagrafica elenco [R];

void inizializza_elenco(int&);
void inserisci_elemento(elenco,int&,anagrafica);
void bubble_sort_nome(elenco,int);
void scambia_record (anagrafica&,anagrafica&);
int ricerca_binaria_record (elenco,int, stringa);









#endif
E qui il .cpp dei sottoprogrammi
#include <iostream>
#include "geststringhe.h"
#include "record.h"
#include <cstdlib>

using namespace std;

void inizializza_elenco (int& riempimento)
{riempimento=0;
}

void inserisci_elemento(elenco e, int& riempimento, anagrafica a1)
{cout<<"Inserisci il nome\n";
cin>>a1.nome;
cout<<"Inserisci il numero del telefono fisso\n";
cin>>a1.fisso;
cout<<"Inserisci il numero del cellulare\n";
cin>>a1.cellulare;
e[riempimento]=a1;
riempimento=riempimento++;
}

void bubble_sort_nome (elenco e, int riempimento)
{bool fatto_scambio;
while (fatto_scambio)
{fatto_scambio=false;
for (int i=0; i<riempimento-1; i++)

{
if (strcmp(e[i].nome,e[i+1].nome)>0)
{scambia_record(e[i],e[i+1]);
fatto_scambio=true;}}
}
}

void scambia_record (anagrafica& a1,anagrafica& a2)
{anagrafica temp;
temp=a1;
a1=a2;
a2=temp;
}

int ricerca_binaria_record (elenco e,int riempimento, stringa nome)
{int sup,inf,medio;
sup=riempimento-1;
inf=0;
while (inf<=sup)
{
medio=(sup+inf)/2;
if (strcmp(e[medio].nome,nome)==0)
return medio;
else if (strcmp(e[medio].nome,nome)>0)
inf=medio+1;
else
sup=medio-1;
}
return -1;
}

[cenarius_88]

Ciao, premetto che ho letto grossolanamente il programma quindi non so se facendo queste modifiche risolverai...

Ho trovato 2 errori grossolani

Nella funzione di inserimento.... fai

riempimento=riempimento++;

Questa operazione è sbagliata in logica... non so se funziona, ma... l'incremento postfisso ha una precedenza inferiore rispetto all'assegnazione... per cui tu prima assegni a riempimento, riempimento stesso, e dopo lo incrementi (non so se l'incremento viene salvato)... per un futuro utilizza l'incremento prefisso (che è più sicuro)... ed inoltre non ha senso usare l'incremento se poi lo assegni a se stesso... modificalo così

++incremento;


Nel bubblesort crei una variabile booleana


bool fatto_scambio;


Essa non ha alcun valore esplicito, ad ogni chiamata della funzione potrebbe valere 8504877 che comunque il programma vedrebbe come TRUE, oppure 0, che è FALSE.... quindi il consiglio è di cambiare come segue


void bubble_sort_nome (elenco e, int riempimento)
{bool fatto_scambio=false;
while (!fatto_scambio)


Prova con queste piccole modifiche, il resto del programma sembra corretto...

[Forzajuve]

Ciao, premetto che ho letto grossolanamente il programma quindi non so se facendo queste modifiche risolverai...

Ho trovato 2 errori grossolani

Nella funzione di inserimento.... fai

riempimento=riempimento++;

Questa operazione è sbagliata in logica... non so se funziona, ma... l'incremento postfisso ha una precedenza inferiore rispetto all'assegnazione... per cui tu prima assegni a riempimento, riempimento stesso, e dopo lo incrementi (non so se l'incremento viene salvato)... per un futuro utilizza l'incremento prefisso (che è più sicuro)... ed inoltre non ha senso usare l'incremento se poi lo assegni a se stesso... modificalo così

++incremento;


Nel bubblesort crei una variabile booleana


bool fatto_scambio;


Essa non ha alcun valore esplicito, ad ogni chiamata della funzione potrebbe valere 8504877 che comunque il programma vedrebbe come TRUE, oppure 0, che è FALSE.... quindi il consiglio è di cambiare come segue


void bubble_sort_nome (elenco e, int riempimento)
{bool fatto_scambio=false;
while (!fatto_scambio)


Prova con queste piccole modifiche, il resto del programma sembra corretto...

Ciao, ti ringrazio per l'aiuto.
Per la prima parte, non l'ho modificato. Il programma funziona in tutte le componenti che richiedono il sottoprogramma, quindi ho dato per scontato che funzioni. Comunque terrò presente il tuo consiglio e nei prossimi programmi cercherò di fare in quest'altro modo :) .
Per la seconda parte ho provato a sostituire e... funziona! Ti ringrazio molto, però vorrei sapere anche perchè logicamente le due cose non sono equivalenti... a me lo sembrano. Se testo prima il verificarsi di una variabile e poi la metto false o testo direttamente la negazione della variabile stessa, non è uguale? :)

EDIT: Ho controllato il programma... forse può dipendere dal non avere messo inizialmente fattoscambio=true? Era una cosa che davo per scontato di aver fatto e non è così... Puoi confermare che non ponendo la variabile booleana come true, una volta che poi la pongo come false non mi trovo più? Ciao

EDIT2: Più precisamente... così:

{bool fatto_scambio=true;
while (fatto_scambio)
{
fatto_scambio=false;
for (int i=0; i<riempimento-1; i++)

{
if (strcmp(e[i].nome,e[i+1].nome)>0)
{scambia_record(e[i],e[i+1]);
fatto_scambio=true;}}
}
}

[vendettaaaaa]

Ciao, premetto che ho letto grossolanamente il programma quindi non so se facendo queste modifiche risolverai...

Ho trovato 2 errori grossolani

Nella funzione di inserimento.... fai

riempimento=riempimento++;

Questa operazione è sbagliata in logica... non so se funziona, ma... l'incremento postfisso ha una precedenza inferiore rispetto all'assegnazione... per cui tu prima assegni a riempimento, riempimento stesso, e dopo lo incrementi (non so se l'incremento viene salvato)... per un futuro utilizza l'incremento prefisso (che è più sicuro)... ed inoltre non ha senso usare l'incremento se poi lo assegni a se stesso... modificalo così

++incremento;


Nel bubblesort crei una variabile booleana


bool fatto_scambio;


Essa non ha alcun valore esplicito, ad ogni chiamata della funzione potrebbe valere 8504877 che comunque il programma vedrebbe come TRUE, oppure 0, che è FALSE.... quindi il consiglio è di cambiare come segue


void bubble_sort_nome (elenco e, int riempimento)
{bool fatto_scambio=false;
while (!fatto_scambio)


Prova con queste piccole modifiche, il resto del programma sembra corretto...
Concordo!
riempimento = riempimento++;

equivale a
riempimento = riempimento;
riempimento = riempimento + 1;

Riguardo alla variabile booleana, oltre a non essere inizializzata hai scelto un nome che indica la conclusione dell'operazione iterativa ma l'hai usata per indicare che il ciclo deve andare avanti finchè quella variabile è vera. Quindi o metti il ! davanti come ha fatto cenarius o scegli un nome opposto.

[vendettaaaaa]

Per la seconda parte ho provato a sostituire e... funziona! Ti ringrazio molto, però vorrei sapere anche perchè logicamente le due cose non sono equivalenti... a me lo sembrano. Se testo prima il verificarsi di una variabile e poi la metto false o testo direttamente la negazione della variabile stessa, non è uguale? :)
Il punto è che non l'hai inizializzata prima di testarla. Quando dichiari una variabile di tipo primitivo (int, bool, char, double) non le stai assegnando un valore, la stai posizionando nella RAM senza scrivere dentro ad essa un certo valore, quindi essa prende il valore che al momento stava nella RAM, del tutto casuale.

[Forzajuve]

Il punto è che non l'hai inizializzata prima di testarla. Quando dichiari una variabile di tipo primitivo (int, bool, char, double) non le stai assegnando un valore, la stai posizionando nella RAM senza scrivere dentro ad essa un certo valore, quindi essa prende il valore che al momento stava nella RAM, del tutto casuale.

Più o meno simile a quando si tenta di accedere con il vettore ad una zona di memoria non dedicata (ad esempio, eccedente la cardinalità)?

[vendettaaaaa]

Più o meno simile a quando si tenta di accedere con il vettore ad una zona di memoria non dedicata (ad esempio, eccedente la cardinalità)?
No, più o meno simile a quando accedi un vettore entro la cardinalità, ma non hai inizializzato il vettore (cioè fai:
int* a = new int[5];
cout << a[2];
).
Insomma, la RAM che viene dedicata al tuo programma quando lo esegui era in utilizzo da qualche altro processo prima di lui, quindi è sporca (nel senso che i bit della RAM non sono tutti a 0, ma hanno valori di ciò che c'è passato prima). Quando dichiari le variabili disponi le variabili nel pezzo di RAM che il sistema operativo ha dedicato al tuo programma. Devi poi inizializzare le variabili (scriverci un valore), prima di usarle in lettura, se vuoi che il tuo programma si comporti in modo definito e non casuale (cioè dipendente da cosa c'era prima).
Ricordati la differenza, in C e C++ (e anche C#):
- dichiarazione -> riservi nella memoria tanti byte quanti ne servono per memorizzare una variabile di un certo tipo (1 byte per char, 4 per int, 8 per double) -> es: int a; double d;
- definizione -> come la dichiarazione ma contestualmente setti un valore iniziale per la variabile -> es: int a = 1; double d = 6.;
- assegnamento -> scrivi nella zona di memoria delimitata dalla tua variabile un nuovo valore. La variabile a cui assegni deve essere già stata dichiarata/definita -> es:
int a; // dichiarazione
double d = 5.; // definizione
a = 3; 7// assegnamento
d = sin(87.); // assegnamento

Inizializzazione è un modo informale per dire "dare un valore ben definito ad una variabile prima di usarla".

Tornando al tuo codice, il tuo bool viene dichiarato, quindi messo in una zona di memoria di 8 bit che hanno valori casuali, e poi testato. Ma per testarlo il tuo programma deve prima dargli un valore, non deve testare quelli che c'era prima!

[Forzajuve]

No, più o meno simile a quando accedi un vettore entro la cardinalità, ma non hai inizializzato il vettore (cioè fai:
int* a = new int[5];
cout << a[2];
).
Insomma, la RAM che viene dedicata al tuo programma quando lo esegui era in utilizzo da qualche altro processo prima di lui, quindi è sporca (nel senso che i bit della RAM non sono tutti a 0, ma hanno valori di ciò che c'è passato prima). Quando dichiari le variabili disponi le variabili nel pezzo di RAM che il sistema operativo ha dedicato al tuo programma. Devi poi inizializzare le variabili (scriverci un valore), prima di usarle in lettura, se vuoi che il tuo programma si comporti in modo definito e non casuale (cioè dipendente da cosa c'era prima).
Ricordati la differenza, in C e C++ (e anche C#):
- dichiarazione -> riservi nella memoria tanti byte quanti ne servono per memorizzare una variabile di un certo tipo (1 byte per char, 4 per int, 8 per double) -> es: int a; double d;
- definizione -> come la dichiarazione ma contestualmente setti un valore iniziale per la variabile -> es: int a = 1; double d = 6.;
- assegnamento -> scrivi nella zona di memoria delimitata dalla tua variabile un nuovo valore. La variabile a cui assegni deve essere già stata dichiarata/definita -> es:
int a; // dichiarazione
double d = 5.; // definizione
a = 3; 7// assegnamento
d = sin(87.); // assegnamento

Inizializzazione è un modo informale per dire "dare un valore ben definito ad una variabile prima di usarla".

Tornando al tuo codice, il tuo bool viene dichiarato, quindi messo in una zona di memoria di 8 bit che hanno valori casuali, e poi testato. Ma per testarlo il tuo programma deve prima dargli un valore, non deve testare quelli che c'era prima!
Grazie, molto chiaro e gentile :D .
Ringrazio sia te che cenarius per l'aiuto. Avevo scritto il programma in 20 minuti poi ho perso 1 ora per trovare l'errore... Ad un certo punto si deve staccare per avere idee nuove :)

[vendettaaaaa]

Grazie, molto chiaro e gentile :D .
Ringrazio sia te che cenarius per l'aiuto. Avevo scritto il programma in 20 minuti poi ho perso 1 ora per trovare l'errore... Ad un certo punto si deve staccare per avere idee nuove :)
Figurati! Questo è uno dei bug più frequenti per chi usa da poco C e C++! E' un comportamento poco intuitivo, ma poi pian piano ti abitui :D
Cmq effettivamente questo forum è un bel posto per schiarirsi le idee.

[van9]

int a; // dichiarazione
double d = 5.; // definizione
a = 3; // assegnamento


Forse la cosa migliore è insegnarla tipo:

int a; // definizione-- stato arbitrario ovvero garbage (tranne nel caso di variabile globale, static, ...)
int a(0); // definizione e inizializzazione con parentesi -- stato iniziale
a = 42; // assegnamento -- modifica allo stato

che per me ha il vantaggio di far capire bene la differenza.

Tornando al tuo codice, il tuo bool viene dichiarato, quindi messo in una zona di memoria di 8 bit che hanno valori casuali, e poi testato. Ma per testarlo il tuo programma deve prima dargli un valore, non deve testare quelli che c'era prima!

"Zona di memoria generalmente equivalente all'unità facilmente indirizzabile dalla cpu" o simile non è meglio? Troppo presto per questo? Beh insomma se uno sta imparando con il C++, non è mai troppo presto per definizione... altrimenti che è partito a fare proprio da lì? :-P

[vendettaaaaa]

Forse la cosa migliore è insegnarla tipo:

int a; // dichiarazione -- stato arbitrario ovvero garbage (tranne nel caso di variabile globale, static, ...)
int a(0); // dichiarazione e inizializzazione -- stato iniziale
a = 42; // assegnamento -- modifica allo stato

che per me ha il vantaggio di far capire bene la differenza.
Molto conciso, mi piace, ma terrei il termine "definizione" che contrasta con "dichiarazione" come un .cpp contrasta col suo .h, rispettivamente. Userei anche l'uguale anzichè le parentesi, sia perchè è più naturale che per il fatto che le parentesi portano un po' di confusione con la dichiarazione di funzioni; piuttosto meglio le parentesi graffe del C++11!
"Zona di memoria generalmente equivalente all'unità facilmente indirizzabile dalla cpu" o simile non è meglio? Troppo presto per questo? Beh insomma se uno sta imparando con il C++, non è mai troppo presto per definizione... altrimenti che è partito a fare proprio da lì? :-P
Questa definizione non mi piace, troppo formale, meglio parlare più terra terra quando non si possono fare disegni o spiegare a quattr'occhi :D

[van9]

un piccolo appunto.. quelle sono definizioni (+ inizializzazioni eventualmente), le dichiarazioni non definiscono nulla in memoria (es. extern int a).

Giustissimo, colpa mia che ci metto tre ore per leggere e capire l'italiano-informatico e non e poi mi perdo sul più facile :(

[van9]

Molto conciso, mi piace, ma terrei il termine "definizione" che contrasta con "dichiarazione" come un .cpp contrasta col suo .h, rispettivamente. Userei anche l'uguale anzichè le parentesi, sia perchè è più naturale che per il fatto che le parentesi portano un po' di confusione con la dichiarazione di funzioni; piuttosto meglio le parentesi graffe del C++11!

Però le tonde richiamano anche l'inizializzazione diretta degli oggetti che si usa facilmente nei primi esempi introduttivi. Le graffe non saprei - a me fanno pensare subito alla definizione d'insieme/vettori. Ci devo pensare.

Sull'uguale più naturale in ambito imperativo stavo attaccare discorso ma tanto è una battaglia persa in partenza :-)

Questa definizione non mi piace, troppo formale, meglio parlare più terra terra quando non si possono fare disegni o spiegare a quattr'occhi :D

Ma si era giusto per non lasciare appeso il numero magico 8, non fosse altro che i neofiti li memorizzano e tirano fuori poi quando meno dovrebbero.

[vendettaaaaa]

un piccolo appunto.. quelle sono definizioni (+ inizializzazioni eventualmente), le dichiarazioni non definiscono nulla in memoria (es. extern int a).
Vero, ho appena letto lo standard! :eek:
Però le tonde richiamano anche l'inizializzazione diretta degli oggetti che si usa facilmente nei primi esempi introduttivi. Le graffe non saprei - a me fanno pensare subito alla definizione d'insieme/vettori. Ci devo pensare.
Io mi sto abituando alle graffe per la cosìddetta "uniform initialization": ovunque devi inizializzare, le graffe vanno bene, anche nei costruttori.
Però devo dire che ci sono almeno due aspetti che remano contro a questa definizione (probabilmente dovuti al fatto che i membri della commissione iso hanno deciso di mantenere retrocompatibilità a tutti i costi):
- se la tua classe A ha un costruttore che prende un int, e un double, puoi fare così:
A a{ 1, 2. };
però se c'è un overload del costruttore che prende un initializer_list, non va più bene :D
A a{ 1, 5. };
perchè 5. viene castato ad int e viene chiamato il costruttore che prende la initializer_list. Questo lo trovo scomodo usando semplicemente std::vector:
vector<int> v(5, 4); // crea un vector di dimensione 5, inizializzato con valore 4
vector<int> v{ 5, 4 }; // crea un vector di dimensione 2, con elementi 5 e 4
- E poi "per ragioni arcaiche legate al name lookup" (citando Stroustrup), non si possono usare le graffe per inizializzare i membri non statici di una classe (nuova feature del C++11):
class A
{
int a = 4; // ok
string s{ "yoyo" }; // non compila
vector<double> v(2, 666.); // ok
vector<double> v1{ 4., 5. }; // no
vector<double> v2 = { 4., 5. }; // sì
};
Sull'uguale più naturale in ambito imperativo stavo attaccare discorso ma tanto è una battaglia persa in partenza :-)
Spara pure! ;)