通过搜索算法进行比较的读取次数

Question

所以我一直在尝试写一个带有气泡和插入排序的随机列表排序代码；代码的目的是生成一个随机数组，用冒泡排序然后快速排序，然后告诉它采取了多少步冒泡排序和用了多少快速排序。然后，它重复这十次，然后找出快速排序所做的平均步骤数和气泡排序的平均步骤数。

我遇到的问题是，当我调用快速排序使用的步骤数时，我最终得到数字1，而当我调用10个快捷键的平均值时，我会得到4950 (每次)。我把它用于冒泡排序，但由于某些原因，它不能用于插入排序--我认为这与优化代码以避免重复有关，但我不知道下一步该做什么；任何帮助都是非常感谢的！

链接到我的代码(显示输出)：https://onlinegdb.com/r14EPAGqm

我的代码：

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

static int num_count_bubble_sort = 0;
static double avg_bubble = 0;
static int num_count_quick_sort = 0;
static double avg_quick = 0;

void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
} 

// A function to implement bubble sort 
void bubbleSort(int arr[], int n) 
{ 
   int i, j;

   num_count_bubble_sort = 0;

   for (i = 0; i < n-1; i++)
   {
       int swapped = 0;

       // Last i elements are already in place 
       for (j = 0; j < n-i-1; j++)
       {
           num_count_bubble_sort++;
           avg_bubble++;

           if (arr[j] > arr[j+1])
           {
              swap(&arr[j], &arr[j+1]);
              swapped = 1;
           }
       }
      if (swapped == 0) break;
   }
} 

/* This function takes last element as pivot, places 
   the pivot element at its correct position in sorted 
   array, and places all smaller (smaller than pivot) 
   to left of pivot and all greater elements to right 
   of pivot */

int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    // pivot 
    int i = (low - 1);  // Index of smaller element 

    num_count_quick_sort =0;

    for (int j = low; j <= high- 1; j++) 
    { 
        // If current element is smaller than or 
        // equal to pivot

        num_count_quick_sort++;
        avg_quick++;

        if (arr[j] <= pivot) 
        { 
            i++;    // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 

/* The main function that implements QuickSort 
 arr[] --> Array to be sorted, 
  low  --> Starting index, 
  high  --> Ending index */
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        /* pi is partitioning index, arr[p] is now 
           at right place */
        int pi = partition(arr, low, high); 

        // Separately sort elements before 
        // partition and after partition 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 

/* Function to print an array */
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
} 

/* random array generator */
int main()
{
    srand(time(NULL));

    int l;

    for (int l = 10; l>0; l--)
    {
        int r;
        int arr[100];

        printf("Original Array: \n");

        for (int r = 99; r>=0; r--)
        {
            int rand_num = rand() % 100;

            printf("%d ",rand_num);

            arr[r] = rand_num;
        }

        /* bubble sort */

        int n = sizeof(arr)/sizeof(arr[0]); 

        bubbleSort(arr, n);

        printf("\n");

        printf("Bubble Sorted Array: \n"); 

        printArray(arr, n); 

        /*quick sort */
        num_count_quick_sort=0;
        quickSort(arr, 0, n-1);

        printf("\n");

        printf("Quick Sorted Array: \n");

        printArray(arr, n);

        printf("\n");

        /* printing amount of comparisons done by each sort */

        printf("comparisons done by bubble sort: %d ", 
num_count_bubble_sort);

        printf("\n");

        printf("comparisons done by Quick sort: %d ",num_count_quick_sort);

        printf("\n");
    }

    printf("\n");

    avg_quick = avg_quick/10.0;

    avg_bubble = avg_bubble/10.0;

    printf("average number of comparisons done by Bubble Sort (list length 
of 100 elements): %f", avg_bubble);

    printf("\n");

    printf("average number of comparisons done by Quick Sort(list length of 
100 elements): %f", avg_quick);
}

作为一个免责声明，我刚刚开始学习c，所以我肯定不会理解语言的某些东西。

Answer 1

这里发生了两件事。

首先，您的测试代码执行以下操作：

1. 创建一个随机数组
2. 用气泡排序对数组进行排序
3. 对数组进行快速排序

因此，您总是传递一个排序数组来快速排序。这就是为什么快速排序的平均值总是等于4950。

若要解决此问题，请复制数组并将副本传递给冒泡排序。然后，您可以确定快速排序和冒泡排序都提供了相同的输入。

num_count_quick_sort始终为1的原因是，每次输入partition函数时都将其设置为0。而且，由于对partition的最后一次调用总是使high和low相差1，所以您只需要遍历一次迭代循环。您需要删除partition函数中的赋值。

另一件事是，计算平均值的方法有点奇怪，尽管在这种情况下，它产生的结果是相同的。您所做的是为所有的运行积累一个总数，同时您也在为一次运行积累总数。也就是说，你有：

num_count_quick_sort++;
avg_quick++;

更常见的方法是只在运行结束时更新avg_quick。在您的代码中有：

    /* printing amount of comparisons done by each sort */
    printf("comparisons done by bubble sort: %d ", num_count_bubble_sort);
    printf("\n");
    printf("comparisons done by Quick sort: %d ,num_count_quick_sort);
    printf("\n");

因此，您可以从循环中删除avg_quick (和avg_bubble)的增量，而是编写：

    /* printing amount of comparisons done by each sort */
    printf("comparisons done by bubble sort: %d\n", num_count_bubble_sort);
    avg_bubble += num_count_bubble_sort;

    printf("comparisons done by Quick sort: %d\n",num_count_quick_sort);
    avg_quick += num_count_quick_sort;

(请注意，我在这些printf语句的末尾添加了一个换行符。不需要单独的语句来打印新行。)

这样做的主要原因不是效率，而是简单。它缩小了avg_quick和avg_bubble变量的范围，使之更容易防止其他无关的代码无意中修改它们。