Mergesort w java

Question

Jestem nowicjuszem w Javie i próbowałem wdrożyć mergesort w Javie. Jednak nawet po kilkakrotnym uruchomieniu programu, zamiast żądanego posortowanego wyjścia, otrzymuję ten sam użytkownik, który otrzymał dane wejściowe jako dane wyjściowe. Byłbym wdzięczny, gdyby ktoś pomógł mi zrozumieć to nieoczekiwane zachowanie.

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

Oto poprawiona wersja kodu:

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

Kiedy ponownie powiązać A w mergeSort():

 A = merge(leftArray,rightArray); 

nie ma to wpływu na inputArray w main().

Musisz zwrócić posortowaną tablicę z mergeSort(), podobnie jak zwracasz ją od merge().

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

aw main():

int[] mergedArray = mergeSort(inputArray); 

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

Answer 3

Problem leży tutaj:

A = merge(leftArray,rightArray); 

Teraz macierzy seryjnej to robi:

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

Kiedy zaczął, A został odniesienie do inputArray . Ale potem ponownie przydzieliłeś to, by cokolwiek wyszło z połączenia. Niestety nie ma to wpływu na to, co inputArray jest w głównej metodzie. Zasadniczo mówi: "Spójrz na całą pracę, którą wykonałeś ... wyrzuć!"

Można zmienić coś jak

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

Następnie w głównym sposobem, można zrobić

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

Answer 4

Zakładając, że funkcja merge jest poprawna:

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; 
} 

Ponieważ trzeba zwrócić tablicę, zwracamy A niezmodyfikowaną, jeśli to ma tylko jeden element, w przeciwnym razie łączymy wyniki sortowania lewej i prawej części tablicy.

Answer 5

Problemem jest to, że Java jest podanie przez wartość i nie przechodzą przez odniesienie ... Po przypisaniu do tablicy A w sposobie łączenia jesteś zmiana kopii odniesienia do A, a nie odniesienie do samego A. Dlatego trzeba zdać się na swoje metody scalania i dokonać zmiany strukturalne A.

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

Powyższe kody są trochę mylić Nigdy nie używać zmiennych o nazwach: „k”, " j "," m ", ... powoduje to, że kod jest bardzo mylący:

Powoduje wykonanie kodu w łatwiejszy sposób ...

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

Równie dobrze można dodać moje zdanie na ten temat: przyjmuje dwie tablice int i scala je. Gdzie wynik "jest tablicą rozmiarze a.length + 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++; 
    } 
    } 
}