Как напечатать время выполнения сортировки слиянием

Question

пример программы здесь

У меня есть программа, которая позволяет пользователю вводить 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

Вот некоторые рекомендации:

• include <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