1

10,000個の乱数の配列にJavaクイックソートコードを実装しようとすると問題が発生するようです。配列に配置された数値を含むテキストファイルがあります。このファイルは、並べ替えアルゴリズムに渡されて並べ替えられます。私の目的は、私が持っているタイミングループを使用して、毎回ソートされる数を増やして、ソートにかかる時間を計ることです。しかし、何らかの理由でこのコードを使用すると、直線ではなく曲線のグラフが得られます。タイミングループと配列コードが正常に機能することを知っているので、ソートコードに問題があるようですが、何も見つからないようです。どんな助けでも大歓迎です！

import java.io.*;
import java.util.*;
public class Quicksort {

public static void main(String args[]) throws IOException {
//Import the random integer text file into an integer array
File fil = new File("randomASC.txt");
FileReader inputFil = new FileReader(fil);
int [] myarray = new int [10000];
Scanner in = new Scanner(inputFil);

for(int q = 0; q < myarray.length; q++)
{
  myarray[q] = in.nextInt();
}
in.close();



for (int n = 100; n < 10000; n += 100) { 
long total = 0;
for (int r = 0; r < 10; ++r) {  
  long start = System.nanoTime ();    
      quickSort(myarray,0,n-1);
      total += System.nanoTime() - start;
    }
  System.out.println (n + "," + (double)total / 10.0);
} 
}

 public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p-1 ;
    int j = r+1 ;

    while (true) {
        i++;
        while ( i< r && a[i] < x)
            i++;
        j--;
        while (j>p && a[j] > x)
            j--;

        if (i < j)
            swap(a, i, j);
        else
            return j;
    }
}

private static void swap(int[] a, int i, int j) {
    // TODO Auto-generated method stub
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
}
4

1 に答える 1

2

内部ループの最初の反復のみが、ファイルから読み取った配列を実際にソートします。以降のすべての反復は、すでにソートされている配列に適用されます。

しかし、何らかの理由でこのコードを使用すると、直線ではなく曲線のグラフが得られます。

で実行時間が非線形に増加することを意味する場合n、クイックソートは線形時間アルゴリズムではないため（比較ソートはありません）、これは予想されることです。

パフォーマンスグラフは、優れた2次関数のように見えます。

パフォーマンスグラフ

ピボットを選択したため、時間ではなく2次式O(n log(n))になります。ほとんどの場合、並べ替えられた配列で関数を呼び出すため、ピボットを選択する方法は、毎回最悪のケースに遭遇することを意味します。

于 2012-12-08T13:22:56.033 に答える