バブルソートコードをデバッグする方法は？

Question

私は大学でこの泡を得て、それを実行しようとしています！それはサイズの小さい順に並べ替えることになっています。どんな助けもありがとう。 （これはYouTubeのDerek Banasからのものです）。なぜそれが動作しないか知っていますか？

public class ListForSorting { 

    int arraySize = 10; 
    int[] myArray = { 10, 12, 3, 4, 50, 60, 7, 81, 9, 100 }; 

    public void printArray() { 

     System.out.println("----------"); 
     for (int i = 0; i < arraySize; i++) { 

      System.out.print("| " + i + " | "); 
      System.out.println(myArray[i] + " |"); 

      System.out.println("----------"); 

     } 

    } 

    public static void main(String[] args) { 
     ListForSorting list = new ListForSorting(); 

     list.printArray(); 

     list.bubbleSort(); 
     list.printArray(); 
    } 

    public void bubbleSort() { 

     for (int i = arraySize - 1; i > 1; i--) { 
      for (int j = 0; j < i; j++) { 
       if (myArray[j] < myArray[j + 1]) 
        swap(j, j + 1); 

      } 
     } 

    } 

    public void swap(int indexOne, int indexTwo) { 
     int temp = myArray[indexOne]; 
     myArray[indexOne] = myArray[indexTwo]; 
     temp = myArray[indexTwo]; 
    } 
} 

出力：

---------- 
| 0 | 10 | 
---------- 
| 1 | 12 | 
---------- 
| 2 | 3 | 
---------- 
| 3 | 4 | 
---------- 
| 4 | 50 | 
---------- 
| 5 | 60 | 
---------- 
| 6 | 7 | 
---------- 
| 7 | 81 | 
---------- 
| 8 | 9 | 
---------- 
| 9 | 100 | 
---------- 
---------- 
| 0 | 81 | 
---------- 
| 1 | 100 | 
---------- 
| 2 | 100 | 
---------- 
| 3 | 100 | 
---------- 
| 4 | 100 | 
---------- 
| 5 | 100 | 
---------- 
| 6 | 100 | 
---------- 
| 7 | 100 | 
---------- 
| 8 | 100 | 
---------- 
| 9 | 100 | 

ありがとう！

Answer 1

swap機能が間違っていました。

public void swap(int indexOne, int indexTwo) { 
    int temp = myArray[indexOne]; 
    myArray[indexOne] = myArray[indexTwo]; 
    myArray[indexTwo] = temp; 
} 

また、bubblesortの機能にエラーがあります。カウンターiはない2に1まで行くべきか、あるいはそれがあるべきよう、あなたの最初の要素をソートすることが習慣：

public void bubbleSort() { 

     for (int i = arraySize - 1; i > 0; i--) { 
      for (int j = 0; j < i; j++) { 
       if (myArray[j] < myArray[j + 1]) 
        swap(j, j + 1); 

      } 
     } 

    } 

今では出力：

---------- 
| 0 | 10 | 
---------- 
| 1 | 12 | 
---------- 
| 2 | 3 | 
---------- 
| 3 | 4 | 
---------- 
| 4 | 50 | 
---------- 
| 5 | 60 | 
---------- 
| 6 | 7 | 
---------- 
| 7 | 81 | 
---------- 
| 8 | 9 | 
---------- 
| 9 | 100 | 
---------- 
---------- 
| 0 | 100 | 
---------- 
| 1 | 81 | 
---------- 
| 2 | 60 | 
---------- 
| 3 | 50 | 
---------- 
| 4 | 12 | 
---------- 
| 5 | 10 | 
---------- 
| 6 | 9 | 
---------- 
| 7 | 7 | 
---------- 
| 8 | 4 | 
---------- 
| 9 | 3 | 
---------- 

あなたが最も小さい番号から最大にしたい場合

public void bubbleSort() { 

     for (int i = arraySize - 1; i > 0; i--) { 
      for (int j = 0; j < i; j++) { 
       if (myArray[j] > myArray[j + 1]) 
        swap(j, j + 1); 

      } 
     } 

    } 

今、目：、ちょうどbubblesort機能でif条件を変更しますE出力は次のようになります。

---------- 
| 0 | 10 | 
---------- 
| 1 | 12 | 
---------- 
| 2 | 3 | 
---------- 
| 3 | 4 | 
---------- 
| 4 | 50 | 
---------- 
| 5 | 60 | 
---------- 
| 6 | 7 | 
---------- 
| 7 | 81 | 
---------- 
| 8 | 9 | 
---------- 
| 9 | 100 | 
---------- 
---------- 
| 0 | 3 | 
---------- 
| 1 | 4 | 
---------- 
| 2 | 7 | 
---------- 
| 3 | 9 | 
---------- 
| 4 | 10 | 
---------- 
| 5 | 12 | 
---------- 
| 6 | 50 | 
---------- 
| 7 | 60 | 
---------- 
| 8 | 81 | 
---------- 
| 9 | 100 | 
---------- 

編集：パフォーマンス

あなたは内側のループは、少なくとも一つのスワップをしなかった場合は、「チェック」することによって、この高速化することができます。それができなかった場合は、終了してから外側のループが存在することを意味し、外側のループの繰り返しの残りの時間を節約します。

Answer 2

あなたは最も問題があり、あなたのコード内のいくつかの問題を得た：

1. 間違っスワップ（最後の行を逆転しなければならない）

2. あなたが全体をループしているN-1回

   これは、配列がソートされるまで、不要にループするだけです。したがって、内部ループにスワップが発生しなくなるまで。

I（C++で）このようにバブルソートを昇順コード：

void sort_asc(int *a,int n) 
    { 
    int i,e; 
    for (e=1;e;n--)     // loop until no swap occurs 
    for (e=0,i=1;i<n;i++)   // process array 
     if (a[i-1]>a[i])    // if swap needed 
     { 
     e=a[i-1];     // swap 
     a[i-1]=a[i]; 
     a[i]=e; 
     e=1;       // allow to process array again 
     } 
    } 

用法：

：降順

int a[]={ 9,8,7,6,5,4,3,2,1,0 }; // worse case scenario 
sort_asc(a,sizeof(a)/sizeof(a[0])); 

は問題だけのに条件を変更しています

 if (a[i-1]<a[i])    // if swap needed 

ところで、ここで32ビットint a[1024]アレイをソートするいくつかの測定を100回ループ：ASCとDESCの種類が同じ速度を有する

      Time  Space 

[ 1.428 ms] Worse case O(n) 
[ 312.744 ms] Bubble asc O(n^2)  O(1 ) OK 
[ 306.084 ms] Bubble dsc O(n^2)  O(1 ) OK 
[ 9.883 ms] Quick asc O(n.log(n)) O(log(n)) OK 
[ 10.620 ms] Quick dsc O(n.log(n)) O(log(n)) OK 

[ 1.816 ms] Random  O(n) 
[ 374.343 ms] Bubble asc O(n^2)  O(1 ) OK 
[ 361.219 ms] Bubble dsc O(n^2)  O(1 ) OK 
[ 14.402 ms] Quick asc O(n.log(n)) O(log(n)) OK 
[ 14.519 ms] Quick dsc O(n.log(n)) O(log(n)) OK 

を両者がので、同じメモリ空間を使用するように若干の測定された差のみによるCACHEであります最初にテストで呼び出されるものは遅くなり、メモリはのCACHEに既にマップされているという事実から2番目の利点が得られます（あまりにも粗すぎない場合）。 btwこのコードは、少しでもさらに最適化することができます...