Java Recursive MergeSort для ArrayLists

Question

У меня возникла проблема с моей функцией mergesort, так как я не могу сортировать серию целых чисел или строк при вводе ее в программу. У меня есть внешний класс, который вызывает элементы в нем, однако он просто не сортирует числа/строки. Ниже приведены два метода, я не знаю, где проблема. Номера вводятся случайным образом.

КОД:

/** 
    * Takes in entire vector, but will merge the following sections together: 
    * Left sublist from a[first]..a[mid], right sublist from a[mid+1]..a[last]. 
    * Precondition: each sublist is already in ascending order 
    * 
    * @param a 
    *   reference to an array of integers to be sorted 
    * @param first 
    *   starting index of range of values to be sorted 
    * @param mid 
    *   midpoint index of range of values to be sorted 
    * @param last 
    *   last index of range of values to be sorted 
    */ 
    private void merge(ArrayList<Comparable> a, int first, int mid, int last) { 
     int x; 
     int i; 
     ArrayList<Comparable> left = new ArrayList<Comparable>(); 
     ArrayList<Comparable> right = new ArrayList<Comparable>(); 
     mergeSort(a,first,mid); 
     for(i = 0; i < a.size() - mid; i++){ 
      left.add(i,a.get(i)); 
      a.remove(i); 
     } 
     mergeSort(a,mid,last); 
     for (x = mid; x < a.size(); x++) { 
      right.add(x,a.get(x)); 
      a.remove(x); 
     } 
     if ((left.get(i).compareTo(right.get(x))) > 0) { 
      i++; 
      a.add(i); 
     } else if (i < x) { 
      x++; 
      a.add(x); 
     } 


     System.out.println(); 
     System.out.println("Merge"); 
     System.out.println(); 

    } 

    /** 
    * Recursive mergesort of an array of integers 
    * 
    * @param a 
    *   reference to an array of integers to be sorted 
    * @param first 
    *   starting index of range of values to be sorted 
    * @param last 
    *   ending index of range of values to be sorted 
    */ 
    public void mergeSort(ArrayList<Comparable> a, int first, int last) { 

     int mid = (first + last)/2; 
     if(first == last){ 

     }else if(last - first == 1){ 
      merge(a,first, mid ,last);    
     }else{ 
      last = mid; 
     } 


       } 

Answer 1

У меня есть внешний класс, который вызывает элементы в него, однако он просто не сортирует числа/строки. Ниже приведены два метода, я не знаю, где проблема.

Первая проблема заключается в том, что если вы называете метод mergeSort с first = 0 и last = a.size() вы ничего не сортировать, как вы только позвоните merge если last-first == 1:

public void mergeSort(ArrayList<Comparable> a, int first, int last) { 
    int mid = (first + last)/2; 
    if(first == last){ 
    }else if(last - first == 1){ 
     // you only merge if last - first == 1... 
     merge(a,first, mid ,last);    
    }else{ 
     last = mid; 
    } 
} 

Appart с этого момента, я не» t получить, как вы пытаетесь реализовать алгоритм сортировки слиянием. Это ни верхняя, ни нижняя реализация. Вы раскалываетесь внутри метода слияния, что также очень странно. Было бы проще помочь вам, если бы вы предоставили свой псевдокод + способ, которым вы называете свой метод public. ИМХО, у вас есть реальная проблема с вашим алгоритмом.

Фактически алгоритм сортировки слияния действительно прост в реализации. Чтобы проиллюстрировать это, я написал эту top down implementation of the merge sort algorithm с помощью Deque вместо List объектов:

import java.util.Deque; 
import java.util.LinkedList; 

public class Example { 

    private LinkedList<Comparable> merge(final Deque<Comparable> left, final Deque<Comparable> right) { 
     final LinkedList<Comparable> merged = new LinkedList<>(); 
     while (!left.isEmpty() && !right.isEmpty()) { 
      if (left.peek().compareTo(right.peek()) <= 0) { 
       merged.add(left.pop()); 
      } else { 
       merged.add(right.pop()); 
      } 
     } 
     merged.addAll(left); 
     merged.addAll(right); 
     return merged; 
    } 

