slacer (Normal User)
Newbie
Messaggi: 13
Iscritto: 16/03/2010
|
Volevo chiedervi un chiarimento su i seguenti algoritmi di ordinamento:
FUSIONE:
Codice sorgente - presumibilmente C++ |
#include <stdlib.h> #include <stdio.h> #include <time.h> int *fusione(int *a,int sx,int cx,int dx,int n) { int *b=malloc(sizeof(int)*n); int i=sx; int j=cx+1; int k=0; while((i<=cx) && (j<=dx)){ if(a[i]<=a[j]){ b[k]=a[i]; i++; }else{ b[k]=a[j]; j++; } k++; } while(i<=cx){ b[k]=a[i]; i++; k++; } while(j<=dx){ b[k]=a[j]; j++; k++; } for(k=sx;k<=dx;k++)a[k]=b[k-sx]; return a; } void *merge(int *a,int sx,int dx,int n){ int cx; if(sx<dx){ cx=(sx+dx)/2; merge(a,sx,cx,n); merge(a,cx+1,dx,n); fusione(a,sx,cx,dx,n); } } int *leggi(int n){ srand(time(NULL)); printf("Inserisci i valori automaticamente nel vettore di %d elementi\n",n); int j; int *array=malloc(sizeof(int)*n); int i=0; while(i<n){ j = rand()%100+1; array[i]=j; i++; } return array; } void stampa(int *sequenza,int n) { int i; printf("\nIl tuo vettore di %d elementi\n",n); for(i=0;i<n;i++){ printf("|%d|",sequenza[i]); } printf("\n"); } int main(){ int n; printf("Inserisci la grandezza del vettore\n"); scanf("%d",&n); int *arr=malloc(sizeof(int)*n); arr=leggi(n); stampa(arr,n); merge(arr,0,n-1,n); stampa(arr,n); return 0; }
|
QUICKSORT:
Codice sorgente - presumibilmente C++ |
#include <stdio.h> #include <time.h> #include <stdlib.h> int *leggi(int n){ srand(time(NULL)); printf("Inserisci i valori automaticamente nel vettore di %d elementi\n",n); int j; int *array=malloc(sizeof(int)*n); int i=0; while(i<n){ j = rand()%100+1; array[i]=j; i++; } return array; } void stampa(int *sequenza,int n) { int i; printf("\nIl tuo vettore di %d elementi\n",n); for(i=0;i<n;i++){ printf("|%d|",sequenza[i]); } printf("\n"); } void scambia(int i,int j,int *arr) { int temp=arr[j]; arr[j]=arr[i]; arr[i]=temp; } int distribuzione(int *arr,int sx,int px,int dx) { if(px!=dx) scambia(px,dx,arr); int i=sx; int j=dx-1; while (i<j){ while((i<j) && (arr[i] <= arr[dx])) i++; while((i<j) && (arr[j] >= arr[dx])) j--; if(i!=dx)scambia(i,j,arr); } if(i!=dx)scambia(i,dx,arr); return i; } void *quicksort(int *arr,int sx,int dx) { if(sx<dx){ printf("Scegli perno tra l'intervallo %d e %d\n",sx,dx); int perno; do{ scanf("%d",&perno); }while(perno<sx || perno>dx); perno = distribuzione(arr,sx,perno,dx); quicksort(arr,sx,perno-1); quicksort(arr,perno+1,dx); } } int main(){ int n; printf("Inserisci grandezza del vettore\n"); scanf("%d",&n); int *arr=malloc(sizeof(int)*n); arr=leggi(n); stampa(arr,n); quicksort(arr,0,n-1); stampa(arr,n); return 0; }
|
Il primo funziona sempre, il secondo quasi mai... eppure l'ho tradotto da uno pseudo-codice dal libro e controllato non so quante volte... mi sembra di aver capito che pių l'array č piccolo, pių il quicksort funziona bene... ma a me funziona il 5% delle volte e solamente su array piccoli! |
