请务必使用我提供的源文件！
我需要实现函数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 <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) {
// Initialize the "stack data structure" to simulate recursive calls
// Note the size of the array.
// Set "top" as -1
// "Push" low and high to "stack"
// In a while loop, "Pop" two top values from s"tack" and simulate
// call of quicksort. If there are still subarrays to sort, their
// low and high values are "pushed to stack".
// Ends when "stack is empty"
}
// Recursive quicksort
// TODO!! Implement this function
void recursive_quicksort(int arr[], int low, int high) {
}
// 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) {
// Initialize output array B equal in size of array A
// Initialize the temporary auxiliary array C. Note it's size
// Fill the temporary array C with zeros
// Store the count of each element into the temporary array C
// Store the cumulative counts into array C
// Find the indexes of the elements of the original array
// and place the elements in the ouput array B
// Find mode from array B
// You do not need to change anything here
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);
/* Uncomment this block of code when you have implemented
the counting sort function
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;
}
