njitiecHeart 2023-03-02 08:59 采纳率: 100%
浏览 178
已结题

C语言数据结构的排序问题

请务必使用我提供的源文件!
我需要实现函数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;
}

  • 写回答

5条回答 默认 最新

  • 白驹_过隙 算法领域新星创作者 2023-03-02 15:51
    关注
    
    #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;
    }
     
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(4条)

报告相同问题?

问题事件

  • 系统已结题 3月10日
  • 已采纳回答 3月2日
  • 创建了问题 3月2日

悬赏问题

  • ¥100 需要跳转番茄畅听app的adb命令
  • ¥50 寻找一位有逆向游戏盾sdk 应用程序经验的技术
  • ¥15 请问有用MZmine处理 “Waters SYNAPT G2-Si QTOF质谱仪在MSE模式下采集的非靶向数据” 的分析教程吗
  • ¥50 opencv4nodejs 如何安装
  • ¥15 adb push异常 adb: error: 1409-byte write failed: Invalid argument
  • ¥15 nginx反向代理获取ip,java获取真实ip
  • ¥15 eda:门禁系统设计
  • ¥50 如何使用js去调用vscode-js-debugger的方法去调试网页
  • ¥15 376.1电表主站通信协议下发指令全被否认问题
  • ¥15 物体双站RCS和其组成阵列后的双站RCS关系验证