[C] selection sort

[Metallica]

allora ho questo programma

#include <stdio.h>
#include <malloc.h>

/* PROTOTIPO FUNZIONE */
void sel_sort(float *A, int n);

main() {

/* DICHIARAZIONE VARIABILI */
int i, n, c;
float *A;

	/* LETTURA GRANDEZZA ARRAY */
	printf("Inserire la grandezza n dell'array: ");
	scanf("%d",&n);

	/* ALLOCAZIONE DINAMICA DELLA MEMORIA */
	if(!(A = (float *)malloc(n*sizeof(float))))
	abort();

	/* LETTURA DI TUTTI GLI ELEMENTI DELL' ARRAY A */
	printf("\nInserire uno per uno tutti gli elementi dell'array...\n");
	   for (i=0; i<n; i++){
	      printf("Inserire il %d° elemento: ", c=i+1);
	      scanf("%f", &A[i]);
	   }

	/* RICHIAMO DELLA FUNZIONE */
	sel_sort(A, n);

	/* STAMPA A VIDEO DELL'ARRAY ORDINATO */
	printf("\nL'array A è ora ordinato come segue:\n");
	for (i=0; i<n; i++)
	printf("%f\n", A[i]);
}

/****************** SPECIFICHE FUNZIONE *************************/
void sel_sort(float *A, int n){
int i, j, p, min;

for (i=0; i<n-1; i++) {
    min = A[i];
    p = i;
        for (j=i+1; j<n; j++){
                if (A[j]<min){
                min = A[j];
                p = j;
                }
           A[p] = A[i];
           A[i] = min;
        }
}
}

che dovrebbe ordinare un' array ma se ad es dò in input un array del tipo:
6 2 45 12
lui mi dà in output:
2 2 12 45.
Che fine fà il 6? dove sbaglio???

[DaUlisse]

io semplicemente nn capisco cosa vuoi fare...
di metodi di ordinamento ce ne sono tanti ma uno cosi nn l'ho mai visto
cmq se vuoi un algoritmo di ordinamento serio usa il quick sort randomizzato che risolve in tempo O(lgN) o almeno quello base ma sta attento x' nei casi peggiori gira in O(N^2)
oppure usa il buble sort + semplice ma meno efficente
...in ogni caso x saperne di + su tali algortimi cerca su internet...
bye, spero di esserti stato di aiuto

[}gu|do[z]{®©]

Originariamente inviato da DaUlisse
io semplicemente nn capisco cosa vuoi fare...
di metodi di ordinamento ce ne sono tanti ma uno cosi nn l'ho mai visto

se lui chiede il selection sort non ne vuol un altro, no? :quipy:

gli do una guardata mariano.. ammesso che ci pcapisca

[}gu|do[z]{®©]

void sel_sort(float *A, int n)
{
int i, j, p, min;

for (i=0; i<n-1; i++) {
    min = A[i];
    p = i;
        for (j=i+1; j<n; j++){
                if (A[j]<min)
                {
                 min = A[j];
                 p = j;
                 A[p] = A[i];
                 A[i] = min;
                }
           
        }
}
}

ricchione... mettevi:
A[p] = A[i];
A[i] = min;

fuori dall'if.. ovvero lo faceva anche se l'elemento corrente era maggiore del minimo

[anx721]

Il problema sta nel fatto che effettui lo scambio ad ogni iterazione del ciclo for interno, invece devi fare lo scambio soltanto alla fine del ciclo for interno, dopo che in p e stato memorizzato l'indice del minimo.

Ecco il codice corretto:

void sel_sort(float *A, int n){
int i, j, p;
float min;

for (i=0; i<n-1; i++) {
    min = A[i];
    p = i;
        for (j=i+1; j<n; j++){
			if (A[j]<min){
                min = A[j];
                p = j;
            }
        }
        A[p] = A[i];
        A[i] = min;
	}
}

Il selection sort è uno degli algoritmi di ordinamento piu semplici e noti; il quicksort ha complessita temporale pari a O(n^2) sempre nel caso peggiore, anche se nei casi pratici si rivela l'algoritmo di ordinamento piu veloce.