Newsgroup: it.comp.lang.c++
Titolo: BubbleSort ricorsivo

Scusate, sarņ stupido quanto volete, ma non riesco a capire per quale motivo
non funziona il prog in questione... se qualcuno puņ darmi una mano lo
ringrazio in anticipo.
Cesare
// Bubble Sort ricorsivo
#include <iostream>
#include <cstdlib>
void bubbleSortRic( int [], int, int ) ;
void scambia( int [], int, int ) ;
int main()
{
    const int arraySize = 10 ;
    int a[ ] = { 45, 34, 6, 72, 13, 3, 98, 84, 65, 23 } ;
    cout << "L'ordine originale dell'aray e' " << endl ;
    for ( int i = 0 ; i < arraySize ; i++ )
        cout << a[ i ] << ' ' ;
    cout << endl ;
    bubbleSortRic( a, 0, arraySize - 1 ) ;
    cout << "L'ordine nuovo dell'aray e' " << endl ;
    for ( int i = 0 ; i < arraySize ; i++ )
        cout << a[ i ] << ' ' ;
    cout << endl ;
    system("PAUSE") ;
    return 0 ;
}
void bubbleSortRic( int array[], int inf, int sup )
{
    if ( inf < sup ) {
       int index ;
       int min = array[ inf ] ;
       for ( int i = inf + 1 ; i <= sup ; i++ )
           if ( min > array[ i ] ) {
              min = array[ i ] ;
              index = i ;
           }
       scambia( array, inf, index ) ;
       bubbleSortRic( array, inf + 1, sup ) ;
    }
}
void scambia( int ar[], int x, int y )
{
    int temp = ar[ x ] ;
    ar[ x ] = ar[ y ] ;
    ar[ y ] = temp ;
}


in cosa non ti funziona? sii piu specifico


Fondamentalmente il programma viene compilato e avviato tranquillamente,
eppure non ordina tutti gli elementi dell'array.
Provando a diminuire il numero di elementi si ha lo stesso problema...
pensavo fosse un problema di "magic numbers", dovuto al -1 con cui passo
l'estremo superiore alla funzione, ma niente.
L'output del file è
L'ordine originale dell'aray e'
45 34 6 72 13 3 98 84 65 23
L'ordine nuovo dell'aray e'
3 6 13 34 45 23 65 72 84 98
Premere un tasto per continuare . . .
come vedi il 23 non è ordinato.
Cesare


Eccoti il programma riveduto e corretto con il relativo output:
#include <iostream>
#include <cstdlib>
using namespace std;
// se non usi il namespace std tutte le chiamate a cout e altre danno errore
void bubbleSortRic( int [], int, int ) ;
void scambia( int [], int, int ) ;
int main()
{
    const int arraySize = 10 ;
    int a[ ] = { 45, 34, 6, 72, 13, 3, 98, 84, 65, 23 } ;
    int i = 0; // qui ho dovuto dichiarare i fuori dai for per un bug del
VisualC++ 6
    cout << "L'ordine originale dell'aray e' " << endl ;
    for (i = 0 ; i < arraySize ; i++ )
        cout << a[ i ] << ' ' ;
    cout << endl ;
    bubbleSortRic( a, 0, arraySize - 1 ) ;
    cout << "L'ordine nuovo dell'aray e' " << endl ;
    for (i = 0 ; i < arraySize ; i++ )
        cout << a[ i ] << ' ' ;
    cout << endl ;
    system("PAUSE") ;
    return 0 ;
}
void bubbleSortRic( int array[], int inf, int sup )
{
 if ( inf < sup )
 {
  int index  = -1;
  int min = array[ inf ] ;
  for ( int i = inf + 1 ; i <= sup ; i++ )
   if ( min > array[ i ] )
   {
    min = array[ i ] ;
    index = i ;
   }
  if (index >= 0)
// qui devi controllare se hai trovato un index,
// altrimenti chiameresti scambia con un index senza significato
   scambia( array, inf, index ) ;
  bubbleSortRic( array, inf + 1, sup ) ;
 }
}
void scambia( int ar[], int x, int y )
{
    int temp = ar[ x ] ;
    ar[ x ] = ar[ y ] ;
    ar[ y ] = temp ;
}
L'ordine originale dell'aray e'
45 34 6 72 13 3 98 84 65 23
L'ordine nuovo dell'aray e'
3 6 13 23 34 45 65 72 84 98
Appuyez sur une touche pour continuer...
Maurus

 }
Purtroppo non ho il tempo di vedere perchè non funzioni dalla metà dell'array in su. Comunque una versione che
rispecchia la descrizione del bubblesort ricorsivo che sia funzionante è
void bubbleSortRic( int array[], int inf, int sup )
{
      if ( inf < sup )
     {
           for( int i = 0; i < sup; ++i )
          {
                 if( array[i] > array[i+1] )
                       scambia( array, i, i+1 ) ;
          }
          bubbleSortRic( array, inf, sup - 1 ) ;
    }
}
dopo ogni passo siamo sicuri che l'elemento maggiore sia in coda ed ordiniamo il resto.
Ciao,
--
----------------------------------------------
Fulvio Esposito
WWW: 
http://digilander.iol.it/fesposito
E-Mail Contact me at: 
ful...@libero.it
----------------------------------------------

 ha scritto nel messaggio news:fzEv8.6037$g04....@tornado.fastwebnet.it...
Quello che hai presentato non è bubble sort ricorsivo, bensi selection sort ricorsivo. Se ci pensi, ad ogni passo n tu
selezioni l'elemento che deve andare nella posizione n. Questo è un selection sort. per il bubble sort ricorsivo vedi il
mio altro post.
Ciao


 // se non usi il namespace std tutte le chiamate a cout e altre danno
errore
Questo dipende dal compilatore, su dev c++ ad esempio non ho bisogno di
usare namespace.

hai ragione infatti era qui l'errore... grazie mille :o)
Cesare

     bubbleSortRic( a, 0, arraySize );
Uhm ci ho provato ma sempre mi dava errore ed in fondo, a mio modesto
parere, non credo sia lě l'errore perchč a fini della funzione devo passare
un indice che esprima l'ultimo elemento dell'array, il che equivale alla
dimensione dell'array diminuita di uno, partendo l'indice da 0.
Cesare


Ti do un piccolo consiglio.
Anche se col tuo compilatore questa cosa funziona, e' meglio che segui le
indicazioni dello standard.
Se un giorno dovessi utilizzare il tuo programma su un altro compilatore o
su un'altra macchina con un sistema operativo diverso potresti avere grosse
rogne.
E inoltre il fatto che il DevC++ usi per default il namespace std non e' una
buona cosa, in quanto e' come dire che i namespaces non servono a una mazza.
Per cui anche se sviluppi su DevC++, abituati ad usare std::cout al posto di
cout (std::endl e cosi' via), altrimenti potresti procurarti problemi in
futuro.
Maurus

namespaces... grazie per avermi corretto.
Sono le vecchie versioni del gcc precedenti alla 3.0 (come quella
distribuita con il dev-c++) che inseriscono tutto anche nel namespace
globale.
-- 
Marco Barisione (ICQ 84277092)