[C] Ricerca del k-mo elemento minimo di un array

[Kyros_]

ricerca del k-mo elemento minimo di un array usando il partizionamento, dove k non lo conosciamo

[Scara95]

Comincia col proporre almeno lo scheletro della soluzione

[Kyros_]

#include <stdio.h>
int partition(int a[], int n);
int main() {
    /*dichiarazioni variabili */
    int i;
    int n;
     /*dimensione array*/
    printf("dimensione array \n ");
    scanf("%d",&n);
    int a[n];
    for(i=0;i<n;i++){
        printf("inserisci numero %d: ",i);
        scanf("%d",&a[i]);    
    }
//  /*chiamata alla funzione */
    int part = partition(a, n);
    /*stampa del risultato */
    printf("Minori o uguali : ");
    for(i = 0; i < part; ++i) {
        printf("%d ", a[i]);
    }
    printf("\nMaggiori: " );
    for(i = part; i < n; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}
int partition(int a[], int n) {
    /*dichiarazioni variabili */
    int i;
    int  j=0;
    int min;
    min=a[0];
    /*ricerca del k-mo elemento minimo */
    for(i=0; i< n;i++) {
        if(min>=a[i]){
            min=a[i];
            }
        }
        printf("il k-mo elemento minimo e' %d  \n",min);
   
    for(i=0; i< n;i++) {
        if(a[i] <= min) {
            int tmp = a[j];
            a[j] = a[i];
            a[i] = tmp;
            j++;
        }
    }
    /*valore di ritorno */
    return j;
}

[Kyros_]

up

[Scara95]

Devi trovare il k-esimo minimo, non i i valori più piccoli...
Comunque:
Lavorando sulla sezione di array a-b
Scegli un pivot p, partizioni ordinando: minoriugualip p maggiorip
Se k < indice(p) vai a sinistra (a, indice(p)-1)
Se k=indice(p) hai trovato l'elemento
Se k>indice(p) vai a destra (indice(p)+1, b)

[militandri]

Secondo me ti conviene semplicemente ordinare tutto l'array e poi scorrerlo per trovare il k-esimo minimo.

[Scara95]

Secondo me ti conviene semplicemente ordinare tutto l'array e poi scorrerlo per trovare il k-esimo minimo.

Aveva specificato "usando il partizionamento" nel testo.

In ogni caso un ordinamento supponendo un qsort ha complessità O(n*log(n)) nel caso medio O(n*n) nel caso pessimo
L'algoritmo di cui sopra ha complessità O(log(n)) nel caso medio O(n*n) nel caso pessimo

E oltretutto, se si vuole un tempo di risposta più prevedibile con un caso pessimo migliore è più opportuno usare una min-heap e k pop: O(n+k*log(n)) che rimane comunque migliore dell'ordinamento.

Ma tutto ciò è inutile, viste le premesse: "usando il partizionamento".

Edit: dimenticavo, una volta ordinato l'array non ti servirebbe nemmeno scorrerlo...

[Wozywors]

ragazzi io ho provato a farlo con un bubble sort parziale ma non mi viene bene potete darmi una mano?

void bubblesort(int a1[],int n1,int k1)
{
    int t;
    int i=0,j;
        
    for(i=0;i<n1;i++)
    {
        for(j=0;j<k1;j++)
        {
            if(a1[j]>a1[j+1])
            {  
                t=a1[j];
                a1[j]=a1[j+1];
                a1[j+1]=t;
			}
        }
 	}
}

ho anche provato a fare un bubble sort inverso xchè mi sembrava più semplice ma niente