Pages: [1]   Go Down
Print
Author Topic: Algoritmi QuickSort e MergeSort  (Read 1368 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« 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.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #1 on: 07-11-2010, 23:51:17 »

Posta tu piuttosto i tuoi e vedremo di trovare i problemi di implementazione .
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 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;
}


}
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #3 on: 08-11-2010, 00:19:50 »

se ti va out of range hai provato a controllare le condizioni di uscita dei cicli?  testate
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 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...
« Last Edit: 08-11-2010, 00:26:08 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #5 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 
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #6 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++] );
Logged
Pages: [1]   Go Up
Print
Jump to: