ricerca del k-mo elemento minimo di un array usando il partizionamento, dove k non lo conosciamo
ricerca del k-mo elemento minimo di un array usando il partizionamento, dove k non lo conosciamo
Comincia col proporre almeno lo scheletro della soluzione
"Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares
codice:#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; }
Ultima modifica di LeleFT; 09-01-2017 a 12:09 Motivo: Aggiunti i tag CODE
up
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)
"Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares
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...
"Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares
ragazzi io ho provato a farlo con un bubble sort parziale ma non mi viene bene potete darmi una mano?
ho anche provato a fare un bubble sort inverso xchè mi sembrava più semplice ma nientecodice: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; } } } }
Ultima modifica di alka; 28-12-2017 a 11:06 Motivo: Formattazione del codice tramite tag CODE