Discussione:Bubble sort

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 compilatore

--bermas66 09:05, Lug 21, 2005 (CEST)

• • 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 e' 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 piu' semplice esprimere gli indici di partenza e di arrivo dei confronti.Moongateclimber

• 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