爲一個已排序陣列的運行時間由選擇排序算法進行排序Vs的時間爲反轉排序的數組進行排序

我想搞清楚的運行時間使用的選擇排序算法來排序的已排序陣列（例如， 1,2,3,4,5，..）以及使用它排序反向數組的時間（例如5,4,3,2 ..）。我發現的奇怪的事情是，在我的計算機上，排序已排序的數組需要更多的時間，而不是排序反向數組。從我所瞭解的情況來看，我認爲它應該是相反的。爲一個已排序陣列的運行時間由選擇排序算法進行排序Vs的時間爲反轉排序的數組進行排序

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
void selectionsort(int A[], int n) { 
    int min; 
    for (int i = 0; i < n - 1; i++) { 
     min = i; 
     for (int k = i + 1; k < n; k++) { 
      if (A[k] < A[min]) { 
       min = k; 
      } 
     } 
     int temp = A[i]; 
     A[i] = A[min]; 
     A[min] = temp; 
    } 
} 

void sort(int A[], int n) { 
    for (int i = 0; i < n; i++) { 
     A[i] = i + 1; 
    } 
} 

void resver_sort(int A[], int n) { 
    for (int i = 0; i < n; i++) { 
     A[i] = n - i; 
    } 
} 

int main() { 
    clock_t start, end; 
    double cpu_time_used; 

    int A[20000] = { 0 }; 
    int B[40000] = {0}; 
    int C[100000] = {0}; 

    printf("Selection Sort, Sorted Array\n"); 

    sort(A, 20000); 
    start = clock(); // start the clock 
    selectionsort(A, 20000); 
    end = clock(); // stop the clock 
    cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC; // calculate the actual time used 
    printf("array size:20000 time:%f\n", cpu_time_used); 

    sort(B, 40000); 
    start = clock(); 
    selectionsort(B, 40000); 
    end = clock(); 
    cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC; 
    printf("array size:40000 time:%f\n", cpu_time_used); 

    sort(C, 100000); 
    start = clock(); 
    selectionsort(C, 100000); 
    end = clock(); 
    cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC; 
    printf("array size:100000 time:%f\n", cpu_time_used); 

    printf("Selection Sort, reverse sorted Array\n"); 

    resver_sort(A, 20000); 
    start = clock(); 
    selectionsort(A, 20000); 
    end = clock(); 
    cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC; 
    printf("array size:20000 time:%f\n", cpu_time_used); 

    resver_sort(B, 40000); 
    start = clock(); 
    selectionsort(B, 40000); 
    end = clock(); 
    cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC; 
    printf("array size:40000 time:%f\n", cpu_time_used); 

    resver_sort(C, 100000); 
    start = clock();  
    selectionsort(C,100000); 
    end = clock(); 
    cpu_time_used = ((double)(end - start))/CLOCKS_PER_SEC; 
    printf("array size:100000 time:%f\n", cpu_time_used); 
}

結果是

Selection Sort, Sorted Array 
array size:20000 time:0.530281 
array size:40000 time:2.109836 
array size:100000 time:13.197117 
Selection Sort, reverse sorted Array 
array size:20000 time:0.500338 
array size:40000 time:2.016468 
array size:100000 time:12.830447 
Program ended with exit code: 0

第一個是一個已排序陣列需要更多的時間。這沒有意義。我花了很多時間調試並嘗試打印這些數組以查看它們，但沒有弄明白。

來源

2017-02-26 Zhenghao He

就做幾千次，並獲得* *平均時間。對優化版本也做這種測量。 –

你能否考慮重新加入你的代碼，以便它可以被實際讀取。 –

@Antti Haapala抱歉，我不知道它對你來說是不可讀的。我修改了它。:) –

有你的代碼中的多個問題：

你不包括<stdio.h>和<time.h>
你不定義數組B和C。我建議你使用靜態或動態（堆）存儲而不是自動的數組來避免堆棧溢出。
功能sort有緩衝區溢出：for (int i = 0; i <= n; i++)應該i < n。

關於定時，你的分頁功能selectionsort執行完全相同數量的比較和交換，除了這樣的定時也必然接近，只有在A[k] < A[min]結果不同的結果。在排序的情況下，該測試總是錯誤的，並且對於另一種情況而言，真實情況的數量從n - 2線性遞減到0。根據這個循環的代碼生成方式以及CPU的分支預測功能的效率如何，您可能會爲其中一個或另一個獲得小優勢，只有仔細計時才能告訴您這一點。從你的結果看來，分支的成本從未超過補償額外的min = i商店。

您的時間實際上是非常接近（小於6％的差異）。我得到了相同的結果，但是同一個程序的多次運行給出了相同數量級的時序...使得很難得出明確的結論。

不同的編譯器和不同的CPU可能會產生相反的結果。

的初始通檢查已經排序輸入是值得的，因爲它增加了很少的低效有點像insertionsort的定時。它會使這些特殊情況幾乎是瞬時的：例如，您可以使用0.00001，0.00002和0.00005。

更高效的排序算法也將使這些時間變得更加簡單：heapsort，mergesort，quicksort，radix排序應該都在100到1000之間times更快。

來源

2017-02-26 09:33:58 chqrlie

爲一個已排序陣列的運行時間由選擇排序算法進行排序Vs的時間爲反轉排序的數組進行排序

回答

相關問題