[C] efficenza Bubble sort

[Skass89]

#include <stdio.h>
#define SIZE 10


int main() {
    
    int a[SIZE] = {78,3,5,6,7,8,1,2,34,56};
    int idx; /* contatore */
    int pass;
    int temp;
    
    printf("Valori del vettore in posizione originale sono: \n");
    
    printf("\n");
    
    for(idx = 0;idx < SIZE; idx++){
       printf("%3d", a[idx]);
    }/* fine ciclo di stampa del vettore disordinato */
    
    printf("\n");
    
    /*bubble sort*/
    
    for(pass = 1; pass < SIZE; pass++){
       
       for(idx = 0; idx < SIZE - 1; idx++){
               
               if(a[idx]>a[idx+1]){
                  temp = a[idx];
                  a[idx] = a[idx+1];
                  a[idx+1] = temp;
                  } /* fine scambio */
       }/*fine for interno*/
    }/*fine for esterno*/

    printf("\n****** - bubble sort - *******\n");
    
    printf("\nGli elementi del vettore ordinati sono: \n");
    
    printf("\n");
    
    /*stampa vettore ordinato*/
    for(idx = 0; idx < SIZE; idx++){
       printf("%3d", a[idx]);
    }
    
    printf("\n\n");
    
    system("pause");
    return 0;
    
}

ciao ragazzi, ho un piccolo problema con un esercizio, allora questo codice che ho postato è l'oridnamento di un vettore statico con il bubble sort. Il problema è che l'esercizio mi richiede di renderlo più efficente, modificandolo in modo tale da ridurre il numero dei passaggi ad ogni incremento della variabile "pass", cioè siccome al primo passaggio il decimo elemento sarà sicuramente andato nell'ultima posizione(a[9]) perchè al secondo passaggio non gli fai controllare solo le altre nove posizioni rimaste? cioè da a[0] ad a[8]...nel terzo passaggio da a[0] ad a[7] e così via....è un po confuso come l'ho scritto spero che capiate qualcosa XD....e mi diate qualche spunto

[Lawliet]

Ma che algoritmo hai usato!? Non è di certo bubble sort!

[Skass89]

Originariamente inviato da Lawliet
Ma che algoritmo hai usato!? Non è di certo bubble sort!

è sicuramente bubble sort!

[Lawliet]

Si, mi ero sbagliato, non avevo mai utilizzato in questo modo l'algoritmo bubble sort, anzi usavo uno più ottimizzato.. con una flag booleana per vedere se c'è stato almeno uno scambio, se non c'è stato vuol dire che è ordinato il vettore! In caso contrario riesegue la iterazione fino a quando non ci saranno più scambi.

[Skass89]

forse tu hai la risposta alla mia richiesta...se non ci sono stati scambi, ok il vettore è ordinato, ma per ridurre i passaggi dopo questi scambi in modo che ad ogni passaggio gli ultimi valori (cioè quelli già ordinati) non vengano più considerati, come si può fare?

[MItaly]

Studiati questo codice, che usa lastSwappedLine sia come limite di riga da esaminare nel ciclo successivo, sia come condizione di uscita (se l'ultima riga scambiata è la riga zero vuol dire che non c'è più niente da scambiare).

void BubbleSort(int Array[], size_t Length)
{
    size_t lastSwappedLine;
    size_t limit=Length-1;
    do
    {
        swappedLine=0;
        for(size_t i=0;i<limit-1;i++)
        {
            if(Array[i]>Array[i+1])
            {
                lastSwappedLine=i;
                Swap(Array+i, Array+i+1);
            }
        }
        limit=lastSwappedLine;
    } while(lastSwappedLine);
}

[c_junior]

Originariamente inviato da Skass89
forse tu hai la risposta alla mia richiesta...se non ci sono stati scambi, ok il vettore è ordinato, ma per ridurre i passaggi dopo questi scambi in modo che ad ogni passaggio gli ultimi valori (cioè quelli già ordinati) non vengano più considerati, come si può fare?

nel for oltre all'i++ prova ad aggiungere anche un SIZE-- cosi ad ogni iterazione non arriverà più in fondo al vettore

[MItaly]

Originariamente inviato da c_junior
nel for oltre all'i++ prova ad aggiungere anche un SIZE-- cosi ad ogni iterazione non arriverà più in fondo al vettore

Occhio però che SIZE è una macro del preprocessore, che non può essere decrementata; deve usare una variabile separata a questo scopo.

[c_junior]

Originariamente inviato da MItaly
Occhio però che SIZE è una macro del preprocessore, che non può essere decrementata; deve usare una variabile separata a questo scopo.

ah si si è vero non l'ho visto!!!!

[Skass89]

Originariamente inviato da MItaly
Studiati questo codice, che usa lastSwappedLine sia come limite di riga da esaminare nel ciclo successivo, sia come condizione di uscita (se l'ultima riga scambiata è la riga zero vuol dire che non c'è più niente da scambiare).

void BubbleSort(int Array[], size_t Length)
{
    size_t lastSwappedLine;
    size_t limit=Length-1;
    do
    {
        swappedLine=0;
        for(size_t i=0;i<limit-1;i++)
        {
            if(Array[i]>Array[i+1])
            {
                lastSwappedLine=i;
                Swap(Array+i, Array+i+1);
            }
        }
        limit=lastSwappedLine;
    } while(lastSwappedLine);
}

questo è un'altro modo d'implementare il bubble sort???

poi....


senza togliere SIZE come posso aggirarlo questo problema di non far arrivare ogni volta fin in fondo il controllo?