[C] Domanda su algoritmo di selezione di massimo

[thefiery77]

Buonasera, oggi durante un esamen il prof di programmazione mi ha chiesto l'algoritmo di ordinamento per selezione di massimo. Io gli ho scritto questo:

void f(int array[], int n) {
    int i,j,temp;
    for(i=n-1; i>=0; i--) {
        for(j=0; j<i-1; j++) {
            if(array[j]>array[i]) {
                temp=array[j];
                array[j]=array[i];
                array[i]=temp;
            }
        }
    }
}

e mi ha detto che non andava bene perché non aveva la stessa complessità di tempo di questo.

void ord_sel_max(char array[],int n) {
    int i,indice_max;
    char max_array;
    for (i=n-1; i>0; i--)
    {
        max_val_ind(&array[0],i+1,&max_array,&indice_max);
        scambiare_c(&array[i],&array[indice_max]);
    }
}

void max_val_ind(char a[],int n,char *max_array, int *i_max) {
    int i;
    *max_array = a[0];
    *i_max = 0;
    for (i=1; i<n; i++)
        if (a[i] > *max_array)
        {
            *max_array = a[i];
            *i_max = i;
        }
}

è vero o mi ha bocciato ingiustamente?

[thefiery77]

up

[MItaly]

Senza entrare nel merito degli algoritmi (se devi cercare solo il massimo basta una ricerca lineare O(n), se devi fare un sort gli algoritmi "veri" sono O(n log n)), ad occhio mi sembrano entrambi O(n^2).

[thefiery77]

il secondo ha una compressita di tempo assoluta di O(n^2) per quanto riguarda i confronti, O(n) per gli scambi. Quello che ho scritto io se non sbaglio è più efficiente nel caso l'array sia già ordinato (non effettua scambi) mentre il secondo no e li effettua comunque. Sbaglio?