Problema algoritmi di ordinamento

[Darèios89]

Ho provato a scrivere gli algoritmi Merge-Sort e Quick-Sort, ma ci sono dei problemi.

Per il QuickSort, ho uno stackOverflow che non capisco da cosa dipenda,

public class QuickSort
{
	public static void main(String [] args)
	{
		int [] a={5,4,6,7,8,0};
		QSort(a,0,a.length-1);
		for(int i=0; i<a.length; i++)
		System.out.print(a[i]+" ");
	}
	
	
	public static void QSort(int [] A, int i, int j)
	{
		if(i>=j) return;
		
			int r=partition(A,i,j);   //primo stackOverflow
			QSort(A,i,r);             //Altro stackOverflow che si ripete.
			QSort(A,r+1,j);
	}
	
	public static int partition(int [] A, int p, int r)
	{
		int i=p-1;
		int j=r+1;
		int x=A[r];
		
		while(true)
		{
			do j=j-1;
			while(A[j]>x);
				
			
				do i=i+1;
				while(A[i]<x);
					
			    
					if(i<j)
						swap(A,i,j);
					
			else return j;
		}
	}
	
	public static void swap(int [] A,int a, int b)
	{
		int tmp=A[a];
		A[a]=A[b];
		A[b]=tmp;
	}
	
	
}

E poi problemi nel Merge-Sort, l'ho preso da wikipedia, mi va in loop...

public class MergeSort
{
	
	public static void main(String [] args)
	{
		int [] a={3,6,5,7,9,8,0,5};
		MSort(a,0,a.length-1);
		for(int i=0; i<a.length; i++)
		System.out.print(a[i]+" ");
	}
	
	
	public static void merge(int [] a, int left,int center, int right)
	{
		int [] S=new int[a.length-1];
		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; k<right; k++)      //non sono molto convinto del funzionamento di questa istruzione
		a[k]=S[k-left];
	}
	
	
	public static void MSort(int [] a,int left, int right)
	{
		
		if(left>=right) return;
		
			
			int center=(left+right)/2;
				MSort(a,left,center);
				MSort(a,center+1,right);
				merge(a, left,center,right);
	
	}
}

[bstefano79]

Per ora rispondo solo sul quicksort

Originariamente inviato da Darèios89
Per il QuickSort, ho uno stackOverflow che non capisco da cosa dipenda,

Semplice fai chiamate ricorsive infinite e alla fine la memoria finisce ^_^ scusa il gioco di parole

prima cosa che non riguarda l'algoritmo ma lo stile di programmazione che è non è cosa meno importante, più chiari si è e meno si rischia di sbagliare, più chiari si è e più facile è che i chi legga il nostro programma o quando noi stessi andremo a leggere i nostri programmi dopo mesi capisca il codice
se possibile non fare mai dei while(true)

while(true)
{
      ......
      if(i<j)
           swap(A,i,j);
                        
      else return j;
} 

perchè non scrivere

do
{
.......
swap(A,i,j);
}while(i>=j)
return j;

passiamo all'algoritmo.... è proprio tutto sbagliato da riscrivere completamente!!!!!

l'idea del Quick è quella che passato un vettore e 2 indici (i,j con i<=j) si scegliere un terzo indice (r in genere casualmente) tale che (i<=r<=j), a questo punto per ogni elemento del vettore si controlla con quello di indice r se è più grande si sposta a destra, se è più piccolo a sinistra in modo tale che l'elemento r-essimo risulti nella posizione che gli spetta

esempio con pseudopseudocodice anzi quasi a parole

Vet=(67 ,34, 12, 9, 1, 23, 0) i=0 ,j=6

Quick(Vet,i,j)
{
     - se i<j allora scelgo r che sarà il nostro pivot fra i,j che hanno valori 0,6 in questo caso suppiniamo 2
           altrimenti ho terminato
     -  Vet[2]=12
     - sposto gli elementi che possono risultare anche non ordinati i maggiori di 12 a destra e quelli minori a sinistra Vet=(9, 1, 0, 12, 67, 34) 12 è sicuramente nella sua posizione ordinata ovvero Vet[3]=12 devo ora andare a rieseguire il passo su due sottoinsiemi a destra e sinistra
     - chiamo Quick(Vet,0,2) e Quick(Vet,4,6) ovvero Quick(Vet,i,indice dove è finito l'elemnto pivot - 1) e Quick(Vet,indice dove è finito l'elemnto pivot + 1, j) ricorsivamente coì andrai a ordinare il vettore
}

[Darèios89]

Scusa perchè è tutto sbagliato?
Quello che dici, su decrementare o incrementare l'indice verrebbe fatto all'interno del while(true)
Perchè tutto da rifare?
Io davvero non so dove sbaglio.