banalità sul selection sort

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
ummagumma
Messaggi: 94
Iscritto il: 22 lug 2007, 11:14

banalità sul selection sort

Messaggio da ummagumma » 10 feb 2008, 19:29

DISCLAIMER La domanda non ha niente di olimpico, ma non vuole essere "scroccona".

Bene, trovandomi ad implementare questo (inutile) algoritmo in C++, ho scelto la procedura standard:

Codice: Seleziona tutto

void select (int riemp, float vett[]) {
     int i,j;    //indici di scorrimento
     int min;    //posto occupato dal minimo
     for (i=0; i<riemp-1; i++) {
         min=i;    
         for (j=i+1; j<riemp; j++) { 
             if (vett[j]<vett[min]){ 
                min=j;
             }
         }   
         swap (vett[min],vett[i]);
     }
}
Tuttavia il programma funge anche in questa versione che poco mi convince sul piano teorica, ma si rivela anche più efficiente della precedente (una var in meno)

Codice: Seleziona tutto

void select (int riemp, float vett[]) {
     int i,j;    //indici di scorrimento
         for (i=0; i<riemp-1; i++) {
         for (j=i+1; j<riemp; j++) { 
             if (vett[j]<vett[i]){ 
                swap (vett[j],vett[i]);
             }
         }   
         
     }
}
grazie a chi voglia togliermi un dubbio

fph
Site Admin
Messaggi: 3801
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 10 feb 2008, 20:46

ehm... qual è la domanda esattamente?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
ummagumma
Messaggi: 94
Iscritto il: 22 lug 2007, 11:14

Messaggio da ummagumma » 10 feb 2008, 22:05

Il secondo codice non mi sembra esatto, quantomeno non aderente all'algoritmo del select sort, almeno per le mie (scarse) conoscenze informatiche.
In nome dell'efficienza volevo sapere se il secondo codice è corretto...grazie

fph
Site Admin
Messaggi: 3801
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 10 feb 2008, 23:11

Se non mi sfugge qualcosa, anche il secondo codice ordina correttamente il vettore in input. Però (in media) chiama molte più volte la funzione swap(), che potrebbe essere un peggioramento in termini di prestazioni (in questo caso sono float, quindi pochi problemi, ma se quello che devi ordinare sono cose più complicate da copiare sono guai).
Se stai imparando il C o è un esercizio di un qualche corso di programmazione, bueno, la tua idea funziona, positivo.
Se invece devi usare quella funzione in un programma "vero", ti consiglio di rimpiazzare la tua funzione di ordinamento scritta a mano con la funzione standard qsort(), ha prestazioni migliori.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Rispondi