递归快速排序，计数交换和比较问题 [英] recursive quicksort, count swap and comparison issue

问题描述

我想比较bubblesort与quicksort函数对唯一数字数组进行排序所花费的交换和比较次数(<，>，==，！=).问题是我使用的quicksort函数是递归的，我有点不确定如何跟踪交换比较.尝试使用指针来跟踪计数，但未成功.有人可以帮我吗?

I want to compare how many swaps and comparisons (<, >, ==, !=) it took for a bubblesort vs. quicksort function to sort an array of unique numbers. The problem is that the quicksort function I use is recursive and I am a bit unsure how to keep track of swaps comparisons. Tried to use pointers to keep track of the count but was unsuccessful. Could anyone help me?

我的泡泡排序:

void bubble_sort(int arr[], int max)
{
    int i=0, j, temp, flag;
    int swap=0, comp=0;
    while(1)
    {
        flag = 0;
        for (j = 0 && comp++;  j < max - i - 1; j++)
        {
            comp++;
            if (arr[j] > arr[j+1])
            {
                swap++;
                /* Swapping */

                temp     = arr[j];
                arr[j]   = arr[j+1];
                arr[j+1] = temp;
                flag=1;
            }
        }
        i++;
        comp++;
        if (flag == 0)
        {
            printf("number of swaps: %d\n",swap);
            printf("number of comparisons: %d \n\n",comp);
            break;
        }
    }
}

我的快速排序:

void quicksort(int arr[],int first,int last)
{
    int pivot,j,temp,i;

    if(first<last)
    {
        pivot=first;
        i=first;
        j=last;

        while(i<j)
        {
            while(arr[i]<=arr[pivot]&&i<last)
                i++;
            while(arr[j]>arr[pivot])
                j--;
            if(i<j)
            {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }

        temp=arr[pivot];
        arr[pivot]=arr[j];
        arr[j]=temp;
        quicksort(arr,first,j-1);
        quicksort(arr,j+1,last);

    }
}

解决方案:

void quick_sort(int arr[],int first,int last, int *swap, int *comp)
{
    int pivot,j,temp,i;
    if(++(*comp) && first<last)
    {
        pivot=first;
        i=first;
        j=last;

        while(++(*comp) && i<j)
        {
            while(++(*comp) && arr[i]<=arr[pivot]&&i<last)
                i++;
            while(++(*comp) && arr[j]>arr[pivot])
                j--;
            if(++(*comp) && i<j)
            {
                ++(*swap);
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        ++(*swap);
        temp=arr[pivot];
        arr[pivot]=arr[j];
        arr[j]=temp;
        quick_sort(arr,first,j-1, swap, comp);
        quick_sort(arr,j+1,last, swap, comp);

    }
}

推荐答案

请按照注释中的建议使用全局变量:

Either use a global variable as suggested in the comments :

int _SwapCount = 0;
void quicksort(int arr[],int first,int last)
{
   ...
   //whenever you swap
   _SwapCount++;

或将指向int的指针作为参数:

or take a pointer to an int as a parameter:

void quicksort(int arr[],int first,int last, int* swapCount)
{
   ...
   //whenever you swap
   (*swapCount)++;
   //recursion
   quicksort(arr,first,j-1, swapCount);
   ...

并在顶级快速排序完成后输出swapCount.

and output the swapCount once the top level quicksort has completed.

最初将标签误读为c#;

Edit : initially mis-read the tag as c#;

这篇关于递归快速排序，计数交换和比较问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！