2

ソート プログラム (挿入ソート アルゴリズムの実装を使用して 100000 の整数をソートする) の Java コードで、配列内の要素が交換された回数を調べようとしています。sort() メソッドは静的であるため、これを静的変数として設定します。

ただし、プログラムの実行中に、整数の制限を超えて、最終的なカウントが負として表示されると思います。これを修正して数値的に正しいカウントを取得する方法があるはずですが、私はこれを理解することができません..助けてもらえますか?

public class InsertionSort {
    private static int exchcount=0;

    public static void exch(Comparable[] a, int i,int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    public static int exchangeCount(){
        return exchcount;
    }

    public static void sort(Comparable[] a){
    int N = a.length;       

    for(int i=0; i< N;i++){
        for(int j=i; j>0 && less(a[j],a[j-1]); j--){
        exch(a,j,j-1);
        exchcount++;

        }
       }
   }
...

    public static void main(String[] args) {
        Integer[] a = RandomNumberArrayGenerator.generate(100000);
        sort(a);
        System.out.println("number of exchanges="+ exchangeCount());
   }

これは与える

number of exchanges= -1799089211
4

4 に答える 4

5

long最も簡単なのは、カウンターをではなく に変えることですint。これにより、9,223,372,036,854,775,807 まで数えることができます。

すべてが 1 CPU サイクルかかる場合、3 GHz のコンピューターでカウンターがオーバーフローするexch()のに約 100 年かかります。long

于 2013-06-29T12:06:20.817 に答える
4

プリミティブ型intは符号付きで、-2,147,483,648 ～ 2,147,483,647 (両端を含む) の 32 ビット値です。これについては、 Java チュートリアルを参照してください。

終了後の値が -1799089211 の場合は、exchanges2,147,483,647 に達すると、-2,147,483,647 よりも -2,147,483,648 になることを意味します...つまり(-2,147,483,648 + 1799089211 - 1)、プリミティブ型の制限を超えていますint。もちろん、この状況では、カウンターが 1 回だけオーバーフローしたと仮定していますが、2 回以上オーバーフローする必要があります。

データ型を使用longし、(念のため) カウンターのオーバーフローをテストします。

于 2013-06-29T12:06:52.680 に答える
1

それを増やすたびに、それが負であるかどうかを確認し、オーバーフローを 1 に設定することができます。これを追跡するために別の整数を使用することもできます。おそらく後で0に設定します。チャンスはありますか

exchcount++;

の中へ

    exchcount++;
    if (exchcount<0) {
      overflowcount++;
      exchcount=0;
   }

代わりに long を使用することもできます。これにより、プログラムで 32 ビットの代わりに 64 ビットを使用できるようになります。

これはあなたがチャンスを必要とするでしょう

private static int exchcount=0;

の中へ

private static long exchcount=0;

これにより、2^31 ではなく 2^63 に向かって数えることができます。

于 2013-06-29T12:04:33.623 に答える
0

longの代わりに使用しintます。それは簡単な答えです。

于 2013-06-29T12:16:11.990 に答える