Java - ordenmaiento por mezcla

   
Vista:

ordenmaiento por mezcla

Publicado por jesus (1 intervención) el 11/01/2011 03:45:18
Alguien me podría facilitar un ejemplo de un algoritmo de ordenamiento del tipo Merge Sort en java?
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:ordenmaiento por mezcla

Publicado por aitor (86 intervenciones) el 11/01/2011 12:04:07
En informática, tipo de combinación o mergesort es un algoritmo de ordenación para la reordenación de las listas (o cualquier otra estructura de datos que sólo se puede acceder de forma secuencial, por ejemplo, secuencias de archivo) en un orden especificado. Es un ejemplo particularmente bueno de la divide y vencerás paradigma algorítmico. Es una especie de comparación.

Conceptualmente, la combinación de obras tipo de la siguiente manera:

1.Divide la lista sin ordenar en dos sublistas de la mitad del tamaño
2.Sort cada uno de los dos sublistas
3.Merge los dos sublistas, ordenados de nuevo en una lista ordenada.
El algoritmo fue inventado por John von Neumann en 1945.

El código siguiente muestra cómo implementar la fusión de ordenación en Java.

public static void mergeSort( Comparable [ ] a ) {
Comparable [ ] tmpArray = new Comparable[ a.length ];
mergeSort( a, tmpArray, 0, a.length - 1 );
}


private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
int left, int right ) {
if( left < right ) {
int center = ( left + right ) / 2;
mergeSort( a, tmpArray, left, center );
mergeSort( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}


private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
int leftPos, int rightPos, int rightEnd ) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;

// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];

while( leftPos <= leftEnd ) // Copy rest of first half
tmpArray[ tmpPos++ ] = a[ leftPos++ ];

while( rightPos <= rightEnd ) // Copy rest of right half
tmpArray[ tmpPos++ ] = a[ rightPos++ ];

// Copy tmpArray back
for( int i = 0; i < numElements; i++, rightEnd-- )
a[ rightEnd ] = tmpArray[ rightEnd ];
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

RE:ordenmaiento por mezcla

Publicado por yoni (1 intervención) el 02/11/2012 20:00:08
no sirve tu codigo, n o corre
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar