martes, 15 de junio de 2010
Sorting - Merge Sort
public static int[] mergeSort( int[] a)
{
if (a.length > 1)
{
int middle = (a.length/2);
int[] b = Arrays.copyOfRange(a, 0, middle);// copy a[0...middle-1] to b
int[] c = Arrays.copyOfRange(a, middle, a.length);//copy a[middle... a.length -1] to c
b = mergeSort(b);
c = mergeSort(c);
a = merge(b,c);
}
return a;
}
private static int[] merge(int[] b, int[] c)
{
int[] merged = new int[b.length + c.length ];
int i =0, j =0, k =0;
while (i < b.length && j < c.length)
{
if (b[i] <= c[j])
{
merged[k]= b[i];
i++;
}
else
{
merged[k]= c[j];
j++;
}
k++;
}
if (i == b.length)
System.arraycopy(c, j, merged, k, c.length-j);
else
System.arraycopy(b, i, merged, k,b.length-i);
return merged;
}
//Testing
public static void showArray(int array[])
{
System.out.print( "Array: [ ");
for(int i = 0; i < array.length; i++)
System.out.print(array[i]+ " ");
System.out.println("]");
}
public static void main(String args[])
{
int a[]={0,5,3,1,9,8,22,4,7,6,45};
showArray(a);
a=mergeSort(a);
showArray(a);
}
Suscribirse a:
Enviar comentarios (Atom)
No hay comentarios:
Publicar un comentario