如何计算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算法中元素比较的数量？

回答

相关问题