Discussione:Bubble sort

Bubble sort
Argomento di scuola secondaria di II grado
Materia	informatica
Dettagli
Dimensione della voce	15 184 byte
Progetto Wikipedia e scuola italiana

Non è così inutile!

L'articolo dice:

si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità.

Tuttavia il bubble-sort ha i suoi usi, in computer Graphics ad esempio viene utilizzata quando si mantiene una lista di oggetti ordinati per distanza da un punto o per profondità lungo un asse. Solitamente la lista rimane quasi del tutto ordinata e accadono piccoli cambiamenti ad ogni time-frame. Il bubble-sort in questa occasione, come in altri casi, ha tempi di esecuzione più brevi di altri algoritmi più avanzati. Inoltre può essere implementato in modo che venga eseguita una singola iterazione per elemento per ogni frame in modo da avere tempi di esecuzione O(n) quando non è fondamentale che la lista sia perfettamente ordinata. FedeDevi.

Lo XOR

Usare lo XOR nel C++ per scambiare dati è sconsigliato da qualunque manuale di buona programmazione: un compilatore ottimizzante fa meglio da solo. e poi esiste std::swap. Provvedo a modificare e metto qui il codice incriminato

template <class Type> void bubbleSort(Type *array, size_t length)
{
  int i, j;
  for(i = length - 1; i > 0; i--)
    for(j = 0; j < i; j++)
      if(array[j] > array[j+1]) /* compara gli elementi vicini */
      {
         array[j] ^= array[j+1]; // Usa XOR per scambiare i valori più velocemente,
         array[j+1] ^= array[j]; //  ma solo quando sei sicuro
         array[j] ^= array[j+1]; //  di poterlo fare (dipende dal tipo di dati)
      }
}

template<typename T> void bubble_sort(T *base, size_t n) {
   T *p, *q, t;    
   while (n--) { 
      for (q = (p = base) + 1; p < base + n; ++q, ++p) {
         (*p > *q) && (t = *p, *p = *q, *q = t);
      }
   }
}

BW Insultami 09:27, Nov 29, 2004 (UTC)

ERRORI ???

