Soy nuevo en Java y han tratado de implementar mergesort en Java. Sin embargo, incluso después de ejecutar el programa varias veces, en lugar de la deseada ordenados de salida, estoy recibiendo el mismo usuario dado de entrada como el de salida. Yo estaría muy agradecido si alguien me pudiera ayudar a entender este comportamiento inesperado.

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;
}
}
tiene usted un paso a través de el uso de un depurador?
Tengo miedo, no sé cómo el uso de una (de java). Me puede sugerir ?
Si usted está usando Eclipse, utilizar el construido en uno. vogella.com/articles/EclipseDebugging/article.html
Usted puede comparar su código en contra de esta rosetta código de combinación de tipo ejemplo: rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Java

OriginalEl autor tinker | 2012-12-05

12 Comentarios

  1. 25

    Aquí es una versión corregida de su código:

    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;
    }
    }
    No debería una función recursiva tiene una base de caso?
    Esta aplicación hace un montón de innecesario de asignación. Sólo necesitas dos matrices, una para la entrada, y uno para contener la salida de la señal. Como un ejemplo de una aplicación, echa un vistazo a Mergesort en Java por Lars Vogel 🙂
    Esto está mal, si ejecuta este con 9,7,3 devuelve 7,7,3.Debe ser int[] leftArray = Arrays.copyOfRange(A, 0, q); int[] rightArray = Arrays.copyOfRange(A,q+1,A.length-1);
    no trabajo .. debe ser Matrices.copyOfRange(A, 0, q) & Matrices.copyOfRange(a, q, A. longitud).

    OriginalEl autor uyetch

  2. 9

    Al volver a enlazar A en mergeSort():

            A = merge(leftArray,rightArray);

    esto no tiene ningún efecto en inputArray en main().

    Necesita devolver el conjunto ordenado de mergeSort() de manera similar a cómo el retorno de merge().

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

    y en main():

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

    OriginalEl autor NPE

  3. 2

    El problema es que java es el paso por valor y no pasar por la referencia… Cuando se asigna a Una matriz en la combinación del método que se está cambiando una copia de la referencia a Una y no la referencia a sí mismo. Por lo tanto, usted necesita para pasar Una en su combinación de método y hacer un cambio estructural a la A.

    OriginalEl autor rascal

  4. 1

    El problema radica aquí:

    A = merge(leftArray,rightArray);

    Ahora la combinación de la matriz hace esto:

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

    Cuando comenzó, era una referencia a inputArray. Pero entonces se le haya asignado para ser lo que salió de combinar. Por desgracia, eso no tocar lo que inputArray es en el método main. Que básicamente dice «Oh mira todo el trabajo que hizo… el tiro a la basura!»

    Usted podría cambiar con algo como

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

    A continuación, en el principal método, usted puede hacer

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

    OriginalEl autor corsiKa

  5. 1
    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] + " ");
    }   
    }
    }
    No estoy seguro de que, en la implementación de mi ejemplo anterior la matriz funciona bien.

    OriginalEl autor Judeyou

  6. 0

    Asumiendo que su merge función es correcta:

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

    Ya que tenemos que volver a la matriz, volvemos A no modificados si tiene un solo elemento, de lo contrario combinar los resultados de la clasificación de las partes izquierda y derecha de la matriz.

    OriginalEl autor crashmstr

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

    OriginalEl autor Rick

  8. 0
    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();
    }
    }

    OriginalEl autor Sumit Kumar Saha

  9. 0

    Los códigos anteriores son un poco confundido
    Nunca usar variables con los nombres de: «k», «j», «m»,… esto hace que el código sea muy confuso

    Sigue el código de una manera más fácil…

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

    OriginalEl autor rafambbr

  10. 0

    Podría también agregar mi opinión sobre esto:
    Toma dos matrices de int y las fusiona.
    Donde ‘resultado’ es una matriz de tamaño un.longitud + b.longitud

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

    OriginalEl autor Liam Larsen

  11. 0
    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++;
    }
    }
    }

    OriginalEl autor Ragulan28

  12. 0

    muy simple y fácil de entender

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

    OriginalEl autor Himanshu Singh

Dejar respuesta

Please enter your comment!
Please enter your name here