Java-реализация MergeSort;

Хорошо, это один из тех отчаянных вопросов. Я пытаюсь реализовать Bottom-Up MS для сортировки и целочисленного массива. Но ради бога, я не могу найти ошибку ...

import java.util.Scanner;

public class A2 {

    public static boolean less(Integer v, Integer w) {
        return v.compareTo(w) < 0;
    }

    public static void sort(int[] a) {
        int N = a.length;
        int[] aux = new int[N];
        for (int sz = 1; sz < N; sz = sz + sz)
            for (int lo = 0; lo < N - sz; lo += sz + sz)
                merge(a, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    }

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++) 
            if (i > mid)
                a[k] = aux[j++];
            else if (j > hi)
                a[k] = aux[i++];
            else if (less(aux[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = a[i++];

    }

    public static void main(String[] args) {
        int next = 0;
        Scanner scanner = new Scanner(System.in);
        int size = Integer.parseInt(scanner.nextLine());
        int[] v = new int[size];
        String s = scanner.nextLine();
        scanner.close();
        String[] sa = s.split("[\s]+");
        while (next < size) {
            v[next] = Integer.parseInt(sa[next]);
            next ++;
        }
        for (Integer i : v)
            System.out.print(i + " ");
        System.out.println();
        System.out.println("----------------------------------");
        sort(v);
        for (int i = 0; i < size; i++)
            System.out.print(v[i] + " ");
        System.out.println();
    }
}

В main функции я печатаю элементы массива, просто чтобы убедиться, что проблема в сортировке. Первое число - это просто размер массива. Ошибка находится либо в sort() либо в merge() . Вот несколько примеров выходных данных:

9
10 45 20 5 -6 80 99 -4 0
10 45 20 5 -6 80 99 -4 0 
----------------------------------
-6 -4 -4 -6 -4 -4 -6 0 99 

6
6 7 3 2 4 1
6 7 3 2 4 1 
----------------------------------
1 1 1 4 6 7 

5
6 5 2 3 4
6 5 2 3 4 
----------------------------------
2 3 4 5 6 

Этот последний, кажется, просто отлично.

Пожалуйста, помогите мне, я бродил и не могу найти ошибку.

Всего 3 ответа


Проблема заключается в методе merge() : в последних 2 случаях в цикле вы копируете значения вместо aux . Это не проблема, когда вы копируете a[j++] но когда вы копируете a[i++] значение может быть уже перезаписано.

Учитывая, что значения в правом срезе записываются только после того, как они уже скопированы, вам нужно только сохранить левый срез.

Вот модифицированная версия с этим упрощением:

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= mid; k++)  // save a[lo..mid] to aux
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                a[k] = a[j++];
            else if (j > hi)
                a[k] = aux[i++];
            else if (less(a[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = aux[i++];
        }
    }

Обратите внимание, что было бы менее подверженным ошибкам рассматривать mid как начало правого среза, а hi - индекс после конца среза. Цикл sort() был бы проще, без хитрых настроек +/- 1. Кстати, тест внутренней петли в вашей версии отключен одним, хотя и без последствий, кроме неэффективности. Должен быть:

for (int lo = 0; lo < N - sz - 1; lo += sz + sz)

Вот еще одна упрощенная реализация с включенными / исключенными слайсами и комбинированным тестом:

    public static void sort(int[] a) {
        int N = a.length;
        int[] aux = new int[N];
        for (int sz = 1; sz < N; sz = sz + sz)
            for (int lo = 0; lo < N - sz; lo += sz + sz)
                merge(a, aux, lo, lo + sz, Math.min(lo + sz + sz, N));
    }

    public static void merge(int[] a, int aux[], int lo, int mid, int hi) {
        for (int i = lo; i < mid; i++) { // save a[lo..mid[ to aux
            aux[i] = a[i];
        }
        for (int i = lo, j = mid, k = lo; i < mid; k++) {
            if (j < hi && less(a[j], aux[i]))
                a[k] = a[j++];
            else
                a[k] = aux[i++];
        }
    }

Эта версия очень проста, но все же не очень эффективна для больших массивов, потому что каждый проход проходит через весь массив, нарушая схему кэширования процессора. Было бы более эффективно постепенно выполнять слияние снизу вверх, используя стек отсортированных подмассивов увеличивающихся размеров.


С этим изменением это работает в моей системе.

            else if(less(aux[j], aux[i]))
                a[k] = aux[j++];             // fix  (aux)
            else
                a[k] = aux[i++];             // fix  (aux)

Если сортировка слиянием избегала шага копирования, изменяя направление слияния с каждым проходом, если в конце прохода слияния остался один прогон, его необходимо скопировать. 3-й раздел в этом ответе имеет пример этого.


Использование less (...) периодически удваивает время выполнения в моей системе, когда я тестировал с использованием больших массивов (например, 8 миллионов ints) со случайными значениями. Изменение if (less (aux [j], aux [i])) на if (aux [j] <aux [i]), кажется, исправило это или сделало это очень редким.


Пример кода для несколько более эффективной сортировки слиянием, которая позволяет избежать копирования, если не существует нечетного числа проходов. Этого можно избежать, сначала посчитав количество проходов, а если число проходов нечетное, поменяйте местами. Это можно распространить на более крупные подгруппы, используя сортировку вставкой по группам из 32 или 64 элементов на начальном проходе.

    public static void sort(int[] a) {
        int n = a.length;
        if(n < 2)
            return;
        int[] dst = new int[n];
        int[] src = a;
        int[] tmp;
        for(int sz = 1; sz < n; sz = sz+sz){
            int lo;
            int md;
            int hi = 0;
            while(hi < n){
                lo = hi;
                md = lo+sz;
                if(md >= n){            // if single run remaining, copy it
                    System.arraycopy(src, lo, dst, lo, n-lo);
                    break;
                }
                hi = md+sz;
                if(hi > n)
                    hi = n;
                merge(src, dst, lo, md, hi);
            }
            tmp = src;                  // swap references
            src = dst;                  //  to change direction of merge
            dst = tmp;
        }
        if(src != a)                    // copy back to a if needed
            System.arraycopy(src, 0, a, 0, n);
    }

    public static void merge(int[] src, int[] dst, int lo, int md, int hi) {
        int i = lo;
        int j = md;
        int k = lo;
        while(true){
            if(src[j]< src[i]){
                dst[k++] = src[j++];
                if(j < hi)
                    continue;
                System.arraycopy(src, i, dst, k, md-i);
                return;
            } else {
                dst[k++] = src[i++];
                if(i < md)
                    continue;
                System.arraycopy(src, j, dst, k, hi-j);
                return;
            }
        }
    }

Вы можете попробовать с этим кодом:

import java.util.Arrays;

public class MergeSort
{
   public static void merge(double[] a, 
                            int iLeft, int iMiddle, int iRight, 
                            double[] tmp)
   {
      int i, j, k;

      i = iLeft;
      j = iMiddle;
      k = iLeft;

      while ( i < iMiddle || j < iRight )
      {
         if ( i < iMiddle && j < iRight )
         {  // Both array have elements
            if ( a[i] < a[j] )
               tmp[k++] = a[i++];
            else
               tmp[k++] = a[j++];
         }
         else if ( i == iMiddle )
            tmp[k++] = a[j++];     // a is empty
         else if ( j == iRight )
            tmp[k++] = a[i++];     // b is empty
      }

      /* =================================
         Copy tmp[] back to a[]
         ================================= */
      for ( i = iLeft; i < iRight; i++ )
         a[i] = tmp[i];
   }

   public static void sort(double[] a, double[] tmp)
   {
      int width;

      for ( width = 1; width < a.length; width = 2*width )
      {
         // Combine sections of array a of width "width"
         int i;

         for ( i = 0; i < a.length; i = i + 2*width )
         {
            int left, middle, right;

        left = i;
        middle = i + width;
        right  = i + 2*width;

            merge( a, left, middle, right, tmp );

         }

         System.out.println("After 1 iter: " + Arrays.toString(a) );
      }
   }
}

Есть идеи?

10000