保持比較執行排序

我想跟蹤一個簡單的c + +排序功能的比較量。保持比較執行排序

void sort(int arr[], int size) 
{ 

int startScan, minIndex, minValue; 

for (startScan = 0; startScan < (size - 1); startScan++) 
{ 
    minIndex = startScan; 
    minValue = arr[startScan]; 

    for (int index = startScan + 1; index < size; index++) 
    { 
     if (arr[index] < minValue) 
     { 
      minValue = arr[index]; 
      minIndex = index; 
     } 
    } 
    arr[minIndex] = arr[startScan]; 
    arr[startScan] = minValue; 
} 



}

我玩弄我想可能返回進行的比較的數量，並在第一次也許是比較的數量將在startScan舉行認爲值。當然不是，開始掃描只能保持最大尺寸-1。這絕對不是進行比較的次數。

我想也許它會在變量索引中找到。所以我創建了int temp = index;，因爲我很懶，不想處理它，但是當我返回temp的值時，它也僅僅是size-1。不知道爲什麼我期望有什麼不同，但我想我會嘗試。

然後我開始考慮這個問題......我甚至知道比較在哪裏發生？

原來我不知道我是否做。我想我所有的比較都發生在第二個循環中，即 for (int index = startScan + 1; index < size; index++)，甚至還有嵌套在裏面的if聲明。

無論何時if語句運行，它都會比較一些內容。 SWEET，我想。所以我在我的函數頂部創建了int temp = 0;，在if語句中打了一個temp++，並認爲這肯定會給我一些比較結果。

這次給了我一個鼓舞人心的數字。當對隨機列表中的13個數字進行排序時（我隨機選擇了隨機數字），我的temp返回了18的值。就我所知，對我而言，與我的任何其他數字都沒有線性關係。

所以這是我真正的問題。這是否工作？我的最終代碼是否按照我希望的方式執行，並確實返回進行的比較次數？或者我只是發現了另一個任意數字，我只是比其他測試中得到的其他數字更接近我。我不知道如何手動計算比較次數。我喜歡這個號碼，但是我知道它可能會有所改變。

最終代碼：

int sort(int arr[], int size) 
{ 
int temp = 0; 
int startScan, minIndex, minValue; 

for (startScan = 0; startScan < (size - 1); startScan++) 
{ 
    minIndex = startScan; 
    minValue = arr[startScan]; 

    for (int index = startScan + 1; index < size; index++) 
    { 
     if (arr[index] < minValue) 
     { 
      minValue = arr[index]; 
      minIndex = index; 
      temp++; 
     } 


    } 
    arr[minIndex] = arr[startScan]; 
    arr[startScan] = minValue; 
} 

return temp; 


}

來源

2016-05-31 Podo

每個循環也有每次迭代時間的比較。 – lcs

所以我想我的第一個循環會運行'大小-1'次，我的第二個循環也會運行'大小-1'次，然後我的if循環運行多次？ Addem都起來了嗎？ – Podo

那麼，當條件爲真時，'temp'變量現在只會增加。當它是錯誤的時候也會發生比較。 – lcs

您提高櫃檯只有當數組值小於minValue：

if (arr[index] < minValue) 
    { 
     minValue = arr[index]; 
     minIndex = index; 
     temp++; 
    }

如果你想指望你做出的arr[index] < minValue比較的數字，你應將代碼更改爲：

if (arr[index] < minValue) 
    { 
     minValue = arr[index]; 
     minIndex = index; 
    } 
    temp++;

而且也許給櫃檯一個更好的名字，那麼counter？ ;）

順便說一句，萬一你想你的排序與比較std::sort你能指望它比較的數量是這樣的：

#include <algorithm> 
#include <iostream> 

bool myCountingCompare(int a,int b){ 
    static int counter = 0; 
    counter++; 
    std::cout << "number of comparisons : " << counter << std::endl; 
    return a > b; 
} 

int main() { 
    int array[3] = {1,2,3}; 
    std::sort(&array[0],&array[3],myCountingCompare); 
    return 0; 
}

來源

2016-05-31 20:23:10 user463035818

好的，這是給我一個更大更合理的數字！ – Podo

保持比較執行排序

回答

相關問題