Merge sort Java

Question

Sto cercando di fare un metodo di merge sort, ma continua a dare i tipi sbagliati. Dove devo cambiare per renderlo realmente ordinare l'array? Quale parte del codice deve essere diverso? Grazie per il tuo tempo.

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {  
        int elements = (rHigh - lHigh +1) ;  
        int[] temp = new int[elements];
        int num = left;
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= array[right]) {
          temp[num] = array[left];
          left++;
        }
        else {
          temp[num] = array[right];
          right++;
        }
       num++;   
      }
     while (left <= right){
        temp[num] = array[left]; // I'm getting an exception here, and is it because of the num???
        left += 1;
        num += 1;  
     }  
     while (right <= rHigh) {
        temp[num] = array[right];
        right += 1;
        num += 1;  
     }  
     for (int i=0; i < elements; i++){
       array[rHigh] = temp[rHigh];
       rHigh -= 1;   
     }

EDIT: ora il Mergesort realtà non ordinare i numeri, qualcuno può dirmi dove specificamente è? soprattutto quando stampo il "Testing merge sort" parte.

Answer 1

Prima di tutto, sto assumendo questo è accademico, piuttosto che pratico, dal momento che non si sta usando una costruito in funzione di ordinamento. Detto questo, ecco qualche aiuto per ottenere in movimento nella giusta direzione:

Di solito, si può pensare ad un merge sort come due diversi metodi: una funzione merge (), che fonde due liste ordinate in una lista ordinata, e mergesort (), che rompe in modo ricorsivo l'elenco in elenchi di elementi singoli. Dal momento che una sola lista elemento è ordinato già, è quindi unire tutte le liste insieme in un unico grande lista ordinata.

Ecco un po 'fuori mano pseudo-codice:

merge(A, B):
  C = empty list

  While A and B are not empty:
    If the first element of A is smaller than the first element of B:
      Remove first element of A.
      Add it to the end of C.
    Otherwise:
      Remove first element of B.
      Add it to the end of C.

  If A or B still contains elements, add them to the end of C.

mergeSort(A):
  if length of A is 1:
    return A

  Split A into two lists, L and R.

  Q = merge(mergeSort(L), mergeSort(R))

  return Q

Forse ti aiuto a chiarire dove si vuole andare.

In caso contrario, c'è sempre MergeSort a wikipedia.

Ulteriori :

Per aiutarti, ecco alcuni commenti inline nel codice.

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {   
        // what do lHigh and rHigh represent?

        int elements = (rHigh - lHigh +1) ;     
        int[] temp = new int[elements];
        int num = left;

      // what does this while loop do **conceptually**? 
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= a[right]) {
          // where is 'pos' declared or defined?
          temp[pos] = a[left];
          // where is leftLow declared or defined? Did you mean 'left' instead?
          leftLow ++;
        }
        else {
          temp[num] = a[right];
          right ++;
        }
       num++;   
      }

     // what does this while loop do **conceptually**?
     while (left <= right){
        // At this point, what is the value of 'num'?
        temp[num] = a[left];
        left += 1;
        num += 1;   
     }
     while (right <= rHigh) {
        temp[num] = a[right];
        right += 1;
        num += 1;       
     }
     // Maybe you meant a[i] = temp[i]?
     for (int i=0; i < elements; i++){
       // what happens if rHigh is less than elements at this point? Could
       // rHigh ever become negative? This would be a runtime error if it did
       a[rHigh] = temp[rHigh];
       rHigh -= 1;      
     }

Sono volutamente vaga essere così si pensa l'algoritmo. Provare a inserire i tuoi commenti nel codice. Se è possibile scrivere ciò che sta accadendo concettualmente, quindi non avere bisogno di Stack Overflow:)

I miei pensieri qui sono che non si sta implementando questo modo corretto. Questo è perché sembra che stai toccando solo gli elementi dell'array solo una volta (o vicino ad una sola volta). Questo significa che hai uno scenario peggiore di O (N) ordinamento richiede generalmente almeno O(N * log N) e da quello che so, le versioni più semplici di merge sort sono in realtà O(N^2).

Altro:

Nel implementazione più semplice di merge sort, mi sarei aspettato di vedere una sorta di ricorsione nel metodo mergesort (). Questo perché merge sort è generalmente definito ricorsivamente. Ci sono modi per farlo in modo iterativo utilizzando cicli for e while, ma io sicuramente non lo consiglio come strumento di apprendimento fino ad arrivare in modo ricorsivo.

Onestamente, vi suggerisco di usare sia il mio pseudo-codice o il pseudo-codice si può trovare in un articolo di Wikipedia per implementare questo e ricominciare con il codice. Se lo si fa e non funziona correttamente ancora, postare qui e ti aiuteremo si lavora il tiro.

Cheers!

