请务必使用我提供的源文件！
我需要实现函数recursive_quicksort（）。TODO在第48行上，该功能从第49行开始。在实现它之后，我需要转到find_mode_quicksort（）函数并注释第一个快速排序调用并取消recursive_quicksort（）函数的注释。接下来，实现计数排序。你可以在第96行找到TODO，这个函数从第98行开始。注意，在这里也不需要实现查找模式的逻辑，而只需要实现计数排序部分。一旦您实现了计数排序，你就可以进入主函数，取消注释启动第二个时钟的块，调用计数排序函数，停止时钟，并运行结果。您不需要注释对finde_mode_quicksort（）函数的调用。计数排序不会改变初始数组，因此首先调用它，然后调用快速排序是安全的。快速排序，因此它改变初始数组中元素的顺序。一旦实现了计数排序，请再次编译并运行代码。较两种不同的排序和查找模式方式的执行时间。计数排序需要一个大小相同的数组B来排列数组a。在th的计数排序函数中保留内存最后，实现迭代快速排序。你将在第30行找到TODO，算法从第32行开始。在这里，你还可以找到进一步的说明作为评论来帮助你。一旦您实现了这个功能，您应该再次进入函数find_mode_quicksort（），这次注释掉对递归快速排序的调用，并取消注释对迭代快速排序的调用。再次，编译并运行代码。。再次注意运行时间。
#include
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Swap function to swap two elements of an array
// Used by pratition
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition used by both iterative and recursive quicksort
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[high]);
}
}
swap(&arr[i+1], &arr[high]);
return i + 1;
}
// Iterative quicksort
// TODO!! Implement this function
// Follow instructions in the comments below
void iterative_quicksort(int arr[], int low, int high) {
if (low < high)
{
int *stack = (int*)malloc(sizeof(int) * (high - low + 1));
int pointer = -1;
stack[++pointer] = low;
stack[++pointer] = high;
float ex = 0;
int left, right = 0;
while (pointer != -1)
{
right = stack[pointer--];
left = stack[pointer--];
int i = left - 1;
float pivot = arr[right];
for (int j = left; j < right; ++j)
{
if (arr[j] < pivot)
{
i++;
ex = arr[i];
arr[i] = arr[j];
arr[j] = ex;
}
}
arr[right] = arr[i + 1];
arr[i + 1] = pivot;
if (left < i)
{
stack[++pointer] = left;
stack[++pointer] = i;
}
if (i + 2 < right)
{
stack[++pointer] = i + 2;
stack[++pointer] = right;
}
}
free(stack);
}
}
// Recursive quicksort
// TODO!! Implement this function
void recursive_quicksort(int arr[], int low, int high) {
int left=low;int right=high;
if (left >= right)
return;
int pivot = arr[left];
int i = left, j = right;
while (i < j)
{
while (i < j && arr[j] >= pivot)
j--;
arr[i] = arr[j];
while (i < j && arr[i] < pivot)
i++;
arr[j] = arr[i];
}
arr[i] = pivot;
recursive_quicksort(arr, left, i-1);
recursive_quicksort(arr, i+1, right);
}
// For library quicksort
int compare(const void *a,const void *b) {
int x = *(int *)(a);
int y = *(int *)(b);
return x-y;
}
/* Finds mode by first sorting the array with quicksort
NOTE!!! Quicksort changes the original array,
so only one quicksort function can be used at a time.
The other function calls can be commented out.
qsort() is the library quicksort
*/
int find_mode_quicksort(int *A, int len) {
//qsort(A,len,sizeof(int),compare);
//iterative_quicksort(A, 0, len - 1);
recursive_quicksort(A, 0, len - 1);
// Find mode from the sorted array.
// You do not need to change this
int mode = A[0];
int freq = 1;
int temp = 1;
int i=1;
while (i < len) {
if (A[i] != A[i-1]) {
temp = 1;
}
else {
temp++;
if (temp > freq) {
freq = temp;
mode = A[i];
}
}
i++;
}
printf("\nQuicksort: Mode = %d, frequence = %d\n",mode,freq);
return mode;
}
// Finds mode by first sorting array with counting sort.
// TODO!! Implement the counting sort algorithm in this function
// Follow the instructions in the comments
int find_mode_counting_sort(int *A, int len) {
int n=0;
int *arr_B = (int *)malloc(len*sizeof(int));
int *arrc = (int *)malloc(9999*sizeof(int));
for(int i=0;i<9999;i++)
{
arrc[i]=0;
}
for(int i=0;i<len;i++)
{
arrc[A[i]]+=1;
}
for(int i=1;i<9999;i++)
for(int j=0;j<arrc[i];j++)
arr_B[n++]=i;
int mode = arr_B[0];
int freq = 1;
int temp = 1;
int i=1;
while (i < len) {
if (arr_B[i] != arr_B[i-1]) {
temp = 1;
}
else {
temp++;
if (temp > freq) {
freq = temp;
mode = arr_B[i];
}
}
i++;
}
printf("\nCounting sort: Mode = %d, frequence = %d\n",mode,freq);
// Free memory allocated to array B
free(arr_B);
return mode;
}
// Initialize array with random numbers
// from 0 to 999
void initialize(int *A, int len) {
int i;
for (i=0; i < len; i++) {
A[i] = rand()%1000;
}
}
int main(){
clock_t start,end;
int mode = 0;
// Reserve a large array
int *array = (int *)malloc(100000000*sizeof(int));
// Seed random number generator
// Otherwise it produces the same sequence every time
// Although, same sequence could be used if you want
// to compare efficiency of different quicksort implementations
int seed = time(NULL);
srand(seed);
double totaltime;
int size, threshold;
printf("Input array size > ");
scanf("%d",&size);
printf("\nSearching for mode... \n");
initialize(array,size);
start = clock();
mode = find_mode_counting_sort(array,size);
end = clock();
totaltime = (double)(end-start)/CLOCKS_PER_SEC;
printf("Mode:%d, Consumed time: %f seconds \n",mode,totaltime);
start = clock();
mode = find_mode_quicksort(array,size);
end = clock();
totaltime = (double)(end-start)/CLOCKS_PER_SEC;
printf("Mode:%d, Consumed time: %f seconds \n",mode,totaltime);
// Free memory allocated to the array
free(array);
return 0;
}
参考GPT和自己的思路，不同的排序算法，包括递归和迭代快速排序以及计数排序。此外，您需要注释和取消注释代码以便在这些排序算法之间切换，并记录运行时间以比较它们的性能。这个任务需要相当多的工作和时间，因此我建议您一个一个完成要求，以确保您正确地实现了每个算法和函数。
我可以为您提供一些提示和建议：
阅读和理解代码：在着手修改和实现代码之前，您应该首先仔细阅读并理解给定的代码。查看每个函数的注释，确保您理解它们的目的和输入/输出。
实现递归快速排序：根据注释中的说明，在“recursive_quicksort”函数中实现递归快速排序。这是标准的快速排序算法，它递归地将数组分成两个子数组，并使用“partition”函数来将较小的元素移动到左侧，较大的元素移动到右侧。
实现迭代快速排序：在“iterative_quicksort”函数中实现迭代快速排序。这需要使用一个“stack”数据结构来模拟递归调用。您可以将“low”和“high”值压入堆栈，然后在while循环中模拟快速排序的调用。当堆栈为空时，算法结束。
实现计数排序：在“find_mode_counting_sort”函数中实现计数排序。这需要您创建一个大小为“len”的计数器数组，然后遍历原始数组并计算每个元素的频率。最后，您可以使用频率数组构建排序的数组，该数组将按顺序包含原始数组中的元素。
测试和比较：完成实现后，您需要测试每个算法并记录其运行时间。您可以使用“clock（）”函数来测量代码块的执行时间。请注意，快速排序将更改原始数组，因此在测试计数排序之前，您应该先调用该函数。此外，如果您没有正确实现算法，则测试可能会失败。因此，最好使用小的数组进行测试，并手动验证排序是否正确。
比较不同算法的性能：一旦您实现了所有算法并测试了它们，请比较它们的性能。您可以在主函数中使用“clock（）”函数记录时间，并将结果打印到控制台上。然后，您可以尝试不同大小的数组并比较运行时间。注意，快速排序算法的性能可能会随着数组大小的增加而变得更慢，因为它具有O（n ^ 2）的最坏情况复
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to swap two integers
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to partition the array on the basis of pivot element
int partition(int *arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// Function to perform QuickSort algorithm recursively
void recursive_quicksort(int *arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
recursive_quicksort(arr, low, pi - 1);
recursive_quicksort(arr, pi + 1, high);
}
}
// Function to perform QuickSort algorithm iteratively
void iterative_quicksort(int *arr, int low, int high) {
// Create an auxiliary stack
int stack[high - low + 1];
// Initialize top of stack
int top = -1;
// Push initial values of low and high to stack
stack[++top] = low;
stack[++top] = high;
// Keep popping from stack while it is not empty
while (top >= 0) {
// Pop high and low
high = stack[top--];
low = stack[top--];
// Set pivot element at its correct position in sorted array
int pi = partition(arr, low, high);
// If there are elements on left side of pivot, then push left
// side to stack
if (pi - 1 > low) {
stack[++top] = low;
stack[++top] = pi - 1;
}
// If there are elements on right side of pivot, then push right
// side to stack
if (pi + 1 < high) {
stack[++top] = pi + 1;
stack[++top] = high;
}
}
}
// Comparison function for qsort
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
// Function to find mode of an array using QuickSort algorithm
int find_mode_quicksort(int *A, int len) {
qsort(A,len,sizeof(int),compare);
//iterative_quicksort(A, 0, len - 1);
//recursive_quicksort(A, 0, len - 1);
// Find mode from the sorted array.
// You do not need to change this
int mode = A[0];
int freq = 1;
int temp = 1;
int i=1;
while (i < len) {
if (A[i] != A[i-1]) {
temp = 1;
} else {
temp++;
}
if (temp > freq) {
freq = temp;
mode = A[i];
}
i++;
}
return mode;
}
int main() {
srand(time(NULL));
int A[ARR_SIZE];
// Generate random integers between MIN and MAX
for (int i = 0; i < ARR_SIZE; i++) {
A[i] = rand() % (MAX - MIN + 1) + MIN;
}
// Print the original array
printf("Original array: ");
print_array(A, ARR_SIZE);
// Find the mode using quicksort
int mode = find_mode_quicksort(A, ARR_SIZE);
// Print the mode
printf("Mode: %d\n", mode);
return 0;
}
这是两个快排函数实现
void iterative_quicksort(int arr[], int low, int high)
{
if (low < high)
{
int *stack = (int*)malloc(sizeof(int) * (high - low + 1));
int pointer = -1;
stack[++pointer] = low;
stack[++pointer] = high;
float ex = 0;
int left, right = 0;
while (pointer != -1)
{
right = stack[pointer--];
left = stack[pointer--];
int i = left - 1;
float pivot = arr[right];
for (int j = left; j < right; ++j)
{
if (arr[j] < pivot)
{
i++;
ex = arr[i];
arr[i] = arr[j];
arr[j] = ex;
}
}
arr[right] = arr[i + 1];
arr[i + 1] = pivot;
if (left < i)
{
stack[++pointer] = left;
stack[++pointer] = i;
}
if (i + 2 < right)
{
stack[++pointer] = i + 2;
stack[++pointer] = right;
}
}
free(stack);
}
}
static void Quick(int *arr,int start,int end)
{
if(arr == NULL || start < 0 || start > end)
{
return -1;
}
int par = partition(arr,start,end);
if(start < par-1)
{
Quick(arr,start,par-1);
}
if(par < end-1)
{
Quick(arr,par+1,end);
}
}
void recursive_quicksort(int arr[], int low, int high) {
Quick(arr,low , high);
}