Java 병합 정렬 알고리즘 오류 - 정렬하지 않음

Question

ArrayList를 사용하는 병합 정렬 프로그램의 알고리즘이 작동하지 않는 이유를 알 수 없습니다 ... 녀석과 할아버지가 내게 도움이된다고 생각하면 도움이 될 것입니다! 인쇄에 필요한 형식은 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 List (수퍼 클래스, 예 : ArrayList)는 목록을 작은 목록으로 분할하기 위해 .subList(fromIndex, toIndex)을 제공합니다. 이걸 사용해야합니다. 머징의 경우 : 위키 피 디아

에서이 애니메이션을 기반으로

당신이 두 목록 병합에 대해 생각하는 방법은 오히려 간단해야한다 :

우선리스트로 두 목록을 유지를 그 개체를 쉽게 제거 할 수 있습니다. 이 시점에서 목록이 정렬 될 것이라는 것을 알기 때문에 각 목록의 첫 번째 개체 (가장 작은 요소)에만 관심이 있습니다.

둘째, 각 목록의 첫 번째 요소를 비교하고 두 목록 중 가장 작은 항목을 해당 목록에서 제거한 다음 정렬 된 목록에 추가해야합니다. 두 목록이 모두 비어있을 때까지 계속이 작업을 수행합니다.이 시점에서 목록을 병합했습니다.

자바에서는 병합 부분에 데이터 구조를 사용해야 각 목록의 첫 번째 요소를 살펴보고 관심있는 데이터를 빠르게 제거 할 수 있음을 나타냅니다. Java에서이 데이터 구조는 LinkedList - ArrayList입니다. 둘 다이 작업에서 끔찍하게 수행하며이를 수행하는 적절한 방법을 제공하지 않습니다. LinkedList는 대기열로 동작하며 목록 끝에있는 객체를 쉽게 확인하고 제거 할 수있는 메소드를 제공합니다. 첫 번째 요소.

MergeSort 알고리즘을 공격하는 방법에 따라 구현 전략을 재검토하고 코드를 단순화해야합니다. 여기에 표준 API 만 사용하는 Java에서 MergeSort의 샘플 구현이 있습니다 (정렬 메소드에서는 빌드되지 않음).

희망이 있습니다.

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