E infine:

  // Precondition: array[left..lHigh] is sorted and array[right...rHigh] is sorted.
  // Postcondition: array[left..rHigh] contains the same elements of the above parts, sorted.
  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {   
        // temp[] needs to be as large as the number of elements you're sorting (not half!)
        //int elements = (rHigh - lHigh +1) ;
        int elements = rHigh - left;

        int[] temp = new int[elements];

        // this is your index into the temp array
        int num = left;

        // now you need to create indices into your two lists
        int iL = left;
        int iR = right;

        // Pseudo code... when you code this, make use of iR, iL, and num!
        while( temp is not full ) {
           if( left side is all used up ) {
             copy rest of right side in.
             make sure that at the end of this temp is full so the
               while loop quits.
           }
           else if ( right side is all used up) {
             copy rest of left side in.
             make sure that at the end of this temp is full so the
               while loop quits.
           }
           else if (array[iL] < array[iR]) { ... }
           else if (array[iL] >= array[iR]) { ... }
        }
 }

Answer 2

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 7, 2, 3, 1, 6, 2};

        print(arr);
        new MergeSort().sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int lo, int hi) {
        if (lo < hi) {
            int mid = (lo + hi) / 2;
            sort(arr, lo, mid);           // recursive call to divide the sub-list
            sort(arr, mid + 1, hi);       // recursive call to divide the sub-list
            merge(arr, lo, mid, hi);      // merge the sorted sub-lists.
            print(arr);
        }
    }

    private void merge(int[] arr, int lo, int mid, int hi) {
        // allocate enough space so that the extra 'sentinel' value
        // can be added. Each of the 'left' and 'right' sub-lists are pre-sorted.
        // This function only merges them into a sorted list.
        int[] left = new int[(mid - lo) + 2];        
        int[] right = new int[hi - mid + 1];         


        // create the left and right sub-list for merging into original list.
        System.arraycopy(arr, lo, left, 0, left.length - 1);
        System.arraycopy(arr, mid + 1, right, 0, left.length - 1);

        // giving a sentinal value to marking the end of the sub-list.
        // Note: The list to be sorted is assumed to contain numbers less than 100.
        left[left.length - 1] = 100;
        right[right.length - 1] = 100;

        int i = 0;
        int j = 0;

        // loop to merge the sorted sequence from the 2 sub-lists(left and right) 
        // into the main list.
        for (; lo <= hi; lo++) {
            if (left[i] <= right[j]) {
                arr[lo] = left[i];
                i++;
            } else {
                arr[lo] = right[j];
                j++;
            }
        }
    }

    // print the array to console.
    private static void print(int[] arr) {
        System.out.println();
        for (int i : arr) {
            System.out.print(i + ", ");
        }
    }
}

Answer 3

Ecco un altro!

private static int[] mergeSort(int[] input){
    if (input.length == 1)
        return input;

    int length = input.length/2;
    int[] left = new int[length];
    int[] right = new int[input.length - length];

    for (int i = 0; i < length; i++)
        left[i] = input[i];
    for (int i = length; i < input.length; i++)
        right[i-length] = input[i];

    return merge(mergeSort(left),mergeSort(right));
}

private static int[] merge(int[] left, int[] right){
    int[] merged = new int[left.length+right.length];
    int lengthLeft = left.length;
    int lengthRight = right.length;
    while (lengthLeft > 0 && lengthRight > 0){
        if (left[left.length - lengthLeft] < right[right.length - lengthRight]){
            merged[merged.length -lengthLeft-lengthRight] = left[left.length - lengthLeft];
            lengthLeft--;
        }else{
            merged[merged.length - lengthLeft-lengthRight] = right[right.length - lengthRight];
            lengthRight--;
        }
    }
    while (lengthLeft > 0){
        merged[merged.length - lengthLeft] = left[left.length-lengthLeft];
        lengthLeft--;
    }
    while (lengthRight > 0){
        merged[merged.length - lengthRight] = right[right.length-lengthRight];
        lengthRight--;
    }
    return merged;
}

Answer 4

static void mergeSort(int arr[],int p, int r) {

   if(p<r) {
        System.out.println("Pass "+k++);

        int q = (p+r)/2;
        mergeSort(arr,p,q);
        mergeSort(arr,q+1,r);
        //System.out.println(p+" "+q+" "+r);
        merge(arr,p,q,r);
    }

}

static void merge(int arr[],int p,int q,int r) {
    int temp1[],temp2[];

    //lower limit array
    temp1 = new int[q-p+1];

    //upper limit array
    temp2 = new int[r-q];

    for(int i=0 ; i< (q-p+1); i++){
        temp1[i] = arr[p+i];
    }

    for(int j=0; j< (r-q); j++){
        temp2[j] = arr[q+j+1];
    }

    int i = 0,j=0;

    for(int k=p;k<=r;k++){

        // This logic eliminates the so called sentinel card logic mentioned in Coreman
        if(i!= temp1.length
                && (j==temp2.length || temp1[i] < temp2[j])
               ) {
            arr[k] = temp1[i];
           // System.out.println(temp1[i]);
            i++;
        }
        else {
            //System.out.println(temp2[j]);
            arr[k] = temp2[j];

            j++;
        }
    }
}

