gpt4 book ai didi

c - 递归快速排序,计数交换和比较问题

转载 作者:太空宇宙 更新时间:2023-11-04 06:23:39 25 4
gpt4 key购买 nike

我想比较冒泡排序与快速排序函数对唯一数字数组进行排序所花费的交换和比较(<、>、==、!=)次数。问题是我使用的快速排序函数是递归的,我有点不确定如何跟踪交换比较。试图使用指针来跟踪计数但没有成功。谁能帮帮我?

我的冒泡排序:

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);

}
}

最佳答案

按照评论中的建议使用全局变量:

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

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

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

并在顶层快速排序完成后输出 swapCount。

编辑:最初将标签误读为 c#;

关于c - 递归快速排序,计数交换和比较问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29943571/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com