Description
Introduction:
In this PA, you are required to implement various sorters that we learnt in the class. You can download the PA1.tar file from NTU COOL website. Uncompress it using Linux command, tar xvf PA1.tar You can see the following directories after uncompressing it. Name Description bin/ Directory of binary file doc/ Directory of document inputs/ Directory of unsorted data lib/ Directory of library source code outputs/ Directory of sorted data src/ Directory of source code utility/ Directory of checker Input/output Files: In the input file (*.in), the first two lines starting with ‘#’ are just comments. Except comments, each line contains two numbers: index followed by the unsorted number.
The range of unsorted number is between 0 and 1,000,000. Two numbers are separated by a space. For an example, the file 5.case1.in contains five numbers Handout #3 September 19, 2019 Chien-Mo Li National Taiwan University Department of Electrical Engineering Algorithms, Fall 2019 # 5 data points # index number 0 16 1 13 2 0 3 6 4 7 The output file(*.out) is actually the same as the input file except that the numbers are sorted in increasing order. For example, 5.case1.out is like: # 5 data points # index number 0 0 1 6 2 7 3 13 4 16 PLOT: You can visualize your unsorted/sorted numbers by using the gnuplot tool by the command gnuplot. After that, please key in the following set xrange [0:5] set yrange [0:20] plot “5.case1.in” usi 1:2 plot “5.case1.out” usi 1:2 # if you want to save to png files set terminal png set output “5.case1.out.png” replot You need to allow X-window display to see the window if you are login remotely. For more gnuplot information, see https://people.duke.edu/~hpgavin/gnuplot.html There are two example “before” and “after” sort pictures with 100 numbers benchmark.
Before sort： After sort： Command line parameters: In the command line, you are required to follow this format NTU_sort –[IS|MS|QS|HS] where IS represents insertion sort, MS is merge sort, QS is quick sort and HS is heap sort. The square bracket with vertical bar ‘[IS|MS|QS|HS]’ means that only one of the four versions is chosen.
The angle bracket should be replaced by the name of the input file, *.[case1|case2|case3].in, where case1 represents test case in random order, case2 is test case in increasing order, and case3 is test case in reverse order. For the best case, all the numbers are sorted in increasing order. For the worst case, all numbers are sorted in descending order. For the average case, numbers are in random order. The output file names are *.[case1|case2|case3].out. Please note that you
do NOT need to add ‘[|]’ or ‘<>’ in your command line. For example, the following command sorts 10000.case1.in to 10000.case1.out using insertion sort. ./bin/NTU_sort -IS inputs/10000.case1.in outputs/10000.case1.out Source code files: Please notice that all of the source code files have been already finished except sort_tool.cpp. You only need to complete the different sorting functions of class SortTool in sort_tool.cpp. You can still modify other source code files if you think it is necessary. The following will simply introduce the source code files. main.cpp: main program for
1. // ************************************************************************** 2. // File [main.cpp] 3. // Author [Yu-Hao Ho] 4. // Synopsis [The main program of 2019 fall Algorithm PA1] 5. // Modify [2019/9/6 Cheng-Yun Hsieh] 6. // ************************************************************************** 7. 8. #include 9. #include 10. #include 11. #include “../lib/tm_usage.h” 12. #include “sort_tool.h” 13. 14. using namespace std; 15. 16. void help_message() { 17. cout << “usage: NTU_sort -[IS|MS|QS|HS] ” << endl; 18. cout << “options:” << endl; 19. cout << ” IS – Insersion Sort” << endl; 20. cout << ” MS – Merge Sort” << endl; 21. cout << ” QS – Quick Sort” << endl; 22. cout << ” HS – Heap Sort” << endl; 23. } 24. 25. int main(int argc, char* argv[]) 26. { 27. if(argc != 4) { 28. help_message(); 29. return 0; 30. } 31. CommonNs::TmUsage tmusg; 32. CommonNs::TmStat stat; 33. 34. //////////// read the input file ///////////// 35. 36. char buffer[200]; 37. fstream fin(argv[2]); 38. fstream fout; 39. fout.open(argv[3],ios::out); 40. fin.getline(buffer,200); 41. fin.getline(buffer,200); 42. int junk,num; 43. vector data; 44. while (fin >> junk >> num) 45. data.push_back(num); // data[0] will be the first data. 46. // data[1] will be the second data and so on. 47. 48. //////////// the sorting part //////////////// 49. tmusg.periodStart(); 50. SortTool NTUSortTool; 51. 52. if(!strcmp(argv[1],”-QS”)) { 53. NTUSortTool.QuickSort(data); 54. } 55. else if(!strcmp(argv[1],”-IS”)) { 56. NTUSortTool.InsertionSort(data); 57. } 58. else if(!strcmp(argv[1],”-MS”)) { 59.
NTUSortTool.MergeSort(data); 60. } 61. else if(!strcmp(argv[1],”-HS”)) { 62. NTUSortTool.HeapSort(data); 63. } 64. else { 65. help_message(); 66. return 0; 67. } 68. 69. tmusg.getPeriodUsage(stat); 70. cout <<“The total CPU time: ” << (stat.uTime + stat.sTime) / 1000.0 << “ms” << endl; 71. cout <<“memory: ” << stat.vmPeak << “KB” << endl; // print peak memory 72. 73. //////////// write the output file /////////// 74. fout << “# ” << data.size() << ” data points” <<endl; 75.=”” fout=”” <<=”” “#=”” index=”” number”=”” endl;=”” 76.=”” for=”” (int=”” i=”0;” <=”” data.size();=”” i++)=”” 77.=”” “=”” <<data[i]=”” 78.=”” fin.close();=”” 79.=”” fout.close();=”” 80.=”” return=”” 0;=”” 81.=”” }=”” handout=”” #3=”” september=”” 19,=”” 2019=”” chien-mo=”” li=”” national=”” taiwan=”” university=”” department=”” of=”” electrical=”” engineering=”” algorithms,=”” fall=”” main.cpp=”” line=”” 36-46:=”” parse=”” unsorted=”” data=”” from=”” input=”” file=”” and=”” push=”” them=”” into=”” the=”” vector.=”” 52-67:=”” call=”” different=”” function=”” depending=”” on=”” given=”” command.=”” 74-77:=”” write=”” sorted=”” file.=”” sort_tool.h:=”” header=”” sorttool=”” class=”” 1.=””
**************************************************************************=”” 2.=”” [sort_tool.h]=”” 3.=”” author=”” [yu-hao=”” ho]=”” 4.=”” synopsis=”” [the=”” class]=”” 5.=”” modify=”” [2019=”” 9=”” 6=”” cheng-yun=”” hsieh]=”” 6.=”” 7.=”” 8.=”” #ifndef=”” _sort_tool_h=”” 9.=”” #define=”” 10.=”” 11.=”” #include<vector=””> 12. using namespace std; 13. 14. class SortTool { 15. public: 16. SortTool(); // constructor 17. void InsertionSort(vector&); // sort data using insertion sort 18. void MergeSort(vector&); // sort data using merge sort 19. void QuickSort(vector&); // sort data using quick sort 20. void HeapSort(vector&); // sort data using heap sort 21. private: 22. void QuickSortSubVector(vector&, int, int); // quick sort subvector 23. int Partition(vector&, int, int); // partition the subvector 24. void MergeSortSubVector(vector&, int, int); // merge sort subvector 25. void Merge(vector&, int, int, int, int); // merge two sorted subvector 26. void MaxHeapify(vector&, int); // make tree with given root be a max-heap 27. //if both right and left sub-tree are max-heap 28. void BuildMaxHeap(vector&); // make data become a max-heap 29. int heapSize; // heap size used in heap sort 30. 31. }; 32. 33. #endif sort_tool.h Line 17-20: sort function which will be called in main.cpp. Line 22: This function will be used in quick sort. It will sort sub vector with given lower and upper bound.
This function should be implemented to partition the sub vector and recursively call itself. Line 23: This function will be used in quick sort and should be implemented to partition the sub vector. Line 24: This function will be used in merge sort. It will sort sub vector with given lower and upper bound. This function should be implemented to call itself for splitting and merging the sub vector. Line 25: This function will be used in merge sort and should be implemented to merge two sorted sub vector. Line 26: This function will be used in heap sort and should be implemented to make the tree with given root be a max-heap if both of its right subtree and left subtree are
max-heap. Line 28: This function will be used in heap sort and should be implemented to make input data be a max-heap. sort_tool.cpp: the implementation of the SortTool Class Handout #3 September 19, 2019 Chien-Mo Li National Taiwan University Department of Electrical Engineering Algorithms, Fall 2019 1. // ************************************************************************** 2. // File [sort_tool.cpp] 3. // Author [Yu-Hao Ho] 4. // Synopsis [The implementation of the SortTool Class] 5. // Modify [2019/9/6 Cheng-Yun Hsieh] 6. // ************************************************************************** 7. 8. #include “sort_tool.h” 9. #include 10. 11. // Constructor 12. SortTool::SortTool() {} 13. 14. // Insertsion sort method 15. void SortTool::InsertionSort(vector& data) { 16. // Function : Insertion sort 17. // TODO : Please complete insertion sort code here 18. } 19. 20. // Quick sort method 21. void SortTool::QuickSort(vector& data){
22. QuickSortSubVector(data, 0, data.size() – 1); 23. } 24. // Sort subvector (Quick sort) 25. void SortTool::QuickSortSubVector(vector& data, int low, int high) { 26. // Function : Quick sort subvector 27. // TODO : Please complete QuickSortSubVector code here 28. // Hint : recursively call itself 29. // Partition function is needed 30. } 31. 32. int SortTool::Partition(vector& data, int low, int high) { 33. // Function : Partition the vector 34. // TODO : Please complete the function 35. // Hint : Textbook page 171 36. } 37. 38. // Merge sort method 39. void SortTool::MergeSort(vector& data){ 40. MergeSortSubVector(data, 0, data.size() – 1); 41. }
42. 43. // Sort subvector (Merge sort) 44. void SortTool::MergeSortSubVector(vector& data, int low, int high) { 45. // Function : Merge sort subvector 46. // TODO : Please complete MergeSortSubVector code here 47. // Hint : recursively call itself 48. // Merge function is needed 49. } 50. 51. // Merge 52. void SortTool::Merge(vector& data, int low, int middle1, int middle2, int high) { 53. // Function : Merge two sorted subvector 54. // TODO : Please complete the function 55. } 56. 57. // Heap sort method 58. void SortTool::HeapSort(vector& data) { 59. // Build Max-Heap 60. BuildMaxHeap(data); 61. // 1. Swap data[0] which is max value and data[i] so that the max value will be in correct location 62. // 2. Do max-heapify for data[0] 63. for (int i = data.size() – 1; i >= 1; i–) { 64. swap(data[0],data[i]); 65. heapSize–; 66. MaxHeapify(data,0); 67. } 68. } 69. 70. //Max heapify 71. void SortTool::MaxHeapify(vector& data, int root) { 72. // Function : Make tree with given root be a max-heap if both right and left sub-tree are max-heap 73. // TODO : Please complete max-heapify code here 74. } 75. 76. //Build max heap 77. void SortTool::BuildMaxHeap(vector& data) { 78. heapSize = data.size(); // initialize heap size 79. // Function : Make input data become a max-heap 80. // TODO : Please complete BuildMaxHeap code here 81. }
sort_tool.cpp Line 15-18: please complete the function of insertion sort here. Line 21-23: the function of quick sort will call function of Sorting sub-vector and give initial lower/upper bound. Line 25-30: please complete the function of sorting sub-vector using quick sort algorithm here. Line 32-36: please complete the function of partition here. Line 39-41: the function of merge sort will call function of Sorting sub-vector and give initial lower/upper bound. Line 44-49: please complete the function of sorting sub-vector using merge sort algorithm here. Line 52-55: please complete the function of merging two sorted sub-vector here. Line 58-68: the function of heap sort will build max-heap first.
And then, exchange data iteratively. Line 71-74: please complete the function of max-heapify which makes the tree with given root be a max-heap if its right and left sub-tree are both max-heap. Line 77-81: please complete the function of building max-heap with given input data. Requirements: 1. Please check the source code files under the src directory. You may need to complete the functions of class SortTool in sort_tool.cpp. You can also modify main.cpp and sort_tool.h if you think it is necessary. 2. Your source code must be written in C or C++.
The code must be executable on EDA union lab machines. 3. In your report, compare the running time of four versions of different input sizes. Please fill in the following table. Please use –O2 optimization and turn off all debugging message. Input size IS MS QS HS CPU time (s) Memory (KB) CPU time (s) Memory (KB) CPU time (s) Memory (KB) CPU time (s) Memory (KB) 4000.case2 4000.case3 4000.case1 16000.case2 16000.case3 16000.case1 32000.case2 32000.case3 32000.case1 1000000.case2 1000000.case3 1000000.case1
4. Draw figures to show the growth of running time as a function of input size and try to analyze the curve (as the following example, where each curve represents an algorithm.) You can skip the test case if the run time is more than 10 minutes. 5. Notice: You are not allowed to include the header or in STL! Compile We expected your code can compile and run in this way.
Type the following commands under _pa1 directory, make cd bin ./NTU_sort –[IS|MS|QS|HS] We provide the sample makefile, please modify into yours if needed. Control the stack size To prevent stack overflow cause by the recursion function calls, please set the stack size to 256MB using the following Linux comment: ulimit -s 262144
1. # CC and CFLAGS are varilables 2. CC = g++ 3. CFLAGS = -c 4. AR = ar 5. ARFLAGS = rcv 6. # -c option ask g++ to compile the source files, but do not link. 7. # -g option is for debugging version 8. # -O2 option is for optimized version 9. DBGFLAGS = -g -D_DEBUG_ON_ 10. OPTFLAGS = -O2 11. # make all 12. all: bin/NTU_sort 13. @echo -n “” 14. 15. # optimized version 16. bin/NTU_sort: sort_tool_opt.o main_opt.o lib 17. $(CC) $(OPTFLAGS) sort_tool_opt.o main_opt.o -ltm_usage -Llib -o bin/NTU_sort 18. main_opt.o: src/main.cpp lib/tm_usage.h 19. $(CC) $(CFLAGS) $< -Ilib -o $@ 20. sort_tool_opt.o: src/sort_tool.cpp src/sort_tool.h 21. $(CC) $(CFLAGS) $(OPTFLAGS) $< -o $@ 22. 23. # DEBUG Version 24. dbg: bin/NTU_sort_dbg 25. @echo -n “” 26.
27. bin/NTU_sort_dbg: sort_tool_dbg.o main_dbg.o lib 28. $(CC) $(DBGFLAGS) sort_tool_dbg.o main_dbg.o -ltm_usage -Llib -o bin/NTU_sort_dbg 29. main_dbg.o: src/main.cpp lib/tm_usage.h 30. $(CC) $(CFLAGS) $< -Ilib -o $@ 31. sort_tool_dbg.o: src/sort_tool.cpp src/sort_tool.h 32. $(CC) $(CFLAGS) $(DBGFLAGS) $< -o $@ 33. 34. lib: lib/libtm_usage.a 35. 36. lib/libtm_usage.a: tm_usage.o 37. $(AR) $(ARFLAGS) $@ $< 38. tm_usage.o: lib/tm_usage.cpp lib/tm_usage.h 39. $(CC) $(CFLAGS) $< 40. 41. # clean all the .o and executable files 42. clean: 43. rm -rf *.o lib/*.a bin/* makefile Line 38-39: compile the object file tm_usage.o from tm_usage.cpp and tm_usage.h Line 36-37: archive tm_usage.o into a static library file libtm_usage.a. Please note that library must start with lib and ends with .a. Line 37: this small library has only one objet file. In a big library, more than one objective files can be archived into a single lib*.a file like this ar rcv libx.a file1.o [file2.o …] Lines 12-21:
When we type ‘make’ without any option the makefile will do the first command (line.12 in this sample). Thus, we can compile the optimization version when we type ‘make’. This version invokes options ‘-O2’ for speed improvement. Also ‘_DEBUG_ON_’ is not defined to disable the printing of arrays in sort_tool.cpp. Lines 23-32: Compile the debug version when we type ‘make dbg’. This version invokes options ‘-g’ (for DDD debugger) and also ‘-D_DEBUG_ON_’ to enable the printing of arrays in sort_tool.cpp.
Lines 13,25: @echo –n “” will print out the message in “”. In this sample we print nothing. Notice: $< represent the first dependency. $@ represent the target itself. Example: a.o : b.cpp b.h $(CC) $(CFLAGS) $(DBGFLAGS) $< -o $@ $< = b.cpp $@ = a.o You can find some useful information here. https://mrbook.org/tutorials/make/ Validation: You can verify your answer very easily by comparing your output with case2 which is the sorted input. Or you can see the gnuplot and see if there is any dot that is not sorted in order. Also, you can use our result checker which is under utility directory to check whether your result is correct or not. To use this checker, simply type ./PA1_Result_Checker Please notice that it will not check whether the format of result file is correct or not.
You have to check the format by yourself if you modify the part of writing output file in main.cpp. Submission: Please submit a single *.tgz file to NTU COOL system before 10/13(Su) 13:00. Your submission must contain: 1. _pa1 directory contains your source code in src directory. By simply typing “make” can compile. 2. A report in the doc directory. _pa1_report.doc or pdf. 3. A README file that explains your files. 4. We will use our own test cases so do NOT include the input files. 5 In summary, you should at least have the following item in your *.tgz file. src/ lib/ bin/NTU_sort doc/_pa1_report.doc
makefile README The submission filename should be compressed in a single file _pa1.tgz. (e.g. b90901000_pa1.tgz). You can use the following command to compress a whole directory: tar zcvf .tgz