Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: Daréios89 on 07-11-2010, 22:45:55



Title: Algoritmi QuickSort e MergeSort
Post by: Daréios89 on 07-11-2010, 22:45:55
Scusate ragazzi....ho provato ad implementare i metodi QuickSort e MergeSort in Java, ma non sono riuscito a farli funzionare, utilizzando gli array vanno sempre out of range, non sono riuscito a capire cosa ho sbagliato.
Non è che qualcuno potrebbe postare gli algoritmi funzionanti in Java in modo da averli e studiarli?

Grazie.


Title: Re:Algoritmi QuickSort e MergeSort
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 07-11-2010, 23:51:17
Posta tu piuttosto i tuoi e vedremo di trovare i problemi di implementazione .wink.


Title: Re:Algoritmi QuickSort e MergeSort
Post by: Daréios89 on 08-11-2010, 00:19:31
MergeSort:
Code:
public class MergeSort
{

public static void main(String [] args)
{
int [] a={3,6,5,7,9,8,0,5};
MSort(a,0,a.length);

}


public static void merge(int [] a, int left,int center, int right)
{
int [] S=new int[a.length];
int i= left;
int j=center+1;
int k=0;


while(i<center && j<right)
{
if(a[i]<a[j])
{
S[k++]=a[i];
i=i++;
}
else if(a[i]>a[j])
{
S[k++]=a[j];
j=j++;
}
}

while(i<center)
{
S[k++]=a[i];
i=i++;
}

while(j<right)
{
S[k++]=a[j];
j=j++;
}

for(k=left; left<=right; left++)
a[k]=S[k-left];
}


public static void MSort(int [] a,int left, int right)
{

if(left>=right) return;
else
{

int center=(left+right)/2;
MSort(a,left,center);
MSort(a,center+1,right);
merge(a, left,center,right);

}



}
}


QuickSort:
Code:
public class QuickSort
{
public static void main(String [] args)
{
int [] a={5,4,6,7,8,0};
QSort(a,0,a.length-1);
}


public static void QSort(int [] A, int i, int r)
{
if(i>=r) return;
else{
int n=partition(A,i,r);
QSort(A,i,n);
QSort(A,n+1,r);
}
}

public static int partition(int [] A, int i, int r)
{
int a=i-1;
int b=r+1;
int p=A[r];

while(true)
{
b--;

while(A[b]>p)
b--;

    a=a+1;

while(A[a]<p)
a=a+1;
if(a<b)
swap(A, a, b);

else return p;
}
}

public static void swap(int [] A,int a, int b)
{
int tmp=A[a];
A[a]=A[b];
A[b]=tmp;
}


}


Title: Re:Algoritmi QuickSort e MergeSort
Post by: shiny on 08-11-2010, 00:19:50
se ti va out of range hai provato a controllare le condizioni di uscita dei cicli?  :-)|


Title: Re:Algoritmi QuickSort e MergeSort
Post by: Daréios89 on 08-11-2010, 00:21:06
Non so...ho controllato più volte ma....non ho saputo risolvere, forse perchè mi sono basato sullo pseudocodice..dopodomani c'è l'esame ma non sono riuscito a sistemarlo nei giorni scorsi...


Title: Re:Algoritmi QuickSort e MergeSort
Post by: shiny on 08-11-2010, 10:07:56
io al momento non ho modo di provare questo codice comunque se ti sei basato sullo pseudo codice vedi che di solito gli indici degli array nello pseudo codice vanno da 1 a n mentre in java gli indici vanno da 0 a n-1 quindi il mio consiglio e' di vedere quale ciclo ti da quell'errore e provare a mettere un -1 nella condizione di uscita  .ciaociao


Title: Re:Algoritmi QuickSort e MergeSort
Post by: shiny on 08-11-2010, 10:28:09
Guarda leggendo il codice non sono riuscito a capire cosa volessi fare qui...
Code:
for(k=left; left<=right; left++)
a[k]=S[k-left];
non si dovrebbero prendere tutti gli elementi dell'array temporaneo e spostarli in quello principale ovvero qualcosa del genere?
Code:
for( k=0, i=left; i<=right;
            a[i++] = S[k++] );