Bubble sort di una lista

di
paki
il
8 risposte
P
paki
Pochi posts
Iscritto da
gen, 2010
Messaggi:
3

Bubble sort di una lista

Ragazzi help! vi sintetizzo le dichiarazioni e il main e poi vi scrivo la funzione...la compila e la esegue, ma fa solo il primo scambio! non cicla eppure mi sembra di aver fatto tutto bene! dateci un'occhiata!

//dichiarazioni
struct LISTA{int dato;
struct LISTA *prossimo;};
typedef struct LISTA lista;
typedef lista *puntalista;

void bubblesort_c(puntalista); //prototipo funzione

void main(){
bubblesort_c(listapunt); //chiamata alla funzione
}

void bubblesort_c(puntalista listapunt){
int i,j,temp,elementi=0;
puntalista cursore,precedente,successivo;
cursore=listapunt;
while(cursore!=NULL){ //mi determino di quanti elementi è fatta la lista
elementi++;
cursore=cursore->prossimo;}
for(i=0;i<=elementi-2;i++){//algoritmo bubblesort
precedente=listapunt;
successivo=listapunt;
successivo=successivo->prossimo;
for(j=0;j<=elementi-2;j++){ //scorro la lista
if(precedente->dato>successivo->dato){ //scambio
temp=precedente->dato;
precedente->dato=successivo->dato;
successivo->dato=temp;}
}
precedente=successivo; //sembra che il problema sia qui!
successivo=successivo->prossimo;}}

