1

10000 個の一意の値を順番にソートするバブル ソート プログラムを作成しました。

プログラムを実行すると、プログラムが完了するまでの時間 (nanoTime を使用) が出力されますが、プログラムのコードに別の出力を追加したいと考えています。プログラムが最初から最後まで並べ替えるのに何回移動するか。

コードは次のとおりです。

public class BubbleSort {
public static void main(String[] args) {
    int BubArray[] = new int[]{#here are 10000 integers#};
    System.out.println("Array Before Bubble Sort");
        for(int a = 0; a < BubArray.length; a++){
             System.out.print(BubArray[a] + " ");
        }

         double timeTaken = bubbleSortTimeTaken(BubArray);
            bubbleSort(BubArray);
            System.out.println("");               
            System.out.println("Array After Bubble Sort");
    System.out.println("    Time taken for Sort : " + timeTaken + " milliseconds.");                
            for(int a = 0; a < BubArray.length; a++){
                    System.out.print(BubArray[a] + " ");
        }
}

private static void bubbleSort(int[] BubArray) {

        int z = BubArray.length;
        int temp = 0;

        for(int a = 0; a < z; a++){
                for(int x=1; x < (z-a); x++){

                        if(BubArray[x-1] > BubArray[x]){

                                temp = BubArray[x-1];
                                BubArray[x-1] = BubArray[x];
                                BubArray[x] = temp;

                        }      
                }
        }
}
public static double bubbleSortTimeTaken(int[] BubArray) {
long startTime = System.nanoTime();
    bubbleSort(BubArray);
long timeTaken = System.nanoTime() - startTime;
return timeTaken;
}
}

コードが実行され、希望どおりに出力されます。

Array Before Bubble Sort
13981 6793 2662 10986 733 10107 2850 ... 
Array After Bubble Sort
10 11 17 24 35 53 57 60 61 78 83 89 128 131 138 141 ....
Time taken for Sort : 1.6788472E7 milliseconds.

しかし、コードに別の出力を追加して、完了までに必要な移動数 (基本的には移動カウンター) を示します。つまり、次のようになります。

Time taken for Sort : 1.6788472E7 milliseconds.
Total number of moves: 3000

これは理にかなっていますか？どんな助けでも感謝します、ありがとう。

4

2 に答える 2

1

これを試して：

// returns the number of switches
private int bubbleSort(int[] BubArray) {

        int z = BubArray.length;
        int temp = 0;
        int timesSwitched = 0;
        for(int a = 0; a < z; a++){
                for(int x=1; x < (z-a); x++){

                        if(BubArray[x-1] > BubArray[x]){

                                temp = BubArray[x-1];
                                BubArray[x-1] = BubArray[x];
                                BubArray[x] = temp;
                                timesSwitched++
                        }      
                }
        }
     return timesSwitched;
}
于 2012-12-06T21:55:59.540 に答える
1

bubbleSortint を返すように変更し、それに時間の複雑さを割り当てます。

private static int bubbleSort(int[] BubArray) {

        int z = BubArray.length;
        int temp = 0;

        int itrs = 0;

        for(int a = 0; a < z; a++){
                for(int x=1; x < (z-a); x++){

                        if(BubArray[x-1] > BubArray[x]){

                                temp = BubArray[x-1];
                                BubArray[x-1] = BubArray[x];
                                BubArray[x] = temp;


                        }    

                        itrs++;
                }
        }

        return itrs;

}

次にmain：

int itrs = bubbleSort(BubArray);
            System.out.println("");               
            System.out.println("Array After Bubble Sort");
    System.out.println("    Time taken for Sort : " + timeTaken + " milliseconds.");  
    System.out.println("Time complexity: " + itrs);
于 2012-12-06T22:00:51.117 に答える