Код сортировки слиянием Java не работает - PullRequest
Новая
       14

Код сортировки слиянием Java не работает

0 голосов
/ 18 марта 2012

Наш учитель дал нам псевдокод для сортировки слиянием, как показано ниже:

enter image description here

Я хочу реализовать его на Java.Мой код ниже: 

public class MergeSorter {
/**
 * @param anArray
*/
    public MergeSorter(int[] anArray,int low, int high)
    {
        a = anArray;
        p = low;
        r = high;
    }
    public void sort()
    {
        if(p < r)
        {
           q = (p + r)/2;
           MergeSorter pqSorter = new MergeSorter(a, p, q);
           MergeSorter qrSorter = new MergeSorter(a, q + 1, r);
           pqSorter.sort();
           qrSorter.sort();
           merge(p, q, r);
        }
   }
private void merge(int low, int mid, int high)
{
   p = low;
   q = mid;
   r = high;
   int i;
   int j;
   int n1 = (q - p) + 1;
   int n2 = (r - q);
   int[] L = new int[n1+1];
   for (i = 0; i < n1; i++)
   {
       L[i] = a[(p + i)];
   }
   int[] R = new int[n2+1];
   for (j = 0; j < n2; j++)
       {
       R[j] = a[q + j];
       }
       L[n1] = Integer.MAX_VALUE;
       R[n2] = Integer.MAX_VALUE;
       i = 0;
       j = 0;
       for (int k = p; k < r; k++)
       {
           count = count + 1;
           if(L[i] <= R[j])
           {
               a[k] = L[i];
               i = i + 1;
           }
          else
           {
               a[k] = R[j];
               j = j + 1;
          }
       } 
    }
    private int[] a;
    private int p; 
    private int r;
    private int q;
    public int count = 0;
}

Но этот код не работает. Я хочу знать, в чем проблема.Извините за неправильное направление изображения.Обновлено: вот мой другой код. Сейчас что-то дозируется, но не отсортировано правильно.Это мой тестовый код ниже 

    public static void main(String[] args) throws FileNotFoundException, IOException
    {
      int[] a = {1,4,6,2,10,7};
      MergeSorter sorter = new MergeSorter(a,0,a.length);
      sorter.sort();
      System.out.println(Arrays.toString(a));
     }

В результате выдается [1,2,4,4,2,7].

Ответы [ 4 ]

1 голос
/ 18 марта 2012

У вас есть пара ошибок "по одному". 

MergeSorter sorter = new MergeSorter(a,0,a.length);

Последний индекс массива: a.length - 1. 

for (j = 0; j < n2; j++)
{
    R[j] = a[q + j];
}

Вторая половина, которая будет объединена, начинается с индекса q+1 до r. 

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

Последний заполняемый индекс - r, а не r-1, поэтому условие должно быть k <= r.

Далее, установка переменных экземпляра 

p = low;
q = mid;
r = high;

в merge() подозрительно. Здесь не больно, потому что они установлены на те значения, которые у них уже есть, но в принципе это неправильно.

1 голос
/ 18 марта 2012

Вам не хватает функции пола внутри функции сортировки при q = (p + r) / 2.Вы упомянули, что исправили это.Следующая проблема - ваш звонок на MergeSorter sorter = new MergeSorter(a,0,a.length); с основного.Я считаю, что это должно быть a.length - 1.Псевдокод, который у вас есть, работает с массивами, где первый элемент находится с индексом 1. Но в массивах java начинаются с индекса 0. После того, как вы сделаете это изменение, у вас возникнут 2 незначительные проблемы, которые необходимо откорректировать внутри функции слияния.Гудлак.

0 голосов
/ 18 марта 2012

Я написал сортировку слиянием в C некоторое время назад, и она отлично работает. Попробуйте сравнить, если что-то поражает.

Кроме того, проверьте свои индексы, так как псевдокод использует индексы массивов из 1..n, а когда вы пишете код, языки, такие как C, Java, используют 0 в качестве первого индекса. 

#include <stdio.h>


int A[] = {11, 32 ,2, 7, 1, 15 };

void
merge_sort(int A[], int startIndex, int endIndex)
{
    int q = 0;
    //Terminating condition
    if (!(startIndex < endIndex)) {
       return; 
    }

    q = (startIndex + endIndex) / 2;
    merge_sort(A, startIndex, q);
    merge_sort(A, q+1, endIndex);
    printf("\n merge with start[%d], q[%d], end[%d]", startIndex,q, endIndex);
    merge(A, startIndex, q, endIndex);
}

merge(int A[], int startIndex, int q, int endIndex)
{
   int i = 0; int j = 0; int k=0;  
   int C[endIndex - startIndex + 1];
   int A1[q - startIndex + 1];
   int A2[endIndex - q];
   int lenA1 =q - startIndex + 1;
   int lenA2 = endIndex - q; 
   int iterator = 0;
   int lenA = endIndex - startIndex + 1;

   for(iterator = 0; iterator < lenA1; iterator++) {
      A1[iterator] = A[iterator + startIndex]; 
      printf("\n Iterator1[%d]", iterator + startIndex);
   }

    dump(A1, lenA1);
   for(iterator = 0; iterator < lenA2; iterator++) {
      A2[iterator] = A[iterator + q + 1]; 
      printf("\n Iterator2[%d]", iterator + q + 1);
   }

    dump(A2, lenA2);

   for (iterator = startIndex; iterator < (endIndex - startIndex + 1) && ((i < lenA1) && (j<lenA2)); iterator++)
   {
       if (A1[i] <= A2[j]) {
           A[k] = A1[i]; 
           printf("\n\t--A[k]--");
           k+=1;
           i+=1; 
       } else {
           A[k] = A2[j];
           printf("\n\t****A[k]***");
           j+=1; 
           k+=1;      
       }
   }
   if (j < lenA2) {
      for (iterator = j; iterator < lenA2; iterator++)
      {
           A[k] = A2[j];
           j+=1; 
           k+=1;      
      }
   } else if (i < lenA1) {
           A[k] = A1[i]; 
           k+=1;
           i+=1; 
   }
    dump(A, lenA);
    fflush(stdout);

}

void dump(int A[], int len)
{
    int i;
    printf("\n --------");
    for(i=0; i<len; i++)
    {
        printf("[%d] ", A[i]);
    }
}

int main()
{
    merge_sort(A, 0, 6);
    dump(A, 7);
//    dump(C, 7);
}
0 голосов
/ 18 марта 2012

Ваш код не соответствует 100% псевдокоду. Подсказка: индексы

То, что Java является ОО, не означает, что вы должны использовать объект во всем. В этом случае вам лучше без него. 

public static void mergeSort(int[] array) {
    mergeSort(array, 0, array.length-1);
}

private static void mergeSort(int[] array, int p, int r) {
    ...
}

private static void merge(int[] array, int p, int q, int r) {
    ...
}
...