Credo che ci siano diversi errori in questo articolo, ma non sono in grado di fare una correzione globale, inoltre vorrei sentire qualche opinione (nel frattempo lo inserisco tra gli articoli da controllare). Credo che la descrizione dell'algoritmo sia errata (confrontare con la versione inglese per esempio, che invece ritengo corretta). Poi l'implementazione in C e in Basic sono differenti (IMHO è corretta quella in basic, mentre quella in C rispecchia la descrizione e quindi è anch'essa errata). Fortran e Java mi sembrano sostanzialmente corretti (forse con qualche piccolo bug). Sugli altri linguaggi non sono in grado di esprimermi. Che ne pensate? DanGarb 18:22, Lug 20, 2005 (CEST)

Ho modificato la descrizione è il programma in C. DanGarb 08:43, Lug 21, 2005 (CEST)

C'era comunque un errore (a=elemN!) l'ho corretto e ho cambiato i cicli (per come erano non c'era l'effetto bolla), ho anche introdotto un'ottimizzazione che comunque è prevista nell'algoritmo originale (ma manca nella discussione).

Io elminerei anche i register in quanto è buona norma lasciar fare al compilatorebermas66 09:05, Lug 21, 2005 (CEST)

• Non saprei, la parola chiave register in effetti lascia fare al compilatore (il suo significato letterale potrebbe essere reso con: "questa variabile verrà usata molto frequentemente nelle prossime istruzioni, se possibile sarebbe utile mantenerla in un registro di CPU"... Moongateclimber
  
  • Mi pare che così com'è il programma non funzioni. Credo sia fondamentale che i due cicli abbiano andamento opposto: una sale e l'altro scende. Consiglio di guardare qui. bye DanGarb 10:49, Lug 21, 2005 (CEST)
    
    • Non è necessario che gli andamenti siano opposti; su molti libri l'algoritmo viene riportato con i 2 cicli in uguale direzione. Ogni ciclo interno posiziona nella cella definitiva almeno uno dei valori non ancora a posto. Purche' il ciclo esterno comporti N iterazioni (dimensione array), alla fine tutti gli elementi sono a posto. Il ciclo inverso rende semplicemente più semplice esprimere gli indici di partenza e di arrivo dei confronti.Moongateclimber
      
    • 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 DanGarb 11:31, Lug 21, 2005 (CEST)
      
      • 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 più 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?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 DanGarb 13:40, Lug 21, 2005 (CEST)
          • Scusami, hai assolutamente ragione anche questa volta. Il problema è 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 :-((
          • A questo punto direi che siamo d'accordo Moongateclimber. :-) . Lascio comunque l'indicazione da controllare perché sarà opportuno dare un'occhiata anche agli altri linguaggi. Da una prima occhiata veloce, per quel che capisco qualche bug è ancora presente. Ora non ho tempo, spero di riuscire a darci un'occhiata più tardi. Mi sembri un esperto del ramo. Se hai tempo dacci un'occhiata anche tu. Alla prossima DanGarb 15:13, Lug 21, 2005 (CEST)

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

BW Insultami 12:06, Lug 21, 2005 (CEST)

Ho modificato di nuovo il codice C, ora è molto più coerente con la descrizione

--bermas66 19:16, Lug 21, 2005 (CEST)

---

Gentili ragazzi: stavo basandomi sulle vostre pagine per superare un esame di ingegneria e devo ammettere che quando parlate di questi algoritmi di ricerca girate un pò intorno al problema, perfavore siate più precisi e fate delle implementazioni più chiare!! E soprattutto evitate un sacco di spiegazioni inutili!! Basandomi su queste pagine ho solo perso due ore di tempo per capire che in realtà l'algoritmo non era sinteticamente spiegato, la codifica era astrusa e incomprensibile e per di più ci sono un sacco di errori!! Regà siate più chiari!!! Grazie Forse se mi gira ve la metto io un implementazione chiara in java: evitate di usare i riferimenti a gli oggetti e le classi tipo clone o isequal perchè si sta parlando di altro!!! Senza offesa e saluti a tutti gli informatici

Ricominciamo dal C

Allora, visto che si parla di ottimizzazioni, direi che si può partire dal KISS, e quindi:

1. è inutile dichiarare register le variabile su un codice didattico
2. altrettanto inutile è ottimizzare via qualche ciclo
3. se proprio vogliamo mettere l'algoritmo più ottimizzabile, mettiamo quello inverso, che parte dalla fine, cioè

void bubbleSort(int *array, int lunghezza)
{
  int a, b, temp;
  for(a = lunghezza - 1; a > 0; --a)
    for(b = 0; b < a; ++b)
      if(array[b] > array[b+1]) 
      {
        temp = array[b];   
        array[b] = array[b+1];
        array[b+1] = temp;
      }
}

Oltre ad essere il più breve, è anche quello che un compilatore ottimizzante gestisce meglio. Non serve nemmeno tener conto degli scambi...

Che ne dite? --BW Insultami 08:43, Lug 22, 2005 (CEST)

---

Sono d'accordo con te, su tutti i punti. Inoltre credo che la struttura del programma debba essere la stessa in tutti i linguaggi. Eventualmente si potrebbe scegliere il C per inserire anche una versione ottimizzata. bye DanGarb 08:54, Lug 22, 2005 (CEST)

Implementazioni

Ricordo a tutti che le implementazioni in specifici linguaggi vanno messe su Wikibooks, come da decisione della comunità. Il link a wikibooks è in fondo alla voce, nella sezione Altri progetti. Grazie. --Giuseppe (msg) 16:40, 27 gen 2010 (CET)

Modifica del secondo pseudocodice

Ho modificato leggermente il secondo pseudocodice: quest'ultimo infatti è un miglioramento del primo, quello base, e verte sul fatto che ad ogni iterazione si può ridurre di una unità il ciclo for. Quindi, al pari di quello base, esso deve fermarsi quando non sono più stati effettuati scambi e non quando alto (che ho rinominato n per maggiore semplicità) va a zero. Infatti, più che un miglioramento si tratterebbe in tal caso di un peggioramento: quello base, ad esempio, uscirebbe subito se la lista fosse già ordinata mentre il secondo codice che dovrebbe essere migliore scandirebbe inutilmente tutte le iterazioni.--Zetazeti (msg) 02:57, 23 gen 2015 (CET)

Carino. Grazie per averlo inserito!

L'analisi di complessità che hai introdotto, però, è molto vaga. Assumi forse uniforme distribuzione di probabilità dei valori? Potresti, in ogni caso, spiegare meglio da dove tiri fuori il dimezzamento dei tempi?

--SoujaK (msg) 17:17, 23 gen 2015 (CET)

Grazie dell'osservazione: rileggendola nuovamente non posso non condividere che la frase è troppo approssimativa. L'avevo tradotta direttamente dal corrispondente articolo inglese senza soffermarmi troppo. Non si può dire che si risparmia almeno il 50% dei confronti. Se ad esempio considero una lista già ordinata in partenza allora sia lo pseudocodice base, sia il terzo pseudocodice faranno la stessa cosa: usciranno alla conclusione del primo passaggio dopo aver effettuato lo stesso numero di confronti.--Zetazeti (msg) 00:18, 24 gen 2015 (CET)

Immagine

Utilizzerei questa File:Sorting bubblesort anim.gif che descrive IMHO meglio l'algoritmo --Valerio Bozzolan (msg) 17:39, 11 ott 2016 (CEST)

Bubble sort è stabile

Per quanto primitivo, bubble-sort ha un vantaggio su tanti tipi di algoritmi più veloci fra cui quick-sort: è stabile, non distrugge cioè l'ordine di chiavi che siano già state ordinate (non sono sicuro che questo fatto sia citato nel libro di Knuth). Se per esempio ordini una lista di clienti nella chiave 'cognome', puoi poi ordinarli nella chiave 'città' ottenendo una lista nella quale sotto ogni città i clienti son ordinati secondo il cognome. Se invece usi per esempio quick-sort per questo secondo ordinamento alla fine l'ordine dei cognomi è solitamente di nuovo casuale. Questa proprietà è discussa in generale in Algoritmo_di_ordinamento#Stabilità_di_un_algoritmo e mi sembra che se ne dovrebbe parlare anche in quest'articolo, dato che è piuttosto importante. 194.174.73.80 (msg) 13:46, 5 nov 2018 (CET) Marco Pagliero Berlin

Vedi WP:BOLD :-) --Horcrux (msg) 16:05, 5 nov 2018 (CET)