    public void mergeSort(final LinkedList<Comparable> input) { 
     if (input.size() != 1) { 
      final LinkedList<Comparable> left = new LinkedList<Comparable>(); 
      final LinkedList<Comparable> right = new LinkedList<Comparable>(); 
      // boolean used to decide if we put elements 
      // in left or right LinkedList 
      boolean logicalSwitch = true; 
      while (!input.isEmpty()) { 
       if (logicalSwitch) { 
        left.add(input.pop()); 
       } else { 
        right.add(input.pop()); 
       } 
       logicalSwitch = !logicalSwitch; 
      } 
      mergeSort(left); 
      mergeSort(right); 
      input.addAll(merge(left, right)); 
     } 
    } 
} 

я использовал Deque потому peek()/pop() является Способов симпатичнее ИМХО чем get(0) и remove(0), но это до вас. Если вы абсолютно хотите использовать ArrayList, здесь следует соответствующая реализация.

import java.util.ArrayList; 
import java.util.List; 

public class Example { 

    private List<Comparable> merge(final List<Comparable> left, final List<Comparable> right) { 
     final List<Comparable> merged = new ArrayList<>(); 
     while (!left.isEmpty() && !right.isEmpty()) { 
      if (left.get(0).compareTo(right.get(0)) <= 0) { 
       merged.add(left.remove(0)); 
      } else { 
       merged.add(right.remove(0)); 
      } 
     } 
     merged.addAll(left); 
     merged.addAll(right); 
     return merged; 
    } 

    public void mergeSort(final List<Comparable> input) { 
     if (input.size() != 1) { 
      final List<Comparable> left = new ArrayList<Comparable>(); 
      final List<Comparable> right = new ArrayList<Comparable>(); 
      boolean logicalSwitch = true; 
      while (!input.isEmpty()) { 
       if (logicalSwitch) { 
        left.add(input.remove(0)); 
       } else { 
        right.add(input.remove(0)); 
       } 
       logicalSwitch = !logicalSwitch; 
      } 
      mergeSort(left); 
      mergeSort(right); 
      input.addAll(merge(left, right)); 
     } 
    } 
} 

Оба работают реализация с Integer и String или других Comparable.

Надеюсь, это поможет.

Answer 2

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

Collections.sort(); 

Если вы хотели бы реализовать свою собственную версию Merge рода, то вы должны смотреть на первую this implementation.

И если вы заинтересованы в улучшении понимания алгоритмов сортировки, я рекомендую this book.

Answer 3

Есть несколько проблем, но важным является то, что вы не должны перебирать список при изменении списка, то есть в:

for (i = 0; i < a.size() - mid; i++){ 
    left.add(i,a.get(i)); 
    a.remove(i); 
} 

, потому что, как только вы удалите элемент, индексы для других не то же самое ...Таким образом, вы добавляете в left элементы a, которые не так вы думаете.

Рабочий код следующим образом (с некоторыми комментариями):

private static void merge(ArrayList<Comparable> a) { 
    if (a.size()<=1) return; // small list don't need to be merged 

    // SEPARATE 

    int mid = a.size()/2; // estimate half the size 

    ArrayList<Comparable> left = new ArrayList<Comparable>(); 
    ArrayList<Comparable> right = new ArrayList<Comparable>(); 

    for(int i = 0; i < mid; i++) left.add(a.remove(0)); // put first half part in left 
    while (a.size()!=0) right.add(a.remove(0)); // put the remainings in right 
    // Here a is now empty 

    // MERGE PARTS INDEPENDANTLY 

    merge(left); // merge the left part 
    merge(right); // merge the right part 

    // MERGE PARTS 

    // while there is something in the two lists 
    while (left.size()!=0 && right.size()!=0) { 
     // compare both heads, add the lesser into the result and remove it from its list 
     if (left.get(0).compareTo(right.get(0))<0) a.add(left.remove(0)); 
     else          a.add(right.remove(0)); 
    } 

    // fill the result with what remains in left OR right (both can't contains elements) 
    while(left.size()!=0) a.add(left.remove(0)); 
    while(right.size()!=0) a.add(right.remove(0)); 
    } 

Он был протестирован на некоторых входах ... Пример:

[4, 7, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11] 
[0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] 

Для повышения эффективности можно использовать метод subList избегайте слишком большого количества дополнительных списков, необходимо будет следить за индексами.