在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算法中計算基本操作？

回答

相關問題