Java, сортировка слиянием

Я пытался кодировать сортировку слиянием, не создавая дополнительных массивов для хранения отсортированных частей, через несколько часов я не могу найти ошибку, которая приводит к тому, что последний бит массива сортируется в неправильном порядке. Есть довольно много вспомогательных методов, которые я использовал для отладки,я оставил их. 

public class Sorter2
{

    public static void toString(int [] list)
    {
        for(int i = 0; i < list.length; i++)
        {
            System.out.print(list[i]);
            if(!(i + 1 == list.length))
            {
                System.out.print(",");
            }
        }

        System.out.println("");
    }

    public static void toString(int list[], int from, int to)
    {
        for(int i = from; i <= to; i++)
        {
            System.out.print(list[i]);
            if(i + 1 <= to)
            {
                System.out.print(",");
            }
        }

        System.out.println("");
    }


    public static void insertAt(int [] list, int insert_at, int taken_from)
    {
        int to_insert = list[taken_from];
        for(int i = taken_from; i >= insert_at; i--)
        {
            if(i != insert_at)
            {
                list[i] = list[i - 1];
            }
            else
            {
                list[i] = to_insert;
            }
        }
    }

    public static void sortSegments(int [] list ,int segment_one_begin, int segment_one_end, int segment_two_begin, int segment_two_end)
    {
        toString(list, segment_one_begin, segment_two_end);
        int sorted = 0;
        for(int i = segment_two_begin; i <= segment_two_end; i++)
        {
            for(int l = segment_one_begin + sorted; l <= segment_one_end; l++)
            {
                if(list[i] <= list[l])
                {
                    insertAt(list, l, i);
                    sorted++;
                }
            }
        }
        toString(list, segment_one_begin, segment_two_end);
    }

    public static void mergeSort(int [] list, int segment_begining, int segment_end)
    {
        if(segment_end - segment_begining < 1)
        {
            return;
        }
        else
        {
            int midpoint = (segment_end + segment_begining) / 2;

            mergeSort(list, segment_begining, midpoint);
            mergeSort(list, midpoint + 1, segment_end);
            sortSegments(list, segment_begining, midpoint, midpoint + 1, segment_end);

        }

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

    public static boolean isInOrder(int [] toCheck)
    {
        for(int i = 1; i < toCheck.length; i++)
        {
            if(toCheck[i] < toCheck[i - 1])
            {
                return false;
            }
        }

        return true;
    }

    public static int [] populate(int numOfItems)
    {
        int [] toReturn = new int[numOfItems];

        for(int i = 0; i < toReturn.length; i++)
        {
            toReturn[i] = (int) (Math.random() * 100 + 1);
        }

        return toReturn;
    }

    public static void main(String [] args)
    {
        int [] nums = populate(20);
        mergeSort(nums);
        toString(nums);
        System.out.println(isInOrder(nums));

    }
}
3 2
sorting merge

3 ответа:

Давайте немного скорректируем ваш код, чтобы тесты были воспроизводимыми, и мы могли видеть весь процесс: 

import java.util.Random;

public class Sorter2 {
    public static final Random RANDOM = new Random(55);

    public static void toString(int[] list) {
        System.out.println(Arrays.toString(list));
    }

    public static void toString(int list[], int from, int to) {
        System.out.print(from + "\t" + to + "\t");
        for (int i = from; i <= to; i++) {
            System.out.print(list[i]);
            if (i + 1 <= to) {
                System.out.print(",");
            }
        }

        System.out.println("");
    }


    public static void insertAt(int[] list, int insert_at, int taken_from) {
        int to_insert = list[taken_from];
        for (int i = taken_from; i >= insert_at; i--) {
            if (i != insert_at) {
                list[i] = list[i - 1];
            } else {
                list[i] = to_insert;
            }
        }
    }

    public static void sortSegments(int[] list, int segment_one_begin, int segment_one_end, int segment_two_begin, int segment_two_end) {
        System.out.println("Sorter2.sortSegments("+segment_one_begin + "," + segment_one_end + "," + segment_two_begin + "," + segment_two_end + ")");
        toString(list, segment_one_begin, segment_two_end);
        int sorted = 0;
        for (int i = segment_two_begin; i <= segment_two_end; i++) {
            for (int l = segment_one_begin + sorted; l <= segment_one_end; l++) {
                if (list[i] <= list[l]) {
                    insertAt(list, l, i);
                    sorted++;
                }
            }
        }
        toString(list, segment_one_begin, segment_two_end);
    }

    public static void mergeSort(int[] list, int segment_begining, int segment_end) {
        if (segment_end - segment_begining < 1) {
            return;
        }

        int midpoint = (segment_end + segment_begining) / 2;
        mergeSort(list, segment_begining, midpoint);
        mergeSort(list, midpoint + 1, segment_end);
        sortSegments(list, segment_begining, midpoint, midpoint + 1, segment_end);
    }

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

    public static boolean isInOrder(int[] toCheck) {
        for (int i = 1; i < toCheck.length; i++) {
            if (toCheck[i] < toCheck[i - 1]) {
                return false;
            }
        }

        return true;
    }

    public static int[] populate(int numOfItems) {
        int[] toReturn = new int[numOfItems];

        for (int i = 0; i < toReturn.length; i++) {
            toReturn[i] = (int) (nextRandom() * 100 + 1);
        }

        return toReturn;
    }

    private static double nextRandom() {
        return RANDOM.nextDouble();
    }

    public static void main(String[] args) {
        int[] nums = populate(20);
        mergeSort(nums);
        toString(nums);
        System.out.println(isInOrder(nums));
    }
}

Вывод выглядит следующим образом: 

Sorter2.sortSegments(0,0,1,1)
0   1   73,47
0   1   47,73
Sorter2.sortSegments(0,1,2,2)
0   2   47,73,48
0   2   47,48,73
Sorter2.sortSegments(3,3,4,4)
3   4   42,64
3   4   42,64
Sorter2.sortSegments(0,2,3,4)
0   4   47,48,73,42,64
0   4   42,47,48,73,64
Sorter2.sortSegments(5,5,6,6)
5   6   12,38
5   6   12,38
Sorter2.sortSegments(5,6,7,7)
5   7   12,38,14
5   7   12,14,38
Sorter2.sortSegments(8,8,9,9)
8   9   18,87
8   9   18,87
Sorter2.sortSegments(5,7,8,9)
5   9   12,14,38,18,87
5   9   12,14,18,38,87
Sorter2.sortSegments(0,4,5,9)
0   9   42,47,48,73,64,12,14,18,38,87
0   9   12,42,14,18,38,47,48,64,73,87
Sorter2.sortSegments(10,10,11,11)
10  11  60,29
10  11  29,60
Sorter2.sortSegments(10,11,12,12)
10  12  29,60,95
10  12  29,60,95
Sorter2.sortSegments(13,13,14,14)
13  14  21,37
13  14  21,37
Sorter2.sortSegments(10,12,13,14)
10  14  29,60,95,21,37
10  14  21,29,37,60,95
Sorter2.sortSegments(15,15,16,16)
15  16  28,66
15  16  28,66
Sorter2.sortSegments(15,16,17,17)
15  17  28,66,73
15  17  28,66,73
Sorter2.sortSegments(18,18,19,19)
18  19  80,69
18  19  69,80
Sorter2.sortSegments(15,17,18,19)
15  19  28,66,73,69,80
15  19  28,66,69,73,80
Sorter2.sortSegments(10,14,15,19)
10  19  21,29,37,60,95,28,66,69,73,80
10  19  21,28,29,37,60,95,66,69,73,80
Sorter2.sortSegments(0,9,10,19)
0   19  12,42,14,18,38,47,48,64,73,87,21,28,29,37,60,95,66,69,73,80
0   19  12,21,28,29,37,42,14,18,38,47,48,64,73,87,60,95,66,69,73,80
12,21,28,29,37,42,14,18,38,47,48,64,73,87,60,95,66,69,73,80
false
Как видите, первая проблема проявляется в следующих строках: 
Sorter2.sortSegments(0,2,3,4)
0   4   47,48,73,42,64
0   4   42,47,48,73,64
Мы берем два упорядоченных куска и получаем в результате неупорядоченный кусок. Поставьте точку останова на линии for (int i = segment_two_begin; i <= segment_two_end; i++) { и попробуйте поймать случай для Sorter2.sortSegments(0,2,3,4):
  • 42 <= 47, поэтому мы называем insertAt переместить 42 перед 47
  • но это значит 73 теперь в segment_two - и полагается быть на месте!

Вот вам ошибка: ваш sortSegments не работает так, как рекламируется.

Если вы немного подумаете об этом методе, вы обнаружите, что на самом деле вам не нужны вложенные циклы: все, что вам нужно, это найти необходимые элементы, шаг за шагом. Таким образом, вам лучше использовать один цикл от segment_one_begin до segment_two_end и указатель на текущую позицию во втором списке: если элемент из первого списка ниже, чем один из второго, вы просто переходите на новую позицию. Если это не так, вы выполняете сдвиг, который вам нужен-и перемещаете указатель.

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

4

Ура, нашел ошибку и исправил ее!

Http://pastebin.com/UJ3dFfrN

Это nLogn?

0
import java.util.Scanner;

public class Main {
    public static int[] t;

    public static void merge(int[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) t[k] = a[k];
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = t[j++];
            else if (j > hi) a[k] = t[i++];
            else if (t[j] < t[i]) {
                a[k] = t[j++];
            } else a[k] = t[i++];
        }
    }

    public static void sort(int[] a) {
        t = new int[a.length];
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        sort(arr);
    }

}

0