Diferenças no mergesort?

0 respostas
P

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

Criado 9 de maio de 2010
Respostas 0
Participantes 1