[c] Algoritmo ricorsivo trova due minori

[nasuka89]

Ecco un altro esercizio che non sono sicuro di aver svolto bene:
Implementare un algoritmo basato sul paradigma divide et impera per trovare i due elementi più piccoli di
un insieme di n elementi.
Quindi dato un array di n numeri a[n] lo ordinavo in modo crescente con la ricorsione e poi stampavo i primi 2 numeri

void trovaMinori(int *a, int n, int i){

  int j,temp;
  
   if( i == n){

     printf("I due minori sono: %d, %d", a[0], a[1]);
     return;        
  
    } 

   for(j=0; j <= n-1; j++){

       if(a[j] > a[i]){

             temp = a[j];
             a[j] = a[i]; 
             a[i] = temp;

             }       

       }


       trovaMinori(*a, n, i +1);

 }

[Mond0]

riguardati la ricorsione ed in particolare il passaggio dei parametri, ad un puntatore bisogna farlo puntare ad un indirizzo di memoria e non assegnargli un valore...
in ogni caso non ho capito dove sfrutti il paradigma divide et impera. se vuoi ordinare guardati come lavorano il merge sort o il quicksort. Quelli sfruttano questo paradigma...

[Who am I]

C'è un errore qua:

trovaMinori(*a, n, i +1);

Il primo parametro deve essere un puntatore ad int ma gli passi un intero.
Per cui lo cambi così:

trovaMinori(a, n, i +1);

Per il resto la funzione è corretta.
L' unica pecca è che la funzione non è efficiente perché spende O(n^2) operazione, quando si potrebbe fare in O(n).
Per trovare i due minori ti basta scorrere tutto l' array (il difficile è farlo ricorsivamente).
Prova a farlo

[nasuka89]

Guardando il quick sort ho provato a fare questo algoritmo ricorsivo di ordinamento

void sort(int *a, int m, int n)
{
    int i,j;   
    int medio; 

    
     medio=(a[m]+a[n])/2;

     i=m;
     j=n;

     do
    {
      
         while(a[i]<medio)
        {
          i++;
        }

        
        while(a[j]>medio)
        {
          j--;
        }

        
        if(i<j)
        {
          scambia(&a[i],&a[j]);
          i++;
          j--;
        }
    
    
    } while(i<j);  																	
    
  
   if(m<j)
    {
           sort(a,m,j);
    }

    
    if(n>i)
    {
           sort(a,i,n);
    }
}


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