[C] - Selection Sort Ricorsivo

di Anonimizzato27228 il
7 risposte
/
Anonimizzato27228
Utente anonimizzato
Salve a tutti, vorrei un parere sul seguente esercizio :

ES: (Ordinamento per selezione) Un ordinamento per selezione ricercherà in un vettore l'elemento più piccolo e, quando l'avrà individuato, lo scambierà di posto con il primo elemento del vettore. Il processo si ripeterà per il sottovettore che comincia con il secondo elemento del vettore. Ogni passaggio sul vettore farà in modo che un elemento sia sistemato nella posizione appropriata. Questo ordinamento richiede che per un vettore di n elementi, dovranno essere eseguiti n-1 passaggi e, per ogni sottovettore, dovranno essere compiuti n-1 confronti per individuare il valore più piccolo. Il vettore risulterà ordinato nel momento in cui il sottovettore da elaborare conterrà un solo elemento. Scrivete una funzione ricorsiva selection_sort che implementi questo algoritmo.

Io l'ho svolto in questo modo : 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 10

void selection_sort(int vett[], int size);

int main()
{
    int vettore[DIM], i;
    srand(time(NULL));

    printf("\nVETTORE CASUALE : ");
    for(i = 0; i < DIM; i++)
    {
    	vettore[i] = 1 + rand() % 20;
    	printf("%d ", vettore[i]);
    }
    
    selection_sort(vettore, DIM - 1);

    printf("\n\nVETTORE ORDINATO : ");
    for(i = 0; i < DIM; i++)
    	printf("%d ", vettore[i]);
    
    printf("\n\n");
    return 0;
}

void selection_sort(int vett[], int size)
{
     int prev;
     
     if(size == 0) 
	 return;
     selection_sort(vett, size - 1); 

     if(vett[size] < vett[size - 1])
     {
	 prev = vett[size];
	 vett[size] = vett[size - 1];
	 vett[size - 1] = prev;
     }
     selection_sort(vett, size - 1); 
}
Secondo voi è corretta come possibile soluzione? La funzione ricorsiva è corretta?

Grazie

7 Risposte

  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221
    Sicuro di aver implementato selection sort e non un altro algoritmo di ordinamento?

    Ad esempio, nel vettore {5, 4, 3, 2, 1} il primo scambio dovrebbe essere tra 5 e 1 
    
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 5

void selection_sort(int vett[], int size);

int vettore[DIM] = {5, 4, 3, 2, 1} ;

int main()
{
    int i;
    srand(time(NULL));

    //printf("\nVETTORE CASUALE : ");
    for(i = 0; i < DIM; i++)
    {
    	//vettore[i] = 1 + rand() % 20;
    	printf("%d ", vettore[i]);
    }
    printf("\n");
    
    selection_sort(vettore, DIM - 1);

    printf("\n\nVETTORE ORDINATO : ");
    for(i = 0; i < DIM; i++)
    	printf("%d ", vettore[i]);
    
    printf("\n\n");
    return 0;
}

void selection_sort(int vett[], int size)
{
     int prev;
     
     if(size == 0) 
	 return;
     selection_sort(vett, size - 1); 

     if(vett[size] < vett[size - 1])
     {
	 prev = vett[size];
	 vett[size] = vett[size - 1];
	 vett[size - 1] = prev;
	 
         for(prev=0;prev<DIM;prev++)
              printf("%d ", vettore[prev]);
         printf("\n");
     }
    
     selection_sort(vett, size - 1); 
}
  • /
    Anonimizzato27228
    Utente anonimizzato

    Weierstrass ha scritto:

    Sicuro di aver implementato selection sort e non un altro algoritmo di ordinamento?

    Ad esempio, nel vettore {5, 4, 3, 2, 1} il primo scambio dovrebbe essere tra 5 e 1 
    
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 5

void selection_sort(int vett[], int size);

int vettore[DIM] = {5, 4, 3, 2, 1} ;

int main()
{
    int i;
    srand(time(NULL));

    //printf("\nVETTORE CASUALE : ");
    for(i = 0; i < DIM; i++)
    {
    	//vettore[i] = 1 + rand() % 20;
    	printf("%d ", vettore[i]);
    }
    printf("\n");
    
    selection_sort(vettore, DIM - 1);

    printf("\n\nVETTORE ORDINATO : ");
    for(i = 0; i < DIM; i++)
    	printf("%d ", vettore[i]);
    
    printf("\n\n");
    return 0;
}

void selection_sort(int vett[], int size)
{
     int prev;
     
     if(size == 0) 
	 return;
     selection_sort(vett, size - 1); 

     if(vett[size] < vett[size - 1])
     {
	 prev = vett[size];
	 vett[size] = vett[size - 1];
	 vett[size - 1] = prev;
	 
         for(prev=0;prev<DIM;prev++)
              printf("%d ", vettore[prev]);
         printf("\n");
     }
    
     selection_sort(vett, size - 1); 
}
    Hai ragione, ho implementato una versione ricorsiva di bubble sort
    l'ho corretto penso che ora dovrebbe essere l'ordinamento giusto : 
    #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 10

void selection_sort(int vett[], int size, int start);

int main()
{
    int vettore[DIM], i;
    srand(time(NULL));
    
    printf("\nVETTORE CASUALE : ");
    for(i = 0; i < DIM; i++)
    {
        vettore[i] = 1 + rand() % 10;
    	printf("%d ", vettore[i]);
    }
    selection_sort(vettore, DIM - 1, 0);

    printf("\n\nVETTORE ORDINATO : ");
    for(i = 0; i < DIM; i++)
    	printf("%d ", vettore[i]);
    
    printf("\n\n");
    return 0;
}

