정수 파일의 빠른 정렬

Question

정수의 사용자 입력 파일을 빨리 정리해야합니다 (파일의 각 줄에는 하나의 정수가 포함되어 있습니다). 내 quicksort 방법을 작동, 나는 이미 그들을 테스트했습니다. 파일을 읽고 동일한 파일의 정렬 된 순서로 인쇄하는 데 문제가 있습니다. 나는 또한 과정에 걸리는 시간을 측정해야한다. 여기에 제가 지금까지 가지고있는 것이 있습니다 : 메서드에 전달 된 첫 번째 인수는 파일이 될 정수의 수이고 전달 된 두 번째 인수는 파일의 이름입니다. generateRandom() 메소드는 Question0 클래스에서 가져온 것이고 각각은 라인으로 구분 된 임의의 정수로 파일을 생성합니다. int와 filename이라는 두 개의 인수를 취합니다. filename이라는 이름의 파일을 만들고 int 정수로 구성됩니다. 바라기를이 모든 것이 의미가 있습니다.

편집 : 여기에 작동하는 코드가 있지만 파일에 1 백만 개의 숫자가있을 때 실행하는 데 문제가 있습니다. outofmemory 오류를 제공합니다. 10 억 명이있을 때, 그것은 숫자 형식으로 말하는 것입니다. 10 억 개의 숫자가있는 테스트 파일을 실행해야합니다.

import java.io.File; 
import java.io.FileNotFoundException; 
import java.io.FileReader; 
import java.io.PrintWriter; 
import java.util.ArrayList; 
import java.util.Scanner; 

public class QuickSort1000 { 
    public static void main(String[] args) throws Exception 
    { 
     int n = Integer.parseInt(args[0]); 
     String filePath = args[1]; 
     Question0 genRan = new Question0(); 
     genRan.generateRandom(n, filePath); 
     //rest if for quicksorting 
     File inFile = new File(filePath); 
     Scanner in = new Scanner(inFile); 
     int[] list = new int[n]; 
     for(int i = 0; i < n; i++) 
     { 
      list[i] = in.nextInt(); 
     } 
     in.close(); 

     long startTime = System.nanoTime(); 
     qSort(list, 0, list.length - 1); 
     long endTime = System.nanoTime(); 
     long duration = endTime - startTime; 
     System.out.println("Total time: " + duration + " nanoseconds"); 
     for(int i = 1; i < list.length; i++) 
     { 
      if(list[i - 1] > list[i]) 
      { 
       throw new Exception("Not in sorted order"); 
      } 
      //System.out.print(list[i]); 
     } 

    } 

     // TODO Auto-generated constructor stub 
    /** 
    * The main quicksort method that uses the partition method below 
    * @param a the input array 
    * @param p the first valid index of array 
    * @param r the last valid index of array 
    */ 
     public static void qSort(int[] a, int p, int r) { 
      // TODO Auto-generated method stub 
      if (p < r) 
      { 
       int q = Partition(a, p, r); 
       qSort(a, p, q - 1); 
       qSort(a, q + 1, r); 
      } 

     } 
     /** 
     * Partitions the array with respect to the last element in the array 
     * @param a the input array 
     * @param p the first element in the array 
     * @param r the last element in the array 
     * @return the element with which we will partition with respect to. The 
     * return element will be in its correct spot. 
     */ 
     private static int Partition(int[] a,int p, int r) 
     { 
      int x = a[r]; 
      int i = p - 1; 
      int temp = 0; 
      for(int j = p; j <= r - 1; j++) 
      { 
       if(a[j] <= x) 
       { 
        i++; 
        temp = a[i]; 
        a[i] = a[j]; 
        a[j] = temp; 
       } 
      } 
      temp = a[i+1]; 
      a[i+1] = a[r]; 
      a[r] = temp; 
      return i + 1; 
     } 


    } 

Answer 1

는 다음과 같은 성명을 바탕으로, 나는 영업 이익은 입력 및 출력에 같은 파일에 IO을 수행하는 방법을 요구하고 있음을 추론.

파일을 읽고 동일한 파일의 정렬 순서로 인쇄하는 데 문제가 있습니다.

1. 당신은 사용자가 정확히 얼마나 많은 정수를 말하는 경우 hasNext()를 사용할 필요가 없습니다.
2. 많은 정수가 이미 알고있는 경우에도 비슷한 크기로 List을 만들 필요가 없습니다.
3. 당신이 그것을 깨뜨릴 준비가 될 때까지 파일을 가리키는 PrintWriter을 열면 안됩니다.

원래 질문에서 수정 된 버전은 main입니다.

public static void main(String[] args) throws FileNotFoundException 
{ 
    int n = Integer.parseInt(args[0]); 
    String filePath = args[1]; 
    //rest is for the quicksorting 
    File inFile = new File(filePath); 
    Scanner in = new Scanner(inFile); 
    int[] list = new int[n]; 
    for(int i = 0; i < n; i++) 
     list[i] = in.nextInt(); 
    in.close(); 
    long startTime = System.currentTimeMillis(); 
    qSort(list, 0, list.length - 1); 
    long endTime = System.currentTimeMillis(); 
    long duration = endTime - startTime; 
    System.out.println(duration); 


    // Create a PrintWriter and clobber the file AFTER you have read it. 
    PrintWriter out = new PrintWriter(filePath); 
    for (int i = 0; i < n; i++) { 
     System.out.println(list[i]); 
     out.println(list[i]); 
    } 
    out.close(); 

}