Unisci domande di implementazione di ordinamento in Java

Sono in un corso di algoritmi e sto imparando a merge sort. Il nostro professore ci ha consigliato di provare ad implementare lo pseudo codice fornito nel libro.

  1. Sono corretto nell'usare Integer.MAX_VALUE come valore sentinella quando ordinamento di un array di numeri interi (utilizzato nelle righe 8 e 9 nell'unione metodo pseudo codice sotto)?
  2. Per la riga 2 del metodo pseudo codice Merge-Sort, è corretto codificarlo in Java usando la matematica.ceil () come ho fatto io? (Edit: in realtà è floor e ho aggiornato il mio codice per riflettere questo.)

Se vedete altri errori per favore fatemelo sapere!

Ecco lo pseudo codice che il libro fornisce per l'ordinamento di unione. unisci algoritmo di ordinamento parte 1

unisci algoritmo di ordinamento parte 2

E, ecco come l'ho codificato in Java:

public void mergeSort(int[] arrNums, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(arrNums, p, q);
        mergeSort(arrNums, q + 1, r);
        merge(arrNums, p, q, r);
    }
}

public void merge(int[] arrNums, int p, int q, int r) {
    int nOne = q - p + 1;
    int nTwo = r - q;

    int[] arrLeft = new int[nOne + 1];
    int[] arrRight = new int[nTwo + 1];

    for (int i = 0; i < nOne; i++) {
        arrLeft[i] = arrNums[p + i - 1];
    }

    for (int j = 0; j < nTwo; j++) {
        arrRight[j] = arrNums[q + j];
    }

    arrLeft[nOne] = Integer.MAX_VALUE;
    arrRight[nTwo] = Integer.MAX_VALUE;

    // Tracks arrLeft index
    int i = 0;

    // Tracks arrRight index
    int j = 0;

    for (int k = p; k < r; k++) {
        if (arrLeft[i] <= arrRight[j]) {
            arrNums[k] = arrLeft[i];
            i++;
        } else {
            arrNums[k] = arrRight[j];
            j++;
        }
    }
}
Author: Nishant, 2017-04-02
Source

2 answers

L'ultimo ciclo for nel metodo merge, la variabile k dovrebbe iniziare da p - 1: 

for (int k = p - 1; k < r; k++) {
    if (arrLeft[i] <= arrRight[j]) {
        arrNums[k] = arrLeft[i];
        i++;
    } else {
        arrNums[k] = arrRight[j];
        j++;
    }
}

Lo pseudo codice in molti libri di testo ama avviare l'indice dell'array da 1, quindi qui è necessario sottrarlo per 1.

 1
Author: shizhz, 2017-04-02 00:17:40

L'ho implementato qualche giorno fa, se qualcuno sarà interessato.

private static void mergeSort(double[] arr, int start, int end){
    if(start < end){
        int mid = ( start + end ) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }
}


private static void Merge(double[] arr, int start, int mid, int end){

    double[] leftArray = new double[mid - start + 2];
    double[] rightArray = new double[end - mid + 1];
    for(int i = start; i <= mid; i++ )
        leftArray[i - start] = arr[i];
    for (int i = mid + 1; i <= end; i++ )
        rightArray[i - mid - 1] = arr[i];

    leftArray[mid - start + 1] = Double.POSITIVE_INFINITY;
    rightArray[end - mid] = Double.POSITIVE_INFINITY;

    int leftIndex = 0, rightIndex = 0;

    for (int k = start; k <= end; k++){
        if(leftArray[leftIndex] <= rightArray[rightIndex])
            arr[k] = leftArray[leftIndex++];
        else
            arr[k] = rightArray[rightIndex++];
    }   
}
 0
Author: sheldonzy, 2017-08-20 13:53:55