вывод сортировки слиянием не полностью отсортирован - PullRequest
Новая
       12

вывод сортировки слиянием не полностью отсортирован

1 голос
/ 22 июня 2011

Я пытаюсь реализовать алгоритм сортировки слиянием из книги «Введение в алгоритм», используя Java, но когда я выполняю код, у меня выводится полусортировка: 

input  = 2,4,5,1,2,3,6,7
output = 2,2,3,4,5,1,2,7 



public class Main {

    public static void main(String[] args) {
        int A[] = {
            2, 4, 5, 1, 2, 3, 6, 7
        };

        int B[] = new Main().mergeSort(A, 0, A.length);
        for (int i = 0; i < B.length; i++) {
            System.out.println(B[i]);
        }
    }

    void merge(int A[], int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        System.out.println("-n1: " + n1 + " n2: " + n2);
        int L[] = new int[n1];
        int R[] = new int[n2];


        for (int i = 0; i < n1; i++) {

            L[i] = A[p + i];
            System.out.println("L--|" + L[i]);
        }
        for (int j = 0; j < n2; j++) {
            R[j] = A[q + j];
            System.out.println("R--|" + R[j]);
        }

        int i = 0;
        int j = 0;

        for (int k = p; k < r; k++) {
            if (L[i] <= R[j]) {

                A[k] = L[i];
                System.out.println("A--|" + A[k] + " i: " + i);
                i = i + 1;
            } else {

                A[k] = R[j];
                System.out.println("A--|" + A[k] + " j: " + j);
                j = j + 1;
            }

            if (i == L.length || j == R.length) break;
        }
    }

    int[] mergeSort(int A[], int p, int r) {
        if (p < r) {
            int q = (int) Math.floor((p + r) / 2);
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            System.out.println("q: " + q + " p: " + p + " r:" + r);
            merge(A, p, q, r);
        }
        return A;
    }
}

Если кто-то может помочь мне в этом коде, я был бы благодарен. Я знаю, что в Java есть много готовых реализаций, и в этой форме я просто хочу знать, что не так с моим кодом.

Ответы [ 2 ]

1 голос
/ 23 июня 2011

Спасибо за ваши предложения, мне удалось заставить его работать, как показано ниже. 

void merge(int A[], int low, int mid, int high) {
    int leftN = mid - low + 1;
    int rightN = high - mid;
    System.out.println("n1: " + leftN + " n2: " + rightN + " q: " + mid + " p: " + low + " r:" + high);
    int L[] = new int[leftN + 1];
    int R[] = new int[rightN + 1];

    L[leftN] = Integer.MAX_VALUE;
    R[rightN] = Integer.MAX_VALUE;

    for (int i = 0; i < leftN; i++) {

        L[i] = A[low + i - 1];
        System.out.println("L--|" + L[i]);
    }
    for (int j = 0; j < rightN; j++) {
        R[j] = A[mid + j];
        System.out.println("R--|" + R[j]);
    }

    int i = 0;
    int j = 0;

    for (int k = low - 1; k < high; k++) {

        if (L[i] <= R[j]) {

            A[k] = L[i];
            System.out.println("A--|" + A[k] + " i: " + i + " R[i] " + L[i]);
            i++;
        } else {

            A[k] = R[j];
            System.out.println("A--|" + A[k] + " j: " + j + " R[j] " + R[j]);
            j++;
        }
    }

}

int[] mergeSort(int A[], int low, int high) {
    if (low < high) {

        int mid = (low + high) / 2;
        System.out.println("q: " + mid + " p: " + low + " r:" + high);
        mergeSort(A, low, mid);
        mergeSort(A, mid + 1, high);
        merge(A, low, mid, high);

    }

    return A;
}
1 голос
/ 22 июня 2011

Не используйте printf () для отладки.Это может помочь вам увидеть, что происходит, но установите точки останова и используйте отладчик.Это прояснит для вас, но вот несколько советов, которые вы можете сделать немедленно:

  1. Не называйте свои переменные p, q, r и т. Д. Переименуйте их в «высокий», "низкий", "средний".Переименуйте n1 в leftLen и т. Д. Это значительно улучшает удобочитаемость для других программистов и помогает вам понять, что происходит.

  2. Подумайте о том, что делают ваши программы.Ваш "mergeSort ()" является полностью стандартным, поэтому проблема должна лежать в вашей программе слияния.Вместо запуска mergeSort, запустите merge отдельно и посмотрите, что происходит.Постарайтесь понять, как работает ваша программа слияния, и сравните ее с тем, что, по вашему мнению, она делает.

  3. В частности, рассмотрите ваши L [] и R [].Могут ли они когда-нибудь быть пустыми?Если так, что происходит?

  4. А как насчет дубликатов?Можете ли вы когда-нибудь хранить одно и то же число в левом и правом массиве?Влияет ли это на ваш код?

  5. Есть ли лучший способ сохранить диапазон чисел?

Удачи!

...