void selection_sort(int vett[], int size, int start)
{
     int min = vett[size], i, index = size;
     
     if(start == size) 
	    return;

     for(i = start; i < size; i++)
     {
        if(vett[i] < min)
        {
	       min = vett[i];
           index = i;
        }
     }
     vett[index] = vett[start];
     vett[start] = min;
     selection_sort(vett, size, start + 1); 
}
    che a differenza del precedente cerca prima il minimo nel vettore, poi lo scambia con l'elemento in prima posizione e poi effettua la chimata ricorsiva. Va bene scritto così o andrebbe corretto qualcosa?
  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221
    Va benissimo.

    Se vuoi potresti semplificare un po'
    
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 10

void selection_sort(int vett[], int size);

int main()
{
    int vettore[DIM], i;
    srand(time(NULL));
    
    printf("\nVETTORE CASUALE : ");
    for(i = 0; i < DIM; i++)
    {
        vettore[i] = 1 + rand() % 10;
    	printf("%d ", vettore[i]);
    }
    selection_sort(vettore, DIM);

    printf("\n\nVETTORE ORDINATO : ");
    for(i = 0; i < DIM; i++)
    	printf("%d ", vettore[i]);
    
    printf("\n\n");
    return 0;
}

void selection_sort(int vett[], int size)
{
     if(size < 2)
        return;
        
     int min = vett[0], i, index = 0;
     for(i = 0; i < size; i++)
        if(vett[i] < min)
        {
	   min = vett[i];
           index = i;
        }
     vett[index] = vett[0];
     vett[0] = min;
     selection_sort(vett + 1, size - 1); 
}
  • Avatar di Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi
    1224
    Volendo potresti anche utilizzare la funzione minimo_ricorsivo() implementata in precedenza, qualcosa del genere insomma: 
    #include <stdio.h>

#define DIM 10

void scambia_valori(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int min(int v[], int i)
{
    int i_min;
    return(!i || v[i] < v[i_min = min(v, i - 1)] ? i : i_min);
}

void selection_sort(int v[], int dim)
{
    if(dim > 1)
    {
        scambia_valori(v, v + min(v, dim - 1));
        selection_sort(v + 1, dim - 1);
    }
}

int main()
{
    int v[DIM] = {3, 9, 0, 2, 5, 4, 8, 6, 1, 7};
    selection_sort(v, DIM);
    for(unsigned int i = 0; i < DIM; ++i)
    {
        printf("%d ", v[i]);
    }
    return 0;
}
  • /
    Anonimizzato27228
    Utente anonimizzato

    Weierstrass ha scritto:

    Va benissimo.

    Se vuoi potresti semplificare un po'
    
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 10

void selection_sort(int vett[], int size);

int main()
{
    int vettore[DIM], i;
    srand(time(NULL));
    
    printf("\nVETTORE CASUALE : ");
    for(i = 0; i < DIM; i++)
    {
        vettore[i] = 1 + rand() % 10;
    	printf("%d ", vettore[i]);
    }
    selection_sort(vettore, DIM);

    printf("\n\nVETTORE ORDINATO : ");
    for(i = 0; i < DIM; i++)
    	printf("%d ", vettore[i]);
    
    printf("\n\n");
    return 0;
}

void selection_sort(int vett[], int size)
{
     if(size < 2)
        return;
        
     int min = vett[0], i, index = 0;
     for(i = 0; i < size; i++)
        if(vett[i] < min)
        {
	   min = vett[i];
           index = i;
        }
     vett[index] = vett[0];
     vett[0] = min;
     selection_sort(vett + 1, size - 1); 
}
    Si e in effetti in questo modo passerei anche un argomento in meno alla funzione, grazie ...per essere sicuro di aver capito nella tua chiamata ricorsiva: 
    selection_sort(vett + 1, size - 1);
    quel vett+1 è il vettore che parte da un indice successivo giusto?
  • /
    Anonimizzato27228
    Utente anonimizzato

    Nippolo ha scritto:

    Volendo potresti anche utilizzare la funzione minimo_ricorsivo() implementata in precedenza, qualcosa del genere insomma: 
    #include <stdio.h>

#define DIM 10

void scambia_valori(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int min(int v[], int i)
{
    int i_min;
    return(!i || v[i] < v[i_min = min(v, i - 1)] ? i : i_min);
}

void selection_sort(int v[], int dim)
{
    if(dim > 1)
    {
        scambia_valori(v, v + min(v, dim - 1));
        selection_sort(v + 1, dim - 1);
    }
}

int main()
{
    int v[DIM] = {3, 9, 0, 2, 5, 4, 8, 6, 1, 7};
    selection_sort(v, DIM);
    for(unsigned int i = 0; i < DIM; ++i)
    {
        printf("%d ", v[i]);
    }
    return 0;
}
    Grazie, anche questa è una buona alterativa. In realtà avevo pensato di utilizzare la funzione ricorsiva sul minimo ma per paura di "annidarmi in chiamate multiple" ho optato per un'altra strada
  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221
    selection_sort(vett + 1, size - 1);
    quel vett+1 è il vettore che parte da un indice successivo giusto?
    Sì
Devi accedere o registrarti per scrivere nel forum
7 risposte