일반 Mergesort는 정수에서는 작동하지만 문자열로 끝나지 않습니까?

Question

어떤 이유로 든 문자열로 테스트 할 때마다 완전히 일반적이고 정수로 작동한다는 사실에도 불구하고 마지막 병합 반복을 건너 뛰는 것 같습니다. 몇 시간 동안 제 코드를 샅샅이 뒤 졌는데 왜 제대로 작동하지 않는지 알 수 없으므로 어떤 통찰력이라도 잘 받아 들여질 것입니다!

import java.util.Iterator; import java.util.LinkedList;

/** * * @author 폴 */공공 클래스 머지 소트> {

LinkedList<T> theList; 

MergeSort(LinkedList<T> toBeSorted) { 
    theList = toBeSorted; 
} 

public LinkedList<T> sort() { 
    return trueSort(theList); 
} 

private LinkedList<T> trueSort(LinkedList<T> sorting) { 
    if (sorting.size() <= 1) { 
     return sorting; 
    } 
    LinkedList<T> left, right, sorted; 
    left = new LinkedList<T>(); 
    right = new LinkedList<T>(); 
    int middle = sorting.size()/2; 
    Iterator<T> sojourner = sorting.iterator(); 
    for (int i = 0; sojourner.hasNext(); i++) { 
     if (i < middle) { 
      left.add(sojourner.next()); 
     } else { 
      right.add(sojourner.next()); 
     } 
    } 
    return trueMerge(trueSort(left), 

trueSort (오른쪽)); }

private LinkedList<T> trueMerge(LinkedList<T> left, 

LinkedList의 오른쪽) { LinkedList의 결과 = 새 LinkedList의(); while (left.size()> 0 || right.size()> 0) { if (left.size()> 0 & & right.size()> 0) { if (left.getFirst() .compareTo (right.getFirst()) <) { result.add (left.pop()); } else { result.add (right.pop()); } } else if (left.size()> 0) { result.add (left.pop()); } else { result.add (right.pop()); } } 반환 결과; }}

여기 내 주요 자바 파일

의

import java.util.Iterator; 
import java.util.LinkedList; 
import java.util.Random; 

/** 
* 
* @author paul 
*/ 
public class Main { 

    public static Random Rand; 

    public static int randomNumber(int min, int max) { 
    return min + (int) (Rand.nextDouble() * ((max - min) + 

1)); }

public static <T> String getString(LinkedList<T> linkInt) { 
    String s = ""; 
    Iterator<T> interLink = linkInt.iterator(); 
    for (int i = 0; interLink.hasNext(); i++) { 
    s = s + interLink.next().toString(); 
    if (interLink.hasNext()) { 
    s = s + ", "; 
    } 
    if ((i + 1) % 10 == 0) { 
    s = s + "\n"; 
    } 
    } 
    return s; 
    } 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
    Rand = new Random(); 

    LinkedList<Integer> numbers = new LinkedList<Integer>(); 
    for(int i = 0; i< 100;i++){ 
    numbers.add(randomNumber(1,1000)); 
    } 
    System.out.println(getString(numbers)); 
    MergeSort m = new MergeSort(numbers); //change this 

이상) (순수 정적 번호 = m.sort하는 단계; System.out.println (getString (numbers));

LinkedList<String> words = new LinkedList<String>(); 
    words.add("Hello"); 
    words.add("MY"); 
    words.add("name"); 
    words.add("Is"); 
    words.add("Barthoal"); 
    words.add("I"); 
    words.add("Enjoy"); 
    words.add("long"); 
    words.add("beach"); 
    words.add("walks"); 
    words.add("would"); 
    words.add("you"); 
    words.add("like"); 
    words.add("to"); 
    words.add("come"); 
    words.add("Join"); 
    words.add("me"); 
    words.add("in"); 
    words.add("my"); 
    words.add("StarDestroyer-MobileHome? 

(TM) "); 에서 System.out.println (에는 getString (단어))의 머지 소트 mm = 신규 머지 소트 (단어) 단어 mm.sort =(); System.out에 .println (getString (words)); } }

이 출력 :

304, 842, 342, 794, 574, 99, 250, 885, 408, 387, 899, 73, 391, 883, 771, 848, 968, 504, 129, 370, 994, 897, 567, 777, 987, 201, 326, 298, 959, 166, 962, 864, 797, 512, 505, 609, 208, 21, 43, 458, 442, 138, 570, 455, 442, 516, 294, 406, 310, 215, 212, 397, 98, 938 496, 263, 973, 571, 861, 687, 276, 927, 608, 421, 831, 820, 510, 68, 172, 504, 8,976,992, 68, 497, 33, 233, 607, 587, 611, 695, 834, 338, 448, 978, 359, 413, 1, 819, 18, 977, 693, 649

1, 8, 18, 21, 33, 43, 68 , 68, 73, 98, 99,129,138,166,172,21, 233, 250, 263, 276, 294, 298, 304, 310, 326, 326, 338, 342, 345, 359, 370, 387, 391, 397, 406, 408, 41, 421, 442, 442, 448, 455, 458, 496, 497, 504, 504, 505, 510, 512, 516, 541, 547, 567, 570, 571, 574, 587,687, 688, 693, 695, 771, 777, 794, 797, 819, 820, 831, 834, 842, 848, 861, 864, 883, 885, 897, 899, 927, 938, 959, 962, 968, 973, 976, 977, 978, 983, 987, 992, 994

MY, 안녕하세요, 이름,인가, Barthoal, I , 즐기십시오, 길게, 해변, 걷기, would 당신은, to, come, Join, me, in, my, StarDestroyer-MobileHome? (TM)

바르 톨, 즐기십시오, 안녕하세요, 저는, 있습니다, 가입, MY, StarDestroyer-MobileHome? 당신이 볼 수 있듯이 해변처럼, 긴, 나, 내, 이름에 와서 (TM)는, 산책, 당신은

, 숫자가 완전히 분류되어 있습니다 것입니다. 문자열은 병합의 마지막 반복을 놓친 것 같습니다. 정확히 무엇이 잘못 되었습니까?

Answer 1

문자열 비교는 대소 문자를 구분합니다. 즉, 모든 대문자 문자열은 소문자 문자열 앞에 배치됩니다. 병합 정렬 알고리즘은 자신의 유스 케이스에 대해 String.CASE_INSENSITIVE_ORDER 일 수있는 자체 비교자를 허용해야합니다.

Answer 2

코드가 올바르게 정렬됩니다. 대문자가 소문자와 다른 것을 이해해야합니다. "My"지혜 "해변"을 비교할 때 "My"는 "beach"앞에 와야합니다 (대문자는 소문자보다 먼저 오기 때문에).

결과적으로 모든 대문자가 대문자로 시작하는 모든 단어를 맨 앞에 놓는 이유입니다.

compareToIgnoreCase() 메서드 (문자열에 정의 됨)를 사용하여 문자의 대소 문자를 무시하면서 문자열을 비교할 수 있습니다.http://download.oracle.com/javase/1.5.0/docs/api/java/lang/String.html#compareToIgnoreCase(java.lang.String

(그리고 다시 포맷하십시오 코드) 내가 평면 밖으로 그 읽기를 거부