8 Risposte

  • I
    Intel
    Utente Attivo
    Iscritto da
    nov, 2003
    Messaggi:
    431

    Re: Bubble sort di una lista

    Ciao, il problema sta nelle prime due righe del primo for. Infatti ad ogni iterazione sposti i puntatori "precedente" e "successivo" all'inizio della lista. Cosi` facendo scambi sempre la prima coppia di elementi. Per risolvere il problema ti basta spostare prima del for i primi 2 assegnamenti.

    P.s. la prossima volta che vuoi inserire del codice leggibile, indentalo bene e mettilo in un blocco code. Cosi` ti possiamo aiutare meglio

    Cmq ti posto il codice corretto:
    

void bubblesort_c(puntalista listapunt){

	int i,j,temp,elementi=0;
	puntalista cursore,precedente,successivo;
	
	cursore=listapunt;

	while(cursore!=NULL){ //mi determino di quanti elementi è fatta la lista
		
		elementi++;
		cursore=cursore->prossimo;

	}

	/* righe spostate da dentro il for */
	precedente=listapunt;
	successivo=listapunt;
	successivo=successivo->prossimo;
	/* ------------------------------- */

	for(i=0;i<=elementi-2;i++){//algoritmo bubblesort
		
		
		for(j=0;j<=elementi-2;j++){ //scorro la lista

			if(precedente->dato > successivo->dato){ //scambio
				temp=precedente->dato;
				precedente->dato=successivo->dato;
				successivo->dato=temp;
	
			}

		}

		precedente=successivo;
		successivo=successivo->prossimo;
		
	}
	
}
    ciao ciao
  • P
    paki
    Pochi posts
    Iscritto da
    gen, 2010
    Messaggi:
    3

    Re: Bubble sort di una lista

    L'ho provato...così mi fa 1 giro della lista...per esempio se nella lista ho 8 7 3 8 5 9 1 lui mi restituisce 7 3 8 5 8 1 9...ha fatto solo un giro della lista, operando gli scambi...
  • P
    paki
    Pochi posts
    Iscritto da
    gen, 2010
    Messaggi:
    3

    Re: Bubble sort di una lista

    Intel ci sei? ho trovato il problema! allora quando finisce il for che ha come indice j per intenderci, abbiamo che successivo=NULL e prossimo='ultimo elemento' quindi quando esce da quel for, verifica la condizione del precedente, che fa ricominciare quello di prima, ma bisogna rinizializzare i puntatori! ecco perchè io, sbagliando, avevo messo quelle istruzioni dopo il primo for, che tu mi hai spostato. quindi? così vanno bene perchè prima non ciclava nemmeno una volta...come si fa?
  • I
    Intel
    Utente Attivo
    Iscritto da
    nov, 2003
    Messaggi:
    431

    Re: Bubble sort di una lista

    Si, scusami, con una lettura veloce del tuo codice non mi ero accorto dell'errore. Cmq devi tenerti 2 puntatori alla tua lista. Uno per l'indice i e l'altro per l'indice j, che per chiarezza chiamo rispettivamente pi e pj. pi accede all'elemento successivo alla lista ad ogni fine iterazione della i, mentre pj viene sempre resettato. Ti metto in pseudocodice la soluzione.
    
int main(){
	
	int i, j;
	int n = NUMERO_ELEMENTI;
	lista l;
	
	pi = l;
	pj = l;
	
	for (i = 0; i < n; i++){
		
		for (j = 0; j < n; j++){
			
			if (pi->valore > pj->valore){
				
				[scambia pi con pj];
				
			}
			
			pj = pj->successivo;
			
		}
		
		pi = pi->successivo;
		pj = lista;
		
	}
	
	return 0;
	
}
    Intel
  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: Bubble sort di una lista

    @paki
    il bubble-sort è molto semplice e l'applicazione alle liste, come tu esegui, è di una
    semplicità estrema. Sarebbe stata più interessante una funzione di scambio puntamenti
    anziché scambiare il contenuto e poi passare un puntatore ad una funzione di comparazione... 
    
void bubblesort_c(puntalista listapunt)
{
  int i,j,temp,elementi=0;
  puntalista cursore,precedente,successivo;

  
  //mi determino di quanti elementi è fatta la lista
  cursore=listapunt;
  while(cursore!=NULL)
  { 
    elementi++;
    cursore=cursore->prossimo;
  }
  
  while (elementi > 1)
  {
    precedente=listapunt;
    prossimo  =(precedente) ? precedente->next : NULL;

    for (i=0;i<elementi-1;i++)
    {
      if(precedente->dato > successivo->dato)
      {
        //scambio
        temp=precedente->dato;
        precedente->dato=successivo->dato;
        successivo->dato=temp;
      }
      precedente=prossimo;
      prossimo  =(precedente) ? precedente->next : NULL;
    }
    elementi--;
  }
}
    Saluti,
    Max
  • I
    Intel
    Utente Attivo
    Iscritto da
    nov, 2003
    Messaggi:
    431

    Re: Bubble sort di una lista

    Io non critico mai la semplicità di un algoritmo. Nessuno è nato "imparato" e penso che siamo partiti tutti così. Per quanto riguarda lo scambio di puntatori alternativo a quello per valori, dal punto di vista algoritmico non cambia nulla. La complessità rimane sempre O(n^2). Invece, sarebbe interessante per paki vedere algoritmi più efficienti che ordinano un insieme di dati in meno tempo o provare quelli già implementati, disponibili nelle librerie standard del c/c++.

    Intel
  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: Bubble sort di una lista

    @Intel,
    Quando hai poche strutture da ordinare quest'algoritmo è più che sufficiente!
    Mille elementi vengono ordinati sulla mio server a 0,033581 secondi utilizzando lo scambio ptr bidirezionale

    Per quanto riguardo lo spostamento dei puntatori -ed il puntamento alla funzione compare- è utile qualora si voglia implementare una funzione utile ad ordinare qualsiasi tipo di dati (o più indici) su qualsiasi tipo di struttura. Inoltre quando si utilizzano liste con 'grossi' blocchi di memoria si evita lo 'spreco' della temporanea.

    La mia rimane, o vuole essere, una critica costruttiva per poter scrivere una volta per tutte una funzione standard!

    Saluti,
    Max
  • I
    Intel
    Utente Attivo
    Iscritto da
    nov, 2003
    Messaggi:
    431

    Re: Bubble sort di una lista

    Hai assolutamente ragione. Stavo solo dicendo che se si vuole imparare non ci si deve fermare a questo, ma si deve andare avanti
Devi accedere o registrarti per scrivere nel forum
8 risposte