PDA

Visualizza la versione completa : [C] Insertion Sort di strutture e controllo ordine crescente e sort non funzionanti


matteo martis
26-02-2011, 10:05
Ciao!
ho creato una pagina c in un si inserisce, stampa e ordina una struct.
La struct contiene il nome, la data di nascita(struct), la media dei voti.
Il sort è crescente in base alla data di nascita.
Il controllo dell'ordine non fa entrare nel doppio for del sort e anche in
assenza del controllo il programma esce subito senza aver effettuato
nessun ordinamento.

Non inserisco qui il codice, ma in un link a parte, perchè il file è
abbastanza lungo.

link del sort della struttura (http://www.matteomartis.altervista.org/codice.pdf)

Grazie!!

GliderKite
26-02-2011, 10:58
L'algoritmo non può funzionare, il selection sort è diverso...

Il primo ciclo scandisce gli elementi dal primo al penultimo e assegna al minimo il valore di i, il secondo ciclo, più interno, va dall'elemento i-esimo + 1 fino all'ultimo e assegna al minimo il valore j-esimo relativo alla struttura effettivamente più "piccola" (o min-esimo se preferisci).
A questo punto solo alla fine del ciclo più interno fai il test: se l'elemento effettivamente più piccolo è diverso da i (cioè c'è stata un'assegnazione all'interno del secondo ciclo) scambia la nuova struttura min-esima con la struttura i-esima (per lo scambio basta una semplice assegnazione). Alla fine tutto ciò che ti serve per adattare il selection sort al tuo caso è una semplicissima funzione di comparazione delle tue strutture in base al campo desiderato.

:ciauz:

matteo martis
26-02-2011, 12:02
senza offesa
ma il codice ha tutte le caratteristiche di
un selection sort.
grazie per l'interessamento, comunque.

GliderKite
26-02-2011, 12:49
Nessuna offesa :) , ma ti stai sbagliando Selection Sort (http://en.wikipedia.org/wiki/Selection_sort)


Questa è la bozza corretta del codice:



void selectionSort( STUD *array, const size_t size, int (*cmp)(const STUD *, const STUD *) )
{
unsigned i;

for( i = 0; i < size-1; ++i )
{
unsigned min = i;
unsigned j = i+1;

for( ; j != size; ++j )
{
if( cmp(&array[j], &array[min]) < 0 )
min = j;
}

if( min != i )
swap( array, i, min );
}
}


Provala, fatti un idea e cerca di capire le differenze.
:ciauz:

matteo martis
26-02-2011, 12:57
Innanzitutto grazie per l'attenzione che mi stai dimostrando.
cmq... muovo una critica
se metti i =0 e j = 1 già dal primo turno mi escludi il primo elemento della serie di elemeti ancora disordinati

GliderKite
26-02-2011, 13:09
Originariamente inviato da matteo martis
Innanzitutto grazie per l'attenzione che mi stai dimostrando.
cmq... muovo una critica
se metti i =0 e j = 1 già dal primo turno mi escludi il primo elemento della serie di elemeti ancora disordinati

No, se guardi bene quando entra per la prima volta nol ciclo interno confronta il primo con il secondo elemento...

Sarebbe stato inutile inizializzare j con lo stesso valore di i confrontando cosi gli stessi elementi, non trovi?

matteo martis
26-02-2011, 13:16
ho capito cosa hai fatto... in realtà i due modi sono equivalenti...
no non è inutile perchè ...
al primo giro i e j sono uguale a zero significa che tutti gli elementi sono disordinati e quindi il minimo lo cerco tra tutti gli elementi poi trovato il minimo incremento i perchè la posizione 0 è occupata dall'elemento primo ordinato..il valore di i esprime il primo elemento disordinato e quindi quello che sarà l'ultimo elemento di quelli ordinati

GliderKite
26-02-2011, 13:22
No ti stai sbagliando, per definizione un array con un solo elemento è un array ordinato, confrontare gli stessi elementi porta a N operazioni aggiuntive inutili per l'ordinamento, si tratta di migliorare l'efficienza dell'algoritmo stesso. Oltretutto quello che ti ho indicato io è quello "originale" senza miglioramenti.

Ti consiglio di leggerti almeno la pagina che ti ho linkato, poi se hai ancora dubbi ne riparliamo.
:ciauz:

matteo martis
26-02-2011, 13:26
okay

Loading