Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - problema algoritmi di ordinamento (fusione & quicksort)
Forum - C/C++ - problema algoritmi di ordinamento (fusione & quicksort)

Avatar
slacer (Normal User)
Newbie


Messaggi: 13
Iscritto: 16/03/2010

Segnala al moderatore
Postato alle 13:17
Giovedì, 15/04/2010
Volevo chiedervi un chiarimento su i seguenti algoritmi di ordinamento:
FUSIONE:
Codice sorgente - presumibilmente C++

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4.  
  5. int *fusione(int *a,int sx,int cx,int dx,int n)
  6. {
  7. int *b=malloc(sizeof(int)*n);
  8. int i=sx;
  9. int j=cx+1;
  10. int k=0;
  11. while((i<=cx) && (j<=dx)){
  12. if(a[i]<=a[j]){
  13. b[k]=a[i];
  14. i++;
  15. }else{
  16.         b[k]=a[j];
  17.         j++;
  18. } k++;
  19. }
  20. while(i<=cx){
  21. b[k]=a[i];
  22. i++;
  23. k++;
  24. }
  25. while(j<=dx){
  26. b[k]=a[j];
  27. j++;
  28. k++;
  29. }
  30. for(k=sx;k<=dx;k++)a[k]=b[k-sx];
  31. return a;
  32. }
  33.  
  34. void *merge(int *a,int sx,int dx,int n){
  35. int cx;
  36. if(sx<dx){
  37. cx=(sx+dx)/2;
  38. merge(a,sx,cx,n);
  39. merge(a,cx+1,dx,n);
  40. fusione(a,sx,cx,dx,n);
  41. }
  42. }
  43.  
  44. int *leggi(int n){
  45. srand(time(NULL));
  46. printf("Inserisci i valori automaticamente nel vettore di %d elementi\n",n);
  47. int j;
  48. int *array=malloc(sizeof(int)*n);
  49. int i=0;
  50. while(i<n){
  51. j = rand()%100+1;
  52. array[i]=j;
  53. i++;
  54. }
  55. return array;
  56. }
  57.  
  58. void stampa(int *sequenza,int n)
  59. {
  60. int i;
  61. printf("\nIl tuo vettore di %d elementi\n",n);
  62. for(i=0;i<n;i++){      
  63. printf("|%d|",sequenza[i]);
  64. }
  65. printf("\n");
  66. }
  67.  
  68. int main(){
  69. int n;
  70. printf("Inserisci la grandezza del vettore\n");
  71. scanf("%d",&n);
  72. int *arr=malloc(sizeof(int)*n);
  73. arr=leggi(n);
  74. stampa(arr,n);
  75. merge(arr,0,n-1,n);
  76. stampa(arr,n);
  77. return 0;
  78. }


QUICKSORT:
Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>
  4.  
  5. int *leggi(int n){
  6. srand(time(NULL));
  7. printf("Inserisci i valori automaticamente nel vettore di %d elementi\n",n);
  8. int j;
  9. int *array=malloc(sizeof(int)*n);
  10. int i=0;
  11. while(i<n){
  12. j = rand()%100+1;
  13. array[i]=j;
  14. i++;
  15. }
  16. return array;
  17. }
  18.  
  19. void stampa(int *sequenza,int n)
  20. {
  21. int i;
  22. printf("\nIl tuo vettore di %d elementi\n",n);
  23. for(i=0;i<n;i++){      
  24. printf("|%d|",sequenza[i]);
  25. }
  26. printf("\n");
  27. }
  28.  
  29. void scambia(int i,int j,int *arr)
  30. {
  31. int temp=arr[j];
  32. arr[j]=arr[i];
  33. arr[i]=temp;
  34.  
  35. }
  36.  
  37. int distribuzione(int *arr,int sx,int px,int dx)
  38. {
  39. if(px!=dx) scambia(px,dx,arr);
  40. int i=sx;
  41. int j=dx-1;
  42. while (i<j){
  43. while((i<j) && (arr[i] <= arr[dx])) i++;
  44. while((i<j) && (arr[j] >= arr[dx])) j--;
  45. if(i!=dx)scambia(i,j,arr);
  46. }
  47. if(i!=dx)scambia(i,dx,arr);
  48. return i;
  49. }
  50.  
  51. void *quicksort(int *arr,int sx,int dx)
  52. {
  53. if(sx<dx){
  54. printf("Scegli perno tra l'intervallo %d e %d\n",sx,dx);
  55. int perno;
  56. do{
  57. scanf("%d",&perno);
  58. }while(perno<sx || perno>dx);
  59. perno = distribuzione(arr,sx,perno,dx);
  60. quicksort(arr,sx,perno-1);
  61. quicksort(arr,perno+1,dx);
  62. }
  63. }
  64.  
  65.  
  66. int main(){
  67. int n;
  68. printf("Inserisci grandezza del vettore\n");
  69. scanf("%d",&n);
  70. int *arr=malloc(sizeof(int)*n);
  71. arr=leggi(n);
  72. stampa(arr,n);
  73. quicksort(arr,0,n-1);
  74. stampa(arr,n);
  75. return 0;
  76. }



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!


La fisica studia il mondo come funziona... Nell informatica sei tu che crei il mondo, e puoi essere un "dio", in piccola scala.
PM Quote
Avatar
Poggi Marco (Member)
Guru


Messaggi: 951
Iscritto: 05/01/2010

Segnala al moderatore
Postato alle 18:59
Giovedì, 15/04/2010
Ciao!

Ho letti i tuoi programmi, e ho notato che continui ad allocare un vettore in memoria senza mai rilasciarlo.

Questa è una procedura molto pericolosa, soprattutto per le funzioni ricorsive.


Nulla va più veloce della luce, quindi rilassati.
PM Quote
Avatar
slacer (Normal User)
Newbie


Messaggi: 13
Iscritto: 16/03/2010

Segnala al moderatore
Postato alle 15:54
Domenica, 18/04/2010
giusto ! In teoria me l'avevano spiegato ma in pratica mai xD ora modifico... ma il problema rimane un altro :S


La fisica studia il mondo come funziona... Nell informatica sei tu che crei il mondo, e puoi essere un "dio", in piccola scala.
PM Quote