wake-up-neo.net

Mergesort in Java

Ich bin neu in Java und habe versucht, Mergesort in Java zu implementieren. Selbst nachdem das Programm mehrmals ausgeführt wurde, bekomme ich anstelle der gewünschten sortierten Ausgabe denselben Benutzer, dessen Eingabe als Ausgabe angegeben wurde. 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;

    }

}
10
tinker

Hier ist eine korrigierte Version Ihres 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;

    }

}
25
uyetch

Wenn Sie A in mergeSort() erneut binden:

        A = merge(leftArray,rightArray);

dies hat keine Auswirkung auf inputArray in main().

Sie müssen das sortierte Array von mergeSort() zurückgeben, ä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]);
    }
9
NPE

Das Problem ist, dass Java als Wert übergeben wird und nicht als Referenz. Wenn Sie Array A in der Merge-Methode zuweisen, ändern Sie eine Kopie der Referenz auf A und nicht die Referenz auf A selbst. Daher müssen Sie A in Ihre Merge-Methode einbinden und eine strukturelle Änderung an A vornehmen.

2
rascal
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] + " ");
    }   
 }
}
1
Judeyou

Das Problem liegt hier:

A = merge(leftArray,rightArray);

Jetzt führt Ihr Merge-Array Folgendes aus:

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

Als Sie angefangen haben, war A ein Verweis auf inputArray. Aber dann haben Sie es wieder zu dem gemacht, was aus der Verschmelzung kam. Leider berührt das nicht, was inputArray in der Hauptmethode ist. Das sagt im Grunde "Oh, schau dir all die Arbeit an, die du gemacht hast ... wirf sie weg!"

Sie könnten das mit etwas ändern

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

Dann können Sie in Ihrer Hauptmethode tun

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

sehr einfach und leicht verständlich 

static void sort(char[] data) {
    int length = data.length;
    if (length < 2)
        return;
    int mid = length / 2;
    char[] left = new char[mid];
    char[] right = new char[length - mid];

    for(int i=0;i<mid;i++) {
        left[i]=data[i];
    }

    for(int i=0,j=mid;j<length;i++,j++) {
        right[i]=data[j];
    }

    sort(left);
    sort(right);
    merge(left, right, data);

}

static void merge(char[] left, char[] right, char[] og) {
    int i = 0, j = 0, k = 0;
    while(i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            og[k++] = left[i++];
        } else {
            og[k++] = right[j++];
        }
    }
    while (i < left.length) {
        og[k++] = left[i++];
    }
    while (j < right.length) {
        og[k++] = right[j++];
    }

}
0
Himanshu Singh

Könnte auch meine Meinung dazu hinzufügen: Nimmt zwei int-Arrays und führt sie zusammen

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++;
    }
  }
}
0
Liam Larsen

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 das Array zurückgeben müssen, geben wir A unmodified zurück, wenn es nur ein Element enthält. Andernfalls werden die Ergebnisse der Sortierung des linken und des rechten Teils des Arrays zusammengeführt.

0
crashmstr
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();

}

}
0

Die obigen Codes sind etwas verwirrt. __ Verwenden Sie niemals Variablen mit 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--];
        }
    }
}
0
rafambbr
public class MyMergeSort {

    private int[] array;
    private int[] tempMergArr;
    private int length;

    public static void main(String a[]){

        int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
        MyMergeSort mms = new MyMergeSort();
        mms.sort(inputArr);
        for(int i:inputArr){
            System.out.print(i);
            System.out.print(" ");
        }
    }

    public void sort(int inputArr[]) {
        this.array = inputArr;
        this.length = inputArr.length;
        this.tempMergArr = new int[length];
        doMergeSort(0, length - 1);
    }

    private void doMergeSort(int lowerIndex, int higherIndex) {

        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
            doMergeSort(lowerIndex, middle);
            // Below step sorts the right side of the array
            doMergeSort(middle + 1, higherIndex);
            // Now merge both sides
            mergeParts(lowerIndex, middle, higherIndex);
        }
    }

    private void mergeParts(int lowerIndex, int middle, int higherIndex) {

        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }

    }
}
0
Ragulan28
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];
    }
}
0
Rick