在Quicksort算法中计算基本操作？

我写了一个quicksort程序，可以工作。我需要包含一个计数器来计算迭代次数。在课堂上，我们讨论了算法，并得出结论：元素比较是基本操作。但是，我不知道该把柜台放在哪里。我似乎无法得到正确的输出结果。我已经包含了我的代码，谢谢！在Quicksort算法中计算基本操作？

void partition(vector<int> & S, int low, int high, int & pivotpoint) 
{ 
vector<int> U; 
int pivotitem = S.at(low); 
int j = low; 
int i; 
for(i = low + 1; i <= high; i++) 
    if(S.at(i) < pivotitem) 
    { 
     j++; 
     swap(S[i], S[j]); 
    } 
pivotpoint = j; 
swap(S[low], S[pivotpoint]); 
} 

void quicksort(vector<int> & S, int low, int high, int &basic_ops) 
{ 
int pivotpoint = low; 
if(high > low) 
{ 
    partition(S, low, high, pivotpoint); 
    quicksort(S, low, pivotpoint -1, basic_ops); 
    quicksort(S, pivotpoint + 1, high, basic_ops); 
} 
}

来源

2013-02-18 Busch

我的计数器认为这个目的可以证明一个全局变量（在文件范围内声明，在函数之外声明），即使它们通常被压抑。（替代方法包括传递一个计数器 - 在我看来是凌乱的 - 或者将函数打包到一个带有成员变量'int counter'的'quicksorter'类中。） – us2012 2013-02-18 04:16:56

我喜欢你的包装想法。使其不那么杂乱。但是，我不知道柜台在哪里。有任何想法吗？ – Busch 2013-02-18 04:26:48

你是指在哪里定义柜台，或者在哪里实际增加柜台？对于后者 - 如你所说，你想计算比较，所以只要你的程序即将进行比较就增加它！ – us2012 2013-02-18 04:27:56

呼叫快速排序为快速排序（阵列，0，长度-1，指针计数器）

void quicksort(vector<int> & S, int low, int high, int &basic_ops) 

{ 

int pivotpoint = low; 
if(high > low) 
{ 

    *basic_ops += high - low; 

    partition(S, low, high, pivotpoint); 

    quicksort(S, low, pivotpoint -1, basic_ops); 

    quicksort(S, pivotpoint + 1, high, basic_ops); 

} 

}

来源

2013-02-18 10:41:59 Deep

将其中枢轴被改变

来源

2013-02-18 14:48:52 TravellingGeek

在Quicksort算法中计算基本操作？

回答

相关问题