Arrays.sort (Objeto [] a): ¿cómo se implementa?

¿Hay algún recurso sobre cómo se implementa el mergeSort utilizado por Arrays.sort (Object [] a)? Si bien está documentado bastante bien, me cuesta entenderlo (especialmente por qué se cambian el src y el dest cuando se llama recursivamente a mergeSort()).Arrays.sort (Objeto [] a): ¿cómo se implementa?

Fuente

2010-02-07 helpermethod

http://www.docjar.com/html/api/java/util/Arrays.java.html aquí está el código fuente – Bozho

Bozho, ¡deberías haber publicado una respuesta! – Will

Parece que el trabajo real comienza en la línea 486. – MatrixFrog

Here is the source de java.util.Arrays.

En realidad, usted tiene ese código fuente en el JDK - simplemente abra java.util.Arrays en su IDE y el código fuente + los comentarios aparecerán. Si no tiene un IDE, mire JDK_HOME\src.zip

Luego, colóquelo en su IDE y rastree cómo funciona.

puntos de interrupción de venta (y ejecutar un programa en modo de depuración)
uso System.out.println(..)
piezas de cambio de él para ver cómo se reflejan.
leer el prestar atención wikipedia article about merge sort
a este comentario: // Recursively sort halves of dest into src

Fuente

2010-02-07 20:02:55 Bozho

** Aparece ** el OP ya vio la fuente (ya que menciona el hecho de que las matrices 'src' y' dest' se cambian cuando se llama de forma recursiva) pero le resulta difícil entender la lógica. –

hm, sí. Di algunos consejos sobre cómo entenderlo mejor. – Bozho

Podría estar equivocado, por supuesto ... De todos modos, iba a sugerir el OP para usar el depurador de * poor-man * (poniendo algunos System.out.println en el algoritmo), ¡pero me lo ganaste! –

cada vez que tenían la misma confusión con usted. Según lo que entiendo, la razón de este cambio es muy simple: hacer que el paso de fusión sea más fácil. Sin magia

private static void mergeSortWithoutSwitch(Object[] src, Object[] dest, int low, int high, int off) { 
    int length = high - low; 

    // Insertion sort on smallest arrays 
    if (length < INSERTIONSORT_THRESHOLD) { 
     for (int i = low; i < high; i++) 
      for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--) 
       swap(dest, j, j - 1); 
     return; 
    } 

    // Recursively sort halves of dest into src 
    int destLow = low; 
    int destHigh = high; 
    low += off; 
    high += off; 
    int mid = (low + high) >>> 1; 
    mergeSortWithoutSwitch(src, dest, low, mid, off); 
    mergeSortWithoutSwitch(src, dest, mid, high, off); 

    // If list is already sorted, just copy from src to dest. This is an 
    // optimization that results in faster sorts for nearly ordered lists. 
    if (((Comparable) dest[mid - 1]).compareTo(dest[mid]) <= 0) { 
     return; 
    } 

    // Merge sorted halves (now in src) into dest 
    for (int i = destLow, p = low, q = mid; i < destHigh; i++) { 
     if (q >= high || p < mid && ((Comparable) dest[p]).compareTo(dest[q]) <= 0) 
      src[i] = dest[p++]; 
     else 
      src[i] = dest[q++]; 
    } 

    // copy back 
    for (int i = destLow; i < destHigh; i++) { 
     dest[i] = src[i]; 
    } 

}

arriba es la aplicación sin tener que cambiar, a partir del código, se puede ver que necesitamos un paso más en la fusión - copiar de nuevo. Creo que la nomenclatura de los parámetros en mergeSort es un poco confusa, ya que src es una matriz auxiliar que solo se usa en el paso de fusión, será mejor nombrarla con aux (incluso podemos eliminarla de la firma del método, y crear una variable local al fusionarse). Y dest es la matriz de resultados.

Fuente

2010-11-19 07:47:32 lostinmoney

Arrays.sort (Objeto [] a): ¿cómo se implementa?

Respuesta

Cuestiones relacionadas