Ошибка алгоритма сортировки слияния Java - не сортировка

Question

Я не могу понять, почему мой алгоритм для программы сортировки слияния с использованием ArrayLists не будет работать ... Если ребята и девочки могут помочь мне разобраться в этом, это будет потрясающе !! Формат, необходимый для печати, должен быть указан на каждом номере и размещаться на новой строке каждые 20 номеров. Моя программа также была ограничена стандартными пакетами Java. Пример ввода и вывода можно найти here. Вот мой код:

import java.io.*; 
import java.util.*; 

public class MergeSort { 
public static void main(String[] args) throws IOException{ 
    Scanner in = new Scanner(System.in); 
    Random r = new Random(); 
    int size, largestInt, holder; 

    System.out.println("How many integers would you like me to create?"); 
    size = in.nextInt(); 
    ArrayList<Integer>list = new ArrayList<Integer>(size); 
    System.out.println("What would the largest integer be?"); 
    largestInt = in.nextInt(); 

    for(int i = 0; i < size; i++){ 
     holder = r.nextInt(largestInt + 1); 
     list.add(holder); 
    } 
    mergeSort(list); 

    for (int j = 0; j < list.size(); j++) { 
     if(j == 19 || j == 39 || j == 59 || j == 79 || j == 99 || j == 119 || j == 139 || j == 159 || j == 179 || j == 199){ 
      System.out.print(list.get(j)); 
      System.out.println(); 
     } 
     else{ 
      System.out.print(list.get(j) + "\t"); 
     } 
    } 
} 

static void mergeSort(ArrayList<Integer> list) { 
    if (list.size() > 1) { 
     int q = list.size()/2; 
     ArrayList<Integer> leftList = new ArrayList<Integer>(); 
     for(int i = 0; i >0 && i <= q; i++){ 
      leftList.add(list.get(i)); 
     } 
     ArrayList<Integer> rightList = new ArrayList<Integer>(); 
     for(int j = 0; j > q && j < list.size(); j++){ 
      rightList.add(list.get(j)); 
     } 

     mergeSort(leftList); 
     mergeSort(rightList); 
     merge(list,leftList,rightList); 
    } 
} 

static void merge(ArrayList<Integer> a, ArrayList<Integer> l, ArrayList<Integer> r) { 
    int totElem = l.size() + r.size(); 
    int i,li,ri; 
    i = li = ri = 0; 
    while (i < totElem) { 
     if ((li < l.size()) && (ri<r.size())) { 
      if (l.get(li) < r.get(ri)) { 
       a.set(i, l.get(li)); 
       i++; 
       li++; 
      } 
      else { 
       a.set(i, r.get(ri)); 
       i++; 
       ri++; 
      } 
     } 
     else { 
      if (li >= l.size()) { 
       while (ri < r.size()) { 
        a.set(i, r.get(ri)); 
        i++; 
        ri++; 
       } 
      } 
      if (ri >= r.size()) { 
       while (li < l.size()) { 
        a.set(i, l.get(li)); 
        li++; 
        i++; 
       } 
      } 
     } 
    } 
} 

Заранее благодарен!

Answer 1

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

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

Подумайте, как работает Merge Sort - он рекурсивный по своей природе, потому что это метод разделения и завоевания. Он решает большую сложную проблему, разбивая ее на небольшие простые задачи и в основном просто объединяет результат из всех этих проблем - ваш алгоритм MergeSort просто должен охватить это.

Если мы пишем это вам нужно сделать следующие шаги:

(1) Проверьте, если список содержит только один элемент - то это уже отсортирован

(2) Разделить вход в равных по размеру списки и отсортировать их до начала (рекурсивный шаг)

(3) Объедините два отсортированных списка и верните один отсортированный список.

Я вижу, что у вас есть сложный метод для части слияния и используйте базовую итерацию для разделяющей части. Список Java (суперкласс, например, ArrayList) предлагает .subList(fromIndex, toIndex) для разбивки списков на более мелкие списки. Вы должны использовать это. Для присоединяемых частей:

На основе этой анимации из википедии

это должно быть довольно просто, как вы должны думать об объединении двух списков:

Сначала поддерживают оба список в списках, легко удалить объекты из. Поскольку в этот момент мы знаем, что списки будут отсортированы, нас интересует только первый объект в каждом списке (самый маленький элемент).

Во-вторых, нам нужно только сравнить первый элемент каждого списка, удалить из них самый маленький из его списка и добавить его в наш отсортированный список. Мы продолжаем делать это до тех пор, пока оба списка не будут пустыми - на этом этапе мы объединили наши списки.

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

Итак, вы должны пересмотреть свою стратегию реализации и упростить свой код на основе того, как вы должны атаковать алгоритм MergeSort. Если это выглядит comfusing здесь, это пример реализации MergeSort в Java, использующий только стандартный API (нет встроенного метода сортировки).

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

import java.util.LinkedList; 
import java.util.Random; 
import java.util.List; 

public class Main { 

    public static void main(String[] args){ 

     Random random = new Random(); 
     LinkedList<Integer> unsorted = new LinkedList<Integer>(); 
     for(int i = 0; i<100; i++){ 
      unsorted.add(random.nextInt(100)); 
     } 

     System.out.println("unsorted: " + unsorted.toString()); 

     List<Integer> sorted = mergeSort(unsorted); 

     System.out.println("sorted: " + sorted.toString()); 
    } 

    //Recursive function for sorting a LinkedList 
    private static LinkedList<Integer> mergeSort(LinkedList<Integer> unsorted){ 

     //If the list only contains 1 object it is sorted 
     if(unsorted.size() == 1){ 
      return unsorted; 
     } 

     //Split the list in two parts and create a new list to store our sorted list 
     LinkedList<Integer> left = mergeSort(new LinkedList<Integer>(unsorted.subList(0, unsorted.size()/2))); 
     LinkedList<Integer> right = mergeSort(new LinkedList<Integer>(unsorted.subList(unsorted.size()/2, unsorted.size()))); 
     LinkedList<Integer> sorted = new LinkedList<Integer>(); 

     //Actual loop for merging the two sublists. Using LinkedLists, this is efficient. (Compared to ArrayList) 
     while(!left.isEmpty() || !right.isEmpty()){ 
      Integer leftInt = left.peekFirst(); 
      Integer rightInt = right.peekFirst(); 

      if(!(leftInt == null) && !(rightInt == null)){ 
       if(leftInt < rightInt){ 
        sorted.add(left.pollFirst()); 
       } 
       else{ 
        sorted.add(right.pollFirst()); 
       } 
      } 
      else if(leftInt == null){ 
       sorted.add(right.pollFirst()); 
      } 
      else{ 
       sorted.add(left.pollFirst()); 
      } 
     } 

     return sorted; 
    } 
}