Bubble sort di lista di interi

MattINfo

il 27 dic 2023, 12:12

5 risposte

MattINfo

Pochi posts

Iscritto da: dic, 2023

Messaggi:: 4

Bubble sort di lista di interi

27 dic 2023, 12:21

Salve

Sto cercando di effettuare un bubblesort che mi ordini la mia lista di interi ma il mio algoritmo non funziona, qualcuno potrebbe correggermelo?
Allego anche la struct della lista che ho creato che sarebbe meglio non modificare se possibile per comodità scolastica.
input provato: 2 5 4 8 5
output: 5 4 5 8 2
Grazie mille


void BubbleSort(Lista l){
    Lista precendete, successivo;
    int elementi=lunghezzalista(&l),tmp;

    precendete=l;
    successivo=l;
    successivo=successivo->next;

    for(int i=0;i<elementi-2;i++){
        for(int j=0;j<elementi-2;j++){
            if(precendete->dato > successivo->dato){
				tmp=precendete->dato;
				precendete->dato=successivo->dato;
				successivo->dato=tmp;
			}
        }
        precendete=successivo;
		successivo=successivo->next;
    }

}

typedef int Dato;
typedef struct nodo{
    Dato dato;
    struct nodo *next;
}Nodo;
typedef Nodo* Lista;

5 Risposte

dobby

Utente Attivo

Iscritto da: nov, 2021

Messaggi:: 70

Re: Bubble sort di lista di interi

27 dic 2023, 13:18

Aggiungo le risposte nei commenti del codice

void BubbleSort(Lista l){
    Lista precendete, successivo;
    int elementi=lunghezzalista(&l),tmp;
    // Come mai calcoli la lunghezza della lista?

    precendete=l;
    successivo=l;
    successivo=successivo->next;

    // precedente e succesivo che valori hanno, quando li aggiorni 
    // durante il ciclo, sicuro sia giusto, io userei un altro ciclo non il for
    for(int i=0;i<elementi-2;i++){
        for(int j=0;j<elementi-2;j++){
            if(precendete->dato > successivo->dato){
				tmp=precendete->dato;
				precendete->dato=successivo->dato;
				successivo->dato=tmp;
			}
        }
        
        // queste due assegnazioni fuori dal secondo ciclo, a cosa servono?
        precendete=successivo;
		successivo=successivo->next;
    }

}

M
MattINfo
Pochi posts
Iscritto da
dic, 2023
Messaggi:
4
Re: Bubble sort di lista di interi
27 dic 2023, 13:27
1 la lunghezza della lista la utilizzo nel for, la ho calcolata per quello
2 precendete e successivo dovrebbero avere lo stesso valore della prima “casella” della lista all'inizio e per poi modificarlo, successivo dovrebbe avere quello dopo.
3 anche io utilizzerei un ciclo while solo che non ero sicuro di come implementarlo
4 quelle due assegnazioni fuori dal ciclo in teoria dovrebbe far scorrere la lista anche se non so se funziona

questo algoritmo è un algoritmo che ho trovato online e ho provato ad adattare al mio programma che guardando e riguardando ora come ora non sono sicuro funzioni. Se hai altre idee di algoritmo sono ben accette
Grazie mille
D
dobby
Utente Attivo
Iscritto da
nov, 2021
Messaggi:
70
Re: Bubble sort di lista di interi
27 dic 2023, 18:32
Leggi bene i due cicli for, nel ciclo interno mi controlli se precedente è maggiore si successivo, ma quando viene aggiornato il loro contenuto? Sicuro che “elementi-2” sia corretto?

io, per non sapere ne leggere ne scrivere, inizializzerei la variabile successivo prima dell'inizio del secondo ciclo poi la farei variare all'interno.
```
for(int i=0;i<elementi-2;i++)
  {
    for(int j=0;j<elementi-2;j++)
     {
      if(precendete->dato > successivo->dato)
       {
		tmp=precendete->dato;
		precendete->dato=successivo->dato;
		successivo->dato=tmp;
	   }
     }
    precendete=successivo;
    successivo=successivo->next;
  }
```
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1237
Re: Bubble sort di lista di interi
28 dic 2023, 18:03
Magari in seguito entro nel merito del codice postato, ma nell'ordinamento di una lista ipotizzo che lo scopo debba essere quello di lavorare sui nodi e non di limitarsi a scambiare i dati. Per me quindi al di là dell'algoritmo c'è proprio un errore concettuale di fondo. Sbaglio?
LukeSkyWalker
Pochi posts
Iscritto da
dic, 2020
Messaggi:
34
Re: Bubble sort di lista di interi
29 dic 2023, 13:39
28/12/2023 - Nippolo ha scritto:
Magari in seguito entro nel merito del codice postato, ma nell'ordinamento di una lista ipotizzo che lo scopo debba essere quello di lavorare sui nodi e non di limitarsi a scambiare i dati. Per me quindi al di là dell'algoritmo c'è proprio un errore concettuale di fondo. Sbaglio?
Sampei ha ragione, dovresti scambiare i nodi e non i valori interi.
Cmq sia i bugs ce li hai sotto il naso.
```
void BubbleSort(Lista l){
    Lista precendete, successivo;
    int elementi=lunghezzalista(&l),tmp;

    precendete=l;
    successivo=l;
    successivo=successivo->next;

    for(int i=0;i<elementi-2;i++){
        for(int j=0;j<elementi-2;j++){
            if(precendete->dato > successivo->dato){
				tmp=precendete->dato;
				precendete->dato=successivo->dato;
				successivo->dato=tmp;
			}
        }
        precendete=successivo;
		successivo=successivo->next;
    }
}
```
Seguimi a livello logico:
Tu inserisci i valori input provato: 2 5 4 8 5 “per il momento lasicamo stare cosa ti restituisce”.
prendiamo in considerazione i primi due interi 2 e 5
il flusso è:
1. entri nella funzione bubblesort
2. inizializzi le variabili
3. entri nel primo for con indice “i”
4. entri nel secondo for con indice “j”
5. esegui l'if …. che valore hanno le variabili che confronti ? precendete->dato = 2 e successivo->dato = 5 . 2 Non è maggiore di 5 …. che succede ? … che non entri nell'if
6. un altro giro di ciclo for con indice “j”
7. ri-esegui l'if e a questo giro, che valori hanno le variabili che confrontari (visto che precedentemente non sei entrato nel' if ) ? …
Non voglio fare il saccente, o il maestrino, ma se hai difficolta' o non riesci a venirne a capo disegna un flow chart (diagramma di flusso)
dal disegno è tutto più chiaro, una volta che il diagramma di flusso è corretto il codice lo scrivi in un nano secondo “senza bugs” .
Ci sono due bugs :
1. il primo “te l'ho detto”,
2. il secondo è conseguenza del primo

Devi accedere o registrarti per scrivere nel forum

5 risposte