計數循環和比較

Question

我需要計算在四種不同的排序方法上發生的循環次數和比較次數。我正在使用「選擇」，「泡泡」，「插入」和「快速排序」方法。理想情況下，每次循環/比較時，我只需放置一個int，如loopCounter和++。雖然對於所有這些方面來說都很新穎，但我在區分需要包含這些計數器時遇到了困難。正如你將能夠看到下面的代碼，我試圖創建多個計數器。儘管如此，我認爲目前爲止只有選拔計數是正確的。

此外，我需要計算一個值轉移的次數。換句話說，整數交換了多少次。

任何與此有關的幫助將不勝感激！

感謝

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（）函數中。然後每當你想交換的時候你就調用這個函數！此外，請注意這是如何使您的交換計數器問題更容易回答的，因爲您可以在交換方法中設置一個計數器來爲您計數。 （雖然請注意，因爲多個方法會調用swap計數器，因此您可能想將它作爲參數傳遞等）。