カウントループと比較

Question

4つの異なるソート方法で発生するループと比較の回数を数える必要があります。 Selection、Bubble、Insertion、およびQuick sortメソッドを使用しています。理想的には、ループ/比較のたびにloopCounterや++などのintを配置するだけです。このすべてに全く新しいものですが、私はそのようなカウンターを含める必要があるときを区別することができません。あなたが次のコードで見ることができるように、私は複数のカウンターを作成しようとしました。しかし、私は今まで選択カウンタだけが正しいと思います。

さらに、値がシフトされた回数をカウントする必要があります。つまり、整数が何回交換されたかということです。

これに関するお手伝いをいただければ幸いです。カウンターで

おかげ

ArrayList<Integer> list = new ArrayList<Integer>(); 

    //Counters for Selection Sort 
    int loopCounter = 0; 
    int compCounter = 0; 
    //Counters for Bubble Sort 
    int loopCounter2 = 0; 
    int compCounter2 = 0; 
    //Counters for Insertion Sort 
    int loopCounter3 = 0; 
    int compCounter3 = 0; 
    //Counters for Quick Sort 
    int loopCounter4 = 0; 
    int compCounter4 = 0; 

public void selectionSort(Integer[] a) { 

    for(int i = 0; i < a.length; i++) { 
     int smallestValue = a[i]; 
     int smallestIndex = i; 
     if(ascButton.isSelected()){ 
      for(int j = i+1; j < a.length; j++) { 
       if (smallestValue > a[j]) { 
        smallestValue = a[j]; 
        smallestIndex = j; 
        loopCounter++; 
        compCounter++; 
       } 
      } 
     a[smallestIndex] = a[i]; 
     a[i] = smallestValue; 
     } else if(desButton.isSelected()){ 
      for(int j = i+1; j < a.length; j++) { 
       if (smallestValue < a[j]) { 
        smallestValue = a[j]; 
        smallestIndex = j; 
        loopCounter++; 
        compCounter++; 
       } 
     } 
     a[smallestIndex] = a[i]; 
     a[i] = smallestValue; 
     } 
    } 
} 

public void bubbleSort(Integer[] a) { 

    int temp; 

    for (int i = a.length - 1; i > 0; i--) { 
     if(ascButton.isSelected()) { 
      for(int j = 0; j < i; j++) { 
       loopCounter2++; 
       compCounter2++; 
       if(a[j] > a[j + 1]) { 
        temp = a[j]; 
        a[j] = a[j + 1]; 
        a[j + 1] = temp; 
       } 
      } 
      } else if(desButton.isSelected()) { 
       for(int j = 0; j < i; j++) { 
        loopCounter2++; 
        compCounter2++; 
        if(a[j] < a[j + 1]) { 
         temp = a[j]; 
         a[j] = a[j + 1]; 
         a[j + 1] = temp; 
        } 
       } 
      } 

    } 
} 

public void insertionSort(Integer[] a) { 
    for(int i = 1; i < a.length; i++) { 
     loopCounter3++; 
     compCounter3++; 
     int temp = a[i]; 
     int j = i - 1; 

     if(ascButton.isSelected()) { 
      while(j >= 0 && a[j] > temp) { 
      a[j + 1] = a[j]; 
      j--; 
     } 
     a[j + 1] = temp; 
     } else if(desButton.isSelected()) { 
      while(j >= 0 && a[j] < temp) { 
      a[j + 1] = a[j]; 
      j--; 
     } 
     a[j + 1] = temp; 
     } 

    } 
} 

public void quickSort(Integer[] a, int left, int right) { 
    int i = left; 
    int j = right; 
    int temp; 
    int pivot = a[(left + right)/2]; 
    while(i <= j) { 
    if(ascButton.isSelected()) { 
     while(a[i] < pivot) 
      i++; 
     while(a[j] > pivot) 
      j--; 
    } else if(desButton.isSelected()) { 
     while(a[i] > pivot) 
      i++; 
     while(a[j] < pivot) 
      j--; 
    } 
     if(i <= j) { 
      temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp; 
      i++; 
      j--; 
     } 
    } 
    if(left < j) { 
     quickSort(a,left,j); 
    } 
    if(i < right) { 
     quickSort(a, i, right); 
    }    
} 

Answer 1

、あなたは単にあなたが何かをカウントするプログラムしたい場合、「カウント」にしたいです。だからあなたが自分のコードを理解していなければ、何かを "数えたい"時を知ることは難しいでしょう。

swapCount++;//Each time a swap happens increment by 1 
    iterationCount++//A full pass has happened increment by 1 

注：それはあなたのコード内で起こっているとき、私はあなたがのいくつかの並べ替えをしたいときには、スワップが起きているときに把握勧めのフルパスは、多くのソートに起こっているという理由だけで、上記あなたがおそらく知っている、それはソートされているわけではありません、それはちょうど1パスを行ったと言っているだけです。

この理論が役立つかどうかはわかりません。あなたの問題がまだ何かに苦しんでいることについて私はいくつかのフィードバックを与え、あなたの探しているものをよりよく反映するように答えを変えることができるかどうかを見ていきます。

Answer 2

@Andreasが示唆しているように、ループカウンタと比較カウンタが正しく配置されています。 スワップカウンターに関しては、このように考えてください。一時変数なしでスワップすることはできません。その結果、一時変数が関与するときはいつでも、あなたはスワップカウンターを増やしたいと思う。 例として、あなたのクイックソートのために、それは次のようになります。

public void quickSort(Integer[] a, int left, int right) { 
    int i = left; 
    int j = right; 
    int temp; 
    int pivot = a[(left + right)/2]; 
    while(i <= j) { 
    if(ascButton.isSelected()) { 
     while(a[i] < pivot) 
      i++; 
     while(a[j] > pivot) 
      j--; 
    } else if(desButton.isSelected()) { 
     while(a[i] > pivot) 
      i++; 
     while(a[j] < pivot) 
      j--; 
    } 
     if(i <= j) { 
      temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp; 
      i++; 
      j--; 
      swapCounterForQuickSort++; 
     } 
    } 
    if(left < j) { 
     quickSort(a,left,j); 
    } 
    if(i < right) { 
     quickSort(a, i, right); 
    }    
} 

はあなたの他の種類のために同じロジックに従ってください。

また、いくつかの一般的な提案：彼らは、彼らがために使用されているものを教えてくれているよう

• は、必ず変数に名前を付けます。 loopCounter1ではなく、loopCounterForSelectionSortなどを試してみてください。長い変数名を恐れてはいけません。情報は力です！
• できるだけ短く再利用可能な機能にしてください。たとえば、コード内で整数を多く入れ替えるとします。たぶん、スワップコードをコピーしてswapIntegers（）関数に貼り付けることができます。その後、毎回交換するときにこの機能を呼び出すだけです！また、スワップカウンターを使ってカウンターを入れてカウンティングすることができるので、スワップカウンターの質問に簡単に答えることができます。 （複数のメソッドがスワップカウンタを呼び出して引数などとして渡すことがあるので注意してください）