.txt 파일의 Mergesort 행

Question

여러 개의 정렬 된 줄이있는 파일이 있습니다. 이제이 모든 줄을 새 파일의 한 병합 된 줄로 정렬하려고합니다. 한 번에 모든 숫자를로드하지 않고.

12,86,280,304,350,359,371,391,405,548, 
 
255,264,325,346,435,466,483, 
 
39,114,214,298,317,377,428,438,575, 
 
35,165,183,281,336,367,386,418,438,593, 
 
44,77,97,117,122,156,251,415,533, 
 
109,155,163,172,212,226,340,358,452,577,592, 
 
33,74,91,204,256,307,357,388,534,552,554,570, 
 
50,99,246,309,345,358,395,405,419,425,566,

지금 내가 처음에 나는 파일이 얼마나 많은 줄 알 필요가 있으므로, 종류의 사람들을 병합 할 :

이

내 파일의 일부이다. 그런 다음 첫 번째 요소를 모두 얻어 비교해야합니다. 가장 낮은 파일을 새로운 파일에 씁니다. 그런 다음 나는 방금 쓴 줄에서 두 번째 숫자를 얻어야합니다. 그리고 다른 라인의 첫 번째 숫자와 비교하십시오. 어떻게해야합니까? 나는 Arraylists에 대한 머지 소트를 작성했습니다 :

 //as long as there is unsorted data 
 
     while (listOfOutputs.size() > 0) { 
 
      //Set the lowest undefined 
 
      List<Integer> lowest = null; 
 
      for (List<Integer> list : listOfOutputs) { 
 
       //if the lowest is undefined, I'm the lowest 
 
       if (lowest == null) { 
 
        lowest = list; 
 
        //Else am I lower then the lowest? Then I'm the lowest 
 
       } else if (list.get(0) < lowest.get(0)) { 
 
        lowest = list; 
 
       } 
 
      } 
 

 
      //Finally the lowest is added to the sorted list and removed to from his own list. 
 
      assert lowest != null; 
 
      sortedList.add(lowest.remove(0)); 
 

 
      //Is the size of the list which contained to lowest now 0, remove him from the listOfOutputs 
 
      if (lowest.size() == 0) listOfOutputs.remove(lowest); 
 
     }

하지만 내 파일을 정렬 하나에이를 다시 작성하는 방법을 모르겠어요. 목록에로드하지 않고 어떻게 수행합니까?

스벤

Answer 1

당신은 하나의 분류 라인이 생성 될 때까지 과정을 반복, 하나의 라인으로 한 번에 2 개 라인을 병합하는 간단한이 방법 병합을 사용할 수 있습니다. k는 라인의 수를 가정

또는

, 당신은 아마도 작은 첫 번째 요소를 가지고있는 라인을 찾아 최적화하기 위해 힙을 사용하여 k 개의 방법 병합을 구현할 수 있습니다. 각 힙 요소에는 행에 대한 참조와 해당 행에 대한 현재 요소에 대한 색인 (또는 포인터)의 등가가 들어 있습니다. 힙은 각 행의 현재 요소에 의해 정렬되어 힙의 머리 부분은 현재 가장 작은 요소가있는 행을 참조합니다. 힙은 모든 k 라인의 첫 번째 요소로 초기화됩니다.

각 병합 단계마다 힙 머리 부분의 줄 (가장 작은 요소가있는 줄)이 제거되고 가장 작은 요소가 출력 줄에 추가되며 가장 작은 요소를 가진 줄이 힙은 다음 요소를 기반으로합니다.

줄 끝에 도달하면 병합이 k-1 방식 병합으로 줄어들어 결국 병합 된 출력으로 복사되는 한 줄로 끝납니다.