Answer 5

>

Merge Sort Utilizzando Sentinel

Questo codice funziona perfettamente bene.

 public void mergeSort(int a[], int low, int high) {

   if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);

    }
}



public void merge(int a[], int low, int mid, int high) {
    int n1 = mid - low + 1;// length of an array a1
    int n2 = high - mid; // length of an array a2
    int a1[] = new int[n1 + 1];
    int a2[] = new int[n2 + 1];
    int lowRange = low;
    for (int i = 0; i < n1; i++) {
        a1[i] = a[lowRange];
        lowRange++;
    }
    for (int j = 0; j < n2; j++) {
        a2[j] = a[mid + j + 1];
    }
    a1[n1] = Integer.MAX_VALUE; // inserting sentinel at the end of array a1 
    a2[n2] = Integer.MAX_VALUE; // inserting sentinel at the end of array a2
    int i = 0;
    int j = 0;
    int k = low;
    for (k = low; k <= high; k++) {

            if (a1[i] >= a2[j]) {
                a[k] = a2[j];
                j++;
            } else {
                a[k] = a1[i];
                i++;
            }

    }
    if (a2.length >= a1.length) {
        for (int ab = k; ab < a2.length; ab++) {
            a[k] = a2[ab];
            k++;
        }
    } else if (a1.length >= a2.length) {
        for (int ab = k; ab < a1.length; ab++) {
            a[k] = a1[ab];
            k++;
        }
    }

}

Answer 6

Ecco un'altra alternativa:

public class MergeSort {
public static void merge(int[]a,int[] aux, int f, int m, int l) {

    for (int k = f; k <= l; k++) {
        aux[k] = a[k];
    }

    int i = f, j = m+1;
    for (int k = f; k <= l; k++) {
        if(i>m) a[k]=aux[j++];
        else if (j>l) a[k]=aux[i++];
        else if(aux[j] > aux[i]) a[k]=aux[j++];
        else a[k]=aux[i++];
    }       
}
public static void sort(int[]a,int[] aux, int f, int l) {
    if (l<=f) return;
    int m = f + (l-f)/2;
    sort(a, aux, f, m);
    sort(a, aux, m+1, l);
    merge(a, aux, f, m, l);
}
public static int[] sort(int[]a) {
    int[] aux = new int[a.length];
    sort(a, aux, 0, a.length-1);
    return a;
}

}

Answer 7

Ecco un semplice algoritmo di ordinamento unione in Java:

buon consiglio: utilizzare sempre int middle = low + (high-low)/2 invece di int middle = (low + high)/2.

public static int[] mergesort(int[] arr) {
    int lowindex = 0;
    int highindex = arr.length-1;
    mergesort(arr, lowindex, highindex);
    return arr;
}

private static void mergesort(int[] arr, int low, int high) {
    if (low == high) {
        return;
    } else {
        int midIndex = low + (high-low)/2;
        mergesort(arr, low, midIndex);
        mergesort(arr, midIndex + 1, high);
        merge(arr, low, midIndex, high);
    }
}
private static void merge(int[] arr, int low, int mid, int high) {
    int[] left = new int[mid-low+2];
    for (int i = low; i <= mid; i++) {
        left[i-low] = arr[i];
    }
    left[mid-low+1] = Integer.MAX_VALUE;
    int[] right = new int[high-mid+1];
    for (int i = mid+1; i <= high; i++) {
        right[i-mid-1] = arr[i];
    }
    right[high - mid] = Integer.MAX_VALUE;
    int i = 0;
    int j = 0;
    for (int k = low; k <= high; k++) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
    }
}

Answer 8

package com;

public class Test {
    int count = 0;

    public static void main(String[] args) {
        int a[] = {1,3,5,7,9,10,14,15,16};
        int b[] = {2,4,6,8,11,12,13,17,18};

        int sizec = a.length+b.length;

        int c[] = new int[sizec];

        int i=0;int j=0;int k=0;

        while(k<sizec)
        {
             if(i == a.length || j == b.length)
                {
                 int sizeDifference = 0;
                 if(i==a.length)
                 {
                     sizeDifference = b.length-j;
                     for (int m =0;m<sizeDifference;m++)
                        {
                            c[k] = b[m+j];
                            if(k<sizec)
                            k++;
                        }
                        break;
                 }

                 else if(j== b.length)
                 {
                     sizeDifference = a.length-i;
                     for (int m =0;m<sizeDifference;m++)
                        {
                            c[k] = a[m+i];
                            if(k<sizec)
                            k++;
                        }
                        break;
                 }
                 else
                 {
                     c[k] = b[j];
                        j++;
                 }

                }

            if(i < a.length || j < b.length )
            {
            if(a[i]>b[j] )
                    {
                        c[k]=b[j];
                        j++;
                    }
            else if(a[i]<b[j])
            {
                c[k]=a[i];
                i++;
            }
            }



            k++;
        }

        for(int l=0;l<sizec;l++)
        {
            System.out.println(c[l]);
        }


    }
}