Requirement
Implement void quicksort(unsigned int *a, int n) as a “C” style function in the file quicksort.cc
- The pivot should always be chosen as the first element of the array.
- See the given quicksort.cc file for how to determine running times. You can modify this file as you wish but I should be able to run it to get your output in the file specified.
- The main function in quicksort.cc reads from the file “quicksortinput” the n integers and writes the n integers to the file “quicksortoutput” in ascending sorted order. See “quicksortsampleinput” and “quicksortsampleoutput” for formatting details. Please make sure that your program can EXACTLY reproduce that output file given the input file. You may want to use the “diff” program to test this.
- The function sorts the array a of n positive integers with the quick sort algorithm.
Implement void radixsort(unsigned int *a, int n) as a “C” style function in the file radixsort.cc
- The elements of the array are positive and are represented with 32 bits.
- See the given radixsort.cc file for how to determine running times. You can modify this file as you wish but I should be able to run it to get your output in the file specified.
- The main function in radixsort.cc reads from the file “radixsortinput” the n integers and writes the n integers to the file “radixsortoutput” in ascending sorted order. See “radixsortsampleinput” and “radixsortsampleoutput” for formatting details. Please make sure that your program can EXACTLY reproduce that output file given the input file. You may want to use the “diff” program to test this.
- The function sorts the array a of n positive integers using the radix sort algorithm.
Analysis
需要实现Quicksort算法以及Radix sort算法。
本题难度不大，但需要理解和掌握这两种算法的原理和特点。
此外需要注意的是，测试集并非是结构化的数据，需要对测试集中字符进行分割，同时处理空行的问题。