阅读搜索算法完成的比较次数

Question

所以我一直在尝试用c编写一个带有冒泡和插入排序的随机列表排序代码；代码的目的是生成一个随机数组，用冒泡排序然后快速排序对其进行排序，然后告诉冒泡排序用了多少步与快速排序用了多少步。然后它重复十次，然后找到快速排序的平均步骤数和冒泡排序的平均步骤数。

我遇到的问题是，当我要求快速排序使用的步数时，我最终得到数字 1，而当我要求 10 次快速排序的平均值时，我得到 4950 (每次）。我让它适用于冒泡排序，但出于某种原因，它不适用于插入排序——我认为这与优化我的代码以使其不重复有关，但我不知道下一步该怎么做；任何帮助将不胜感激！

link 到我的代码（显示输出）：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

这里发生了两件事。

首先，你的测试代码是这样做的：

创建一个随机数组
使用冒泡排序对数组进行排序
使用快速排序对数组进行排序

所以您总是将排序后的数组传递给快速排序。这就是为什么快速排序的平均值始终等于 4,950。

要解决该问题，请复制数组并将副本传递给冒泡排序。那么您确定快速排序和冒泡排序提供了相同的输入。

之所以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 变量的范围，更容易防止它们被其他不相关的代码无意中修改。

阅读搜索算法完成的比较次数

Reading number of comparisons done by Search Algorithms

c

algorithm

search

quicksort

bubble-sort