Mergesort in Java

Question

Ich bin neu in Java und habe versucht, Mergesort in Java zu implementieren. Aber auch nach mehrmaligem Ausführen des Programms anstelle der gewünschten sortierten Ausgabe erhalte ich die gleiche vom Benutzer eingegebene Eingabe wie die Ausgabe. Ich wäre dankbar, wenn mir jemand helfen könnte, dieses unerwartete Verhalten zu verstehen.

import java.io.*; 
import java.util.Arrays; 


public class MergeSort { 

    public static void main(String[] args) throws IOException{ 
     BufferedReader R = new BufferedReader(new InputStreamReader(System.in)); 
     int arraySize = Integer.parseInt(R.readLine()); 
     int[] inputArray = new int[arraySize]; 
     for (int i = 0; i < arraySize; i++) { 
      inputArray[i] = Integer.parseInt(R.readLine()); 
     } 
     mergeSort(inputArray); 

     for (int j = 0; j < inputArray.length; j++) { 
      System.out.println(inputArray[j]); 
     } 

    } 

    static void mergeSort(int[] A) { 
     if (A.length > 1) { 
      int q = A.length/2; 
      int[] leftArray = Arrays.copyOfRange(A, 0, q); 
      int[] rightArray = Arrays.copyOfRange(A,q+1,A.length); 
      mergeSort(leftArray); 
      mergeSort(rightArray); 
      A = merge(leftArray,rightArray); 
     } 
    } 

    static int[] merge(int[] l, int[] r) { 
     int totElem = l.length + r.length; 
     int[] a = new int[totElem]; 
     int i,li,ri; 
     i = li = ri = 0; 
     while (i < totElem) { 
      if ((li < l.length) && (ri<r.length)) { 
       if (l[li] < r[ri]) { 
        a[i] = l[li]; 
        i++; 
        li++; 
       } 
       else { 
        a[i] = r[ri]; 
        i++; 
        ri++; 
       } 
      } 
      else { 
       if (li >= l.length) { 
        while (ri < r.length) { 
         a[i] = r[ri]; 
         i++; 
         ri++; 
        } 
       } 
       if (ri >= r.length) { 
        while (li < l.length) { 
         a[i] = l[li]; 
         li++; 
         i++; 
        } 
       } 
      } 
     } 
     return a; 

    } 

} 

Answer 1

ist eine korrigierte Version des Codes:

import java.io.*; 
import java.util.Arrays; 


public class MergeSort { 

    public static void main(String[] args) throws IOException{ 
     BufferedReader R = new BufferedReader(new InputStreamReader(System.in)); 
     int arraySize = Integer.parseInt(R.readLine()); 
     int[] inputArray = new int[arraySize]; 
     for (int i = 0; i < arraySize; i++) { 
      inputArray[i] = Integer.parseInt(R.readLine()); 
     } 
     mergeSort(inputArray); 

     for (int j = 0; j < inputArray.length; j++) { 
      System.out.println(inputArray[j]); 
     } 

    } 

    static void mergeSort(int[] A) { 
     if (A.length > 1) { 
      int q = A.length/2; 

//changed range of leftArray from 0-to-q to 0-to-(q-1) 
      int[] leftArray = Arrays.copyOfRange(A, 0, q-1); 
//changed range of rightArray from q-to-A.length to q-to-(A.length-1) 
      int[] rightArray = Arrays.copyOfRange(A,q,A.length-1); 

      mergeSort(leftArray); 
      mergeSort(rightArray); 

      merge(A,leftArray,rightArray); 
     } 
    } 

    static void merge(int[] a, int[] l, int[] r) { 
     int totElem = l.length + r.length; 
     //int[] a = new int[totElem]; 
     int i,li,ri; 
     i = li = ri = 0; 
     while (i < totElem) { 
      if ((li < l.length) && (ri<r.length)) { 
       if (l[li] < r[ri]) { 
        a[i] = l[li]; 
        i++; 
        li++; 
       } 
       else { 
        a[i] = r[ri]; 
        i++; 
        ri++; 
       } 
      } 
      else { 
       if (li >= l.length) { 
        while (ri < r.length) { 
         a[i] = r[ri]; 
         i++; 
         ri++; 
        } 
       } 
       if (ri >= r.length) { 
        while (li < l.length) { 
         a[i] = l[li]; 
         li++; 
         i++; 
        } 
       } 
      } 
     } 
     //return a; 

    } 

} 

Answer 2

Wenn Sie rebind A in mergeSort():

 A = merge(leftArray,rightArray); 

dies keine Wirkung in inputArray in main() hat.

Sie müssen das sortierte Array von mergeSort() ähnlich wie Sie es von merge() zurückgeben.

static int[] mergeSort(int[] A) { 
    ... 
    return A; 
} 

und in main():

int[] mergedArray = mergeSort(inputArray); 

    for (int j = 0; j < mergedArray.length; j++) { 
     System.out.println(mergedArray[j]); 
    } 

Answer 3

Das Problem hier liegt:

A = merge(leftArray,rightArray); 

nun Ihre merge Array tut dies:

static int[] merge(int[] l, int[] r) { 
    int[] a = new int[totElem]; 
    // bunch of code 
    return a; 
} 

Wenn Sie begonnen, A wurde ein Verweis auf inputArray . Aber dann hast du es neu zugewiesen, um zu sein, was auch immer aus der Zusammenführung kam. Leider berührt das nicht, was InputArray in der Hauptmethode ist. Das sagt im Grunde "Oh, schau dir all deine Arbeit an ... wirf es weg!"

Sie könnten, dass mit etwas ändern wie

static int[] mergeSort(int[] A) { 
    // A = merge... // not this 
    return merge... // use this 
} 

dann in der Haupt Methode können Sie tun

int[] merged = mergeSort(inputArray); 
for(int i : merged) System.out.println(i); 

Answer 4

Angenommen, Ihre merge Funktion ist korrekt:

static int[] mergeSort(int[] A) { 
    if (A.length > 1) { 
     int q = A.length/2; 
     int[] leftArray = Arrays.copyOfRange(A, 0, q); 
     int[] rightArray = Arrays.copyOfRange(A,q+1,A.length); 
     return merge(mergeSort(leftArray),mergeSort(rightArray)); 
    } 
    else 
     return A; 
} 

Da wir müssen das Array zurückgeben, wir geben A unmodified zurück, wenn es hat nur ein Element, sonst verbinden wir die Ergebnisse der Sortierung der linken und rechten Teile des Arrays. Hier

Answer 5

Das Problem ist, dass Java-Pass von Wert und nicht als Verweis übergibt ... Wenn Sie Array A in dem Merge-Verfahren zuweisen Sie sind Ändern einer Kopie der Referenz auf A und nicht die Referenz auf A selbst. Daher müssen Sie ein in Ihre merge Methode zu übergeben und eine strukturelle Veränderung

Answer 6

public void sort(int[] randomNumbersArrray) 
{ 
    copy = randomNumbersArrray.clone(); 
    mergeSort(0 , copy.length - 1); 
} 

private void mergeSort(int low, int high) 
{ 
    if(low < high) 
    { 
     int mid = ((low + high)/2); 
     mergeSort(low, mid); //left side 
     mergeSort(mid + 1, high); // right side 
     merge(low, mid, high); //combine them 
    } 

} 


private void merge(int low, int mid, int high) 
{ 
    int temp[] = new int[high - low + 1]; 
    int left = low; 
    int right = mid + 1; 
    int index = 0; 

    // compare each item for equality 
    while(left <= mid && right <= high) 
    { 
     if(copy[left] < copy[right]) 
     { 
      temp[index] = copy[left]; 
      left++; 
     }else 
     { 
      temp[index] = copy[right]; 
      right++; 
     } 
     index++; 
    } 

    // if there is any remaining loop through them 
    while(left <= mid || right <= high) 
    { 
     if(left <= mid) 
     { 
      temp[index] = copy[left]; 
      left++; 
      index++; 
     }else if(right <= high) 
     { 
       temp[index] = copy[right]; 
       right++; 
       index++; 
     } 
    } 
    // copy back to array 
    for(int i = 0; i < temp.length; i++) 
    { 
     copy[low + i] = temp[i]; 
    } 
} 

Answer 7

package Sorting; 

public class MergeSort { 

private int[] original; 
private int len; 
public MergeSort(int length){ 

    len = length; 
    original = new int[len]; 

    original[0]=10; 
    original[1]=9; 
    original[2]=8; 
    original[3]=7; 
    original[4]=6; 
    original[5]=5; 
    original[6]=4; 
    original[7]=3; 
    original[8]=2; 
    original[9]=1; 

    int[] aux = new int[len]; 
    for(int i=0;i<len;++i){ 
     aux[i]=original[i]; 
    } 

    Sort(aux,0,len); 


} 

public void Sort(int[] aux,int start, int end){ 

    int mid = start + (end-start)/2; 

    if(start < end){ 
     Sort(aux, start, mid-1); 
     Sort(aux, mid, end); 
     Merge(aux, start, mid, end); 
    } 
} 

public void Merge(int[] aux, int start, int mid, int end){// while array passing be careful of shallow and deep copying 

    for(int i=start; i<=end; ++i) 
     auxilary[i] = original[i]; 

    int i = start; 
    int k = start; 
    int j = mid+1; 
    while(i < mid && j <end){ 
     if(aux[i] < aux[j]){ 
      original[k++] = aux[i++]; 
     } 
     else{ 
      original[k++] = aux[j++]; 
     } 
    } 
    if(i == mid){ 
     while(j < end){ 
      original[k++] = aux[j++]; 
     } 
    } 
    if(j == end){ 
     while(i < mid){ 
      original[k++] = aux[i++]; 
     } 
    } 
} 
public void disp(){ 
    for(int i=0;i<len;++i) 
     System.out.print(original[i]+" "); 
} 
public static void main(String[] args) { 

    MergeSort ms = new MergeSort(10); 

    ms.disp(); 

} 

} 

Answer 8

public class MergeSort{ 
public static void sort(int[] in){ 
    if(in.length <2) return; //do not need to sort 
    int mid = in.length/2; 
    int left[] = new int[mid]; 
    int right[] = new int[in.length-mid]; 
    for(int i=0; i<mid; i++){ //copy left 
     left[i] = in[i]; 
    } 
    for(int i=0; i<in.length-mid; i++){ //copy right 
     right[i] = in[mid+i]; 
    } 
    sort(left); 
    sort(right); 
    merge(left, right, in); 
} 

private static void merge(int[] a, int[] b, int[] all){ 
    int i=0, j=0, k=0; 
    while(i<a.length && j<b.length){ //merge back 
     if(a[i] < b[j]){ 
      all[k] = a[i]; 
      i++; 
     }else{ 
      all[k] = b[j]; 
      j++; 
     } 
     k++; 
    } 
    while(i<a.length){ //left remaining 
     all[k++] = a[i++]; 
    } 
    while(j<b.length){ //right remaining 
     all[k++] = b[j++]; 
    } 
} 

public static void main(String[] args){ 
    int[] a = {2,3,6,4,9,22,12,1}; 
    sort(a);  
    for(int j=0; j<a.length; j++){ 
     System.out.print(a[j] + " "); 
    } 
} 
} 

Answer 9

Die obigen Codes sind ein wenig verwirrt nie Variablen A. machen verwenden mit dem Namen: „k“, " j "," m ", ... das macht den Code sehr verwirrend

Folgt dem Code auf einfachere Weise ...

import java.util.Arrays; 

public class MergeSort { 

    public static void main(String[] args) { 
     Integer[] itens = {2,6,4,9,1,3,8,7,0}; 

     Integer[] tmp = new Integer[itens.length]; 
     int left = 0; 
     int right = itens.length - 1; 

     mergeSort(itens, tmp, left, right); 

     System.out.println(Arrays.toString(itens)); 
    } 

    private static void mergeSort(Integer[] itens, Integer[] tmpArray, int left, int right) { 

     if(itens == null || itens.length == 0 || left >= right){ 
      return; 
     } 

     int midle = (left + right)/2; 

     mergeSort(itens, tmpArray, left, midle); 
     mergeSort(itens, tmpArray, midle + 1, right); 

     merge(itens, tmpArray, left, midle + 1, right); 
    } 

    private static void merge(Integer[] itens, Integer[] tmpArray, int left, int right, int rightEnd) { 
     int leftEnd = right - 1; 
     int tmpIndex = left; 

     while (left <= leftEnd && right <= rightEnd){ 
      if (itens[left] < itens[right]){ 
       tmpArray[tmpIndex++] = itens[left++]; 
      } else { 
       tmpArray[tmpIndex++] = itens[right++]; 
      } 
     } 

     while (left <= leftEnd) { // Copy rest of LEFT half 
      tmpArray[tmpIndex++] = itens[left++]; 
     } 
     while (right <= rightEnd) { // Copy rest of RIGHT half 
      tmpArray[tmpIndex++] = itens[right++]; 
     } 
     while(rightEnd >= 0){ // Copy TEMP back 
      itens[rightEnd] = tmpArray[rightEnd--]; 
     } 
    } 
} 

Answer 10

Es könnte aber auch meine Meinung dazu addieren: nimmt zwei int-Arrays und fügt sie zusammen. Wo ‚Ergebnis‘ eine Reihe von Größe a.length ist + b.length

public static void merge(int[] a, int[] b, int[] result) 
{ 
    int i = 0, j = 0; 

    while (true) 
    { 
    if (i == a.length) 
    { 
     if (j == b.length) 
     return; 

     result[ i + j ] = b[ j ]; 
     j++; 
    } 
    else if (j == b.length) 
    { 
     result[ i + j ] = a[ i ]; 
     i++; 
    } 
    else if (a[ i ] < b[ j ]) 
    { 
     result[ i + j ] = a[ i ]; 
     i++; 
    } 
    else 
    { 
     result[ i + j ] = b[ j ]; 
     j++; 
    } 
    } 
}