PDA

Visualizza la versione completa : [C] Ricerca del k-mo elemento minimo di un array


Kyros_
06-01-2017, 16:09
ricerca del k-mo elemento minimo di un array usando il partizionamento, dove k non lo conosciamo

Scara95
06-01-2017, 17:07
Comincia col proporre almeno lo scheletro della soluzione

Kyros_
06-01-2017, 17:48
#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_
09-01-2017, 10:50
up

Scara95
11-01-2017, 10:52
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
14-01-2017, 15:31
Secondo me ti conviene semplicemente ordinare tutto l'array e poi scorrerlo per trovare il k-esimo minimo.

Scara95
14-01-2017, 17:58
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
14-12-2017, 13:16
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

Loading