如何打印归并排序的执行时间

Question

sample program output here

我这里有一个程序，可以让用户输入 N 个随机生成的数字。现在，我在打印它时遇到了问题。它打印的时间超过了执行时间。

void merge_sort(int i, int j, int a[], int aux[]) {

    start = clock();
    if (j <= i) {
      // if the subsection is empty or a single element
      return;
    }
    int mid = (i + j) / 2;

    // left sub-array is a[i .. mid]
    // right sub-array is a[mid + 1 .. j]

    merge_sort(i, mid, a, aux);         // sort the left sub-array recursively
    merge_sort(mid + 1, j, a, aux);     // sort the right sub-array recursively

    int pointer_left = i;               // pointer_left points to the beginning of the left sub-array
    int pointer_right = mid + 1;        // pointer_right points to the beginning of the right sub-array
    int k;                              // k is the loop counter

    // we loop from i to j to fill each element of the final merged array
    for (k = i; k <= j; k++) {
        if (pointer_left == mid + 1) {                      // left pointer has reached the limit
            aux[k] = a[pointer_right];
            pointer_right++;
        } else if (pointer_right == j + 1) {                // right pointer has reached the limit
            aux[k] = a[pointer_left];
            pointer_left++;
        } else if (a[pointer_left] < a[pointer_right]) {     // pointer left points to smaller element
            aux[k] = a[pointer_left];
            pointer_left++;
        } else {        // pointer right points to smaller element
            aux[k] = a[pointer_right];
            pointer_right++;
        }
    }
    // copy the elements from aux[] to a[]
    for (k = i; k <= j; k++) {
        a[k] = aux[k];
    }
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("TIME: %f\n", cpu_time_used);
}

// main method
int main(){

    int size, i;
    printf("Enter N: ");
    scanf("%d", &size);
    int array[size];
    int aux[size];
    if(size <= 0)
    {
        printf("\n Error!\n");
    }

    for (i = 0; i < size; i++)
    {
        array[i] = rand() % MAXRANGE;

    }

    printf("\nMerge Sorted: ");
    merge_sort(0, size - 1, array, aux);
    printArray(array, size);

    return 0;
}

我不知道在哪里放置 clock() 调用或执行时间的计算。是打印后吗？

Answer 1

以下是一些准则：

包括<time.h>
使用 clock_t start = clock() 在您要计时的函数之前获取当前时间。
在函数结束后用clock_t elapsed = clock() - start;计算经过的时间。
在定时例程期间不产生输出。
避免在您要计时的函数之前产生任何输出。

输出经过的时间转换为毫秒数：

printf("Elapsed time: %12.3f\n", elapsed * 1000.0 / CLOCKS_PER_SEC);

您在代码中遵循了这些准则，但您应该将计时移到 mergesort 之外，因为此函数是递归的。

这是修改后的版本：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void merge_sort(int i, int j, int a[], int aux[]) {
    if (j <= i) {
        // if the subsection is empty or a single element
        return;
    }
    int mid = (i + j) / 2;

    // left sub-array is a[i .. mid]
    // right sub-array is a[mid + 1 .. j]

    merge_sort(i, mid, a, aux);         // sort the left sub-array recursively
    merge_sort(mid + 1, j, a, aux);     // sort the right sub-array recursively

    int pointer_left = i;               // pointer_left points to the beginning of the left sub-array
    int pointer_right = mid + 1;        // pointer_right points to the beginning of the right sub-array
    int k;                              // k is the loop counter

    // we loop from i to j to fill each element of the final merged array
    for (k = i; k <= j; k++) {
        if (pointer_left == mid + 1) {  // left pointer has reached the limit
            aux[k] = a[pointer_right];
            pointer_right++;
        } else if (pointer_right == j + 1) {  // right pointer has reached the limit
            aux[k] = a[pointer_left];
            pointer_left++;
        } else if (a[pointer_left] < a[pointer_right]) {  // pointer left points to smaller element
            aux[k] = a[pointer_left];
            pointer_left++;
        } else {                        // pointer right points to smaller element
            aux[k] = a[pointer_right];
            pointer_right++;
        }
    }
    // copy the elements from aux[] to a[]
    for (k = i; k <= j; k++) {
        a[k] = aux[k];
    }
}

#define MAXRANGE 1000

// main method
int main() {
    clock_t start, elapsed1, elapsed2;
    int size, i;

    printf("Enter N: ");
    if (scanf("%d", &size) != 1 || size <= 0) {
        printf("Invalid input!\n");
        return 1;
    }

    int array[size];
    int aux[size];

    start = clock();
    for (i = 0; i < size; i++) {
        array[i] = rand() % MAXRANGE;
    }
    elapsed1 = clock() - start;

    start = clock();
    merge_sort(0, size - 1, array, aux);
    elapsed2 = clock() - start;

    printf("initialisation time: %12.3f\n",
           (double)elapsed1 * 1000.0 / CLOCKS_PER_SEC);
    printf("    merge sort time: %12.3f\n",
           (double)elapsed2 * 1000.0 / CLOCKS_PER_SEC);

    for (i = 1; i < size; i++) {
        if (array[i - 1] > array[i])
            break;
    }

    if (i == size) {
        printf("array sorted\n");
    } else {
        printf("sort error: array[%i] = %d > array[%i] = %d\n",
               i - 1, array[i - 1], i, array[i]);
    }
    return 0;
}

输出：

Enter N: 500000
initialisation time:        5.783
    merge sort time:       45.890
array sorted

Answer 2

以下是一些准则：

获取执行时间：

include <time.h>
int main(){
    struct timeval stop,start;
    int arr[10000];
    gettimeofday(&start,NULL);
    mergeSort(arr, 100);
    gettimeofday(&stop,NULL);
    printf("Time taken for Quick sort is: %ld microseconds\n", 
        (stop.tv_sec-start.tv_sec)*1000000+stop.tv_usec-start.tv_usec);
}

如何打印归并排序的执行时间

How to print the execution time of Merge Sort

c

mergesort

execution-time