如何計算Quicksort算法中元素比較的數量？

當給定一個元素數組時，如何計算算法執行的元素比較量？如何計算Quicksort算法中元素比較的數量？

這不像向分區方法添加計數器那麼簡單。

private void partition(int low, int high) { 
    int i = low, j = high; 
    // Get the pivot element from the middle of the list 
    int pivot = numbers[low + (high-low)/2]; 

    // Divide into two lists 
    while (i <= j) { 

     if (array[i] < pivot) { 
      i++; 
      compareCount++; //it's not as easy as just adding this here 
     } 
     else if (numbers[j] > pivot) { 
      j--; 
      compareCount++; 
     } 

     else (i <= j) { 
      exchange(i, j); 
      i++; 
      j--; 
     } 
    }

你不能這樣做，因爲它計算剛剛做出的比較，而不是計算結果爲false時的任何比較。

我試過將if (array[i] < pivot)更改爲while (array[i] < pivot)（對於j），但我覺得我仍然錯過了某些東西，如果我這樣做。

來源

2011-03-01 David

相反，你必須指望交換的數量。我認爲我無法解釋你真正想要的東西，可以請澄清一點。還有，如果部分你爲什麼要做++ comparecounter？ – Algorithmist 2011-03-01 03:46:13

我把它留在那裏最初是因爲當對所有相等元素的數組進行排序時，這是我能夠判斷元素何時被排序的唯一方法。 – David 2011-03-01 04:10:53

當你在做while（array [i] Algorithmist 2011-03-01 05:55:17

理想情況下，您應該可以通過分析邏輯來完成。但是如果你想讓程序在運行時爲你做，那麼簡單的方法就是具有執行比較操作的功能。讓函數在每次調用時增加一個全局/靜態變量，然後進行比較。在所有邏輯結束時，只需打印這個全局/靜態變量。

public class Myclass{ 

    public static int compareCount = 0; 

    } 

    /* 
    * PASS parameter comparisonMethod as following 
    * 0 for ==, 1 for >, 2 for >=, 3 for < and 4 for <== 
    * Method returns true or false by doing appropriate comparison based on comparisonMethod 
    */ 

    public bool compare(int i, int j, int comparisonMethod) 
    { 
     Myclass.compareCount++; 
     if(comparisionMethod ==0) return i==j?true:false; 
     if(comparisionMethod ==1) return i>j?true:false; 
     if(comparisionMethod ==2) return i>=j?true:false; 
     if(comparisionMethod ==3) return i<j?true:false; 
     if(comparisionMethod ==4) return i<=j?true:false; 
    } 


    private void partition(int low, int high) { 
     int i = low, j = high; 
     // Get the pivot element from the middle of the list 
     int pivot = numbers[low + (high-low)/2]; 

     // Divide into two lists 
     while (compare(i, j, 4)) { 

      if (compare(array[i], pivot, 3)) { 
       i++; 
      } 
      else if (compare(numbers[j], pivot, 2)) { 
       j--; 
      } 

      else (compare(i, j, 4)) { 
       exchange(i, j); 
       i++; 
       j--; 
      } 
     } 
// At the end of the logic, Myclass.compareCount wil give number of comparisons made.

來源

2011-03-01 03:53:34 PraveenGorthy

我不認爲你需要第一個或最後一個比較，因爲那些只是元素*位置*變量，而不是他們正在比較的實際元素。在這種情況下，如果你刪除了這兩個，它是否仍然捕捉每一個元素的比較？ – David 2011-03-01 04:43:27

你不覺得你有複雜的東西了一些。我認爲在分區程序中的一個簡單的修改會做的trick.Please檢查我的算法 – Algorithmist 2011-03-01 05:42:05

@David由於函數比較是你所做的每一個比較要求，它應該趕上一切。 @Algorithmist我實際上想通過將計數比較邏輯與分區方法分開來簡化問題。我覺得這樣做比較容易，而不是把所有東西都捆綁在一起。話雖如此，這只是一種做法。還有其他的方式，像你所建議的。 – PraveenGorthy 2011-03-01 17:24:28

快速排序的方法分區之前將被稱爲直到數組的大小不是1在這種情況下我們的陣列將sorted.In你的代碼，當你有founf在該樞紐將交換位置（以你的其他部分）你不應該增加比較計數器。

您可以使用此修改的分區方法

partition(A,p,r) 
{ 

    pivot=A[r]; // Taking last element as pivot 
    i=p; 
    j=r; 

    while (true) 
    { 

     while(A[i] < pivot && i <= r) 
     { 

      ++comparecounter; 
      ++i; 

     } 

     while(A[j] >= pivot && j >= 0) 
     { 

      --j; 
      ++comparecount; 

     } 

     if(i < j) 
     { 

      Exchange A[i] and A[j] 

     } 
     else 
     { 
      return j; 
     }

在上述算法中，你可以做countcompare全球這將將incrment來回每次調用partition.This會會算沒有做出comparisions的。

來源

2011-03-01 03:58:25 Algorithmist

您可以嵌入比較計數增量內的每個if語句...

if ((compareCount++ != -1) && (array[i] < pivot)) 
    ... 
    else if ((compareCount++ != -1) && (numbers[j] > pivot)) 
    ... 
    else if ((compareCount++ != -1) && (i <= j))

它永遠評估如果第一條，永遠返回true，始終然後執行第二。

來源

2011-03-01 19:28:10

如何計算Quicksort算法中元素比較的數量？

回答

相關問題