Java, merge sort

Question

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

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

    } 
} 

Answer 1

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

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 и указателем на текущую позицию во втором списке: если элемент из первого списка ниже, чем один из второго, вы просто переходите к новой позиции. Если это не так, вы выполняете требуемый сдвиг и перемещаете указатель.

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

Answer 2

Yay, нашел ошибку и исправил этот вид!

http://pastebin.com/UJ3dFfrN

Это NlogN?

Answer 3

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

}