PDA

Visualizza la versione completa : [C] Partizionamento di un array


Kyros_
03-01-2017, 16:45
ciao a tutti, mi serve un programma che fa il Partizionamento in 2 porzioni di un array in base ad un valore di discrimine.
io ho usato questo algoritmo ma non so della sua effettiva funzione :
#include <stdio.h>
void insertion_sort(int n,int a[]);
int main(){
int i;
int n;
int num;
printf("inserimento dimesione array \n");
scanf("%d",&n);
int a[n];
for(i=0;i<n;i++){
printf("numero %d \n",i);
scanf("%d",&num);
a[i]=num;
}
insertion_sort(n,a);
}
void insertion_sort(int n,int a[]){
int i;
int temp;
int j;
int m;
m=3;//valore discriminante
for(i=1;i<n;i++){
temp=a[i];
j=i-1;
while(j>=0 && a[j]>temp){
if(a[j]>m){
a[j+1]=a[j];
j--;
}
}
a[j+1]=temp;
}

for(i=0;i<n;i++){
printf(" %d ",a[i]);
}
}

Scara95
03-01-2017, 20:58
Se devi solo distinguere rispetto ad una soglia non serve ordinare l'array, puoi farlo in complessitÓ lineare ( O(N) ) e ordinando parzialmente

#include <stdio.h>

int partition(int a[], int n, int e) {
int from, to;
for(from = to = 0; from < n; ++from) {
if(a[from] < e) {
int tmp = a[to];
a[to] = a[from];
a[from] = tmp;
++to;
}
}
return to;
}


#define N 8


int main(void) {
int i;
int test[N] = {1283, 23, 5, 65, 2, 8, 56, 32};
int split_on = 56;
int split = partition(test, N, split_on);
printf("Minori della soglia(%d): ", split_on);
for(i = 0; i < split; ++i) {
printf("%d ", test[i]);
}
printf("\nMaggiori o uguali alla soglia(%d): ", split_on);
for(i = split; i < N; ++i) {
printf("%d ", test[i]);
}
return 0;
}

Kyros_
05-01-2017, 13:48
Grazie mille

Loading