Oi,
estava a tentar implemetar o MergeSort, no entanto meu código não está a funcionar correctamente. Fui à procura de uma implementação que funcionasse e não consegui encontrar diferença entre o meu código e o que funciona.
Conseguem ver se existe differença, porque realmente não estou a descobrir?
O meu código (não funciona):
public class MiddlePoint {
int[] t;
// Helperarray
int[] helper;
public MiddlePoint(int[] t)
{
this.t=t;
this.helper = new int[t.length];
}
private void middle(int start, int end)
{
if(start<end)
{
int m = (start+end)/2;
middle(start, m);
middle(m+1, end);
merge(start, m, end);
}
}
private void merge(int low, int middle, int high)
{
int i = low, j = middle+1, k=0;
while(i<=middle && j<=high)
{
if (t[i] < t[j])
helper[k++] = t[i++];
else
helper[k++] = t[j++];
}
while(i<=middle)
helper[k++] = t[i++];
while(j<=high)
helper[k++] = t[j++];
for (k = 0; k < high-low; k++)
t[k] = helper[k];
}
private void printArray()
{
for(int i=0; i<t.length; i++)
System.out.print(t[i] + ",");
System.out.println();
System.out.println();
for(int i=0; i<helper.length; i++)
System.out.print(helper[i] + ",");
System.out.println();
}
public static void main(String[] args) {
int t[] = new int[]{50,43,67,89,24,12,12,8,7,1};
MiddlePoint mp = new MiddlePoint(t);
mp.middle(0, t.length-1);
mp.printArray();
}
}
A implementação que funciona:
public class MergeSort
{
public static void mergesort(int[] data, int start, int n)
{
int fsthalf; // Size of the first half of the array
int sndhalf; // Size of the second half of the array
if (n > 1)
{
// Compute sizes of the two halves
fsthalf = n / 2;
sndhalf = n - fsthalf;
mergesort(data, start, fsthalf); // Sort data[first] through data[first+n1-1]
mergesort(data, start + fsthalf, sndhalf); // Sort data[first+n1] to the end
mergeSortedHalves(data, start, fsthalf, sndhalf);
}
}
private static void mergeSortedHalves(int[] data, int start, int fsthalf, int sndhalf)
{
int[] temp = new int[fsthalf+sndhalf]; // Allocate the temporary array
int copied = 0; // Number of elements copied from data to temp
int copied1 = 0; // Number copied from the first half of data
int copied2 = 0; // Number copied from the second half of data
int i; // Array index to copy from temp back into data
// Merge elements, copying from two halves of data to the temporary array.
while ((copied1 < fsthalf) && (copied2 < sndhalf))
{
// coloca os elementos no temp de forma crescente.
if (data[start + copied1] < data[start + fsthalf + copied2])
temp[copied++] = data[start + (copied1++)];
else
temp[copied++] = data[start + fsthalf + (copied2++)];
}
// Copy any remaining entries in the left and right subarrays.
// só um dos whiles é executado por cada passagem.
while (copied1 < fsthalf)
temp[copied++] = data[start + (copied1++)];
while (copied2 < sndhalf)
temp[copied++] = data[start + fsthalf + (copied2++)];
// Copy from temp back to the data array.
for (i = 0; i < fsthalf+sndhalf; i++)
data[start + i] = temp[i];
}
public static void main(String[ ] args)
{
final String BLANKS = " "; // A String of two blanks
int i; // Array index
int[ ] data = {90, 80, 70, 60, 50, 40, 30, 20, 10};
// Print the array before sorting:
System.out.println("Here is the entire original array:");
for (i = 0; i < data.length; i++)
System.out.print(data[i] + BLANKS);
System.out.println( );
// Sort the numbers, and print the result with two blanks after each number.
mergesort(data, 0, data.length);
System.out.println("I have sorted all but the first and last numbers.");
System.out.println("The numbers are now:");
for (i = 0; i < data.length; i++)
System.out.print(data[i] + BLANKS);
System.out.println( );
}
}
Obrigado,
PSC