Project Objective: in completing this project, you will Enhance your understanding of sorting algorithms Understand the effect on Big O notation using different sorting algorithms and data Enhance your understanding of software development on a team and the use of git for managing your source code. Practice designing and creating an experiment The team will need to implement the following sorting algorithms: (1) Two O(n2 ) sorts from the lectures: bubble sort, selection sort, or insertion sort (2) Two O(n log n) sorts from the lectures: heap sort, quick sort, merge sort, or radix sort (3) Another sorting algorithm that is not in the lists above (cannot be slower than O(n log n)), you can search the Internet or improve some O(n log n) or faster algorithm. You may copy the source code for the algorithms from the Internet, but you need to cite the website in your source code and written report and verify the algorithms. The team will design an experiment to answer the following questions about the sorting algorithms: 1. How do O(n2 ) and O(n log n) sorts compare in actual run times? You will need to implement an effective and correct way to compare the run times of various sorting algorithms a. Populate a large array with random numbers to effectively compare sorting algorithms. Your array must have at least 1000 element to adequately test the differences between the fast and slow algorithms. A larger array may give you better results. b. Capture times for unsorted array data. Please verify that the data you are using for each sort is unsorted by printing the first 5 elements in the array before each sort. 2. How does the order of the data prior to sorting affect the run time of any given sorting algorithm? You will need to measure run time of the sorts when the data is already sorted. a. Use a large, sorted array to effectively compare sorting algorithms. Your array must have at least 1000 element to adequately test the differences between the fast and slow algorithms. A larger array may give you better results. b. Capture times for an already sorted data. Please verify that the data you are using for each sort is sorted by printing the first 5 elements in the array before each sort. 2 3. You may try different array sizes and multiple trials to obtain a better comparison. Use your creativity and curiosity in implementing your experiment. Team Set Up 1) Final team assignments will be made by me. I will give you a chance to meet briefly in class to exchange information and create GitHub repository. Come up with a team name for reference (add semester and year to make it unique if needed). 2) Follow the link in Blackboard to accept the assignment in GitHub classroom and join your team. The first team member will create the team and all others will join the team. 3) All teams will be presenting in the classroom during class on November 30th and December 2nd. You are required to attend class all days even if your team is not presenting. Team Tips You can do most of your work asynchronously. I recommend meeting as a team as soon as possible to determine your communication channel, assign tasks, and establish milestones and deadlines. Example milestones might include the following: Complete sorts. Complete driver. Run experiments. Create graph/chart of results. Create experiment and new algorithm report. Create presentation slides. Practice presentation. Teamwork is 20% of your grade for this project, so each person needs to contribute equally to the team. Each team member should use git to push changes to the repository and pull changes from the repository as you are working on the project. You may distribute the work how you want, but I am providing you this list to give you some ideas. Please adjust as needed. Team member 1: Implement two O(n2 ) sorts and the new O(n log n) sort. Carefully test your algorithm on your own BEFORE integrating it into the experiment. Team member 2: Implement two O(n log n) sorts. Carefully test your algorithm on your own BEFORE integrating it into the experiment. Team member 3: Start the experiment driver program that creates an array of random numbers (unsorted) and is ready to call all the sorts when the sorts are ready. Implement timing code for timing the arrays. Implement code to copy the original array to another array before you sort (so you can run each sort on the same unsorted data). All team members. Integrate all code to work together (call sorts for unsorted and sorted data with run times). Run experiment and collect data. All team members: project report and presentation slides. 3 Due Dates and Honor This project will be due by the beginning of the class on due date for all groups regardless of presentation date. Remember, you may copy sort source code from other sources, but NOT the experiment driver. Also, provide links in your source code and reports for any source code you copied from the Internet. Artifacts of the project Please submit by the due date the following to your Blackboard text submission. Only one member of your team needs to submit the artifacts. Please create Google drive folder and place the required documents in the folder. The Google drive folder containing report and slides must be shared with me for editing. 1) Project Report (shared Google document) with the following sections: a) Experiment Report page description (including figures) that describes the results of your experiment. This section should include the following sub sections: Introduction, Methods, Results (include chart or graph), and Analysis/Discussion. A table or graph comparing results of each algorithm sorted and each algorithm unsorted is required. b) New Algorithm Description - page description of the new sorting algorithm, including a description of the algorithm and a simple example to help explain how it works (including data values) c) Time Log -a chart showing team members, tasks, and approximate time for each task. Include all task for the project such as coding, running experiments, and writing documents. (See example below) Team Member(s) Task Approximate Time Michelle Talley Implemented bubble sort and selection sort 1 hour 2) Group Presentation - A shared Google Slide that is your group presentation. 3) Team member evaluation - You will be required to evaluate yourself and all other team members via the Google Form provided in Blackboard. 4) Source Code - A URL to your GitHub shared repository including all your source code. Your source code must be checked into your team GitHub repository by the beginning of class on the due date. 5) Output of experiment(s) - Please capture enough of the output of your main driver to demonstrate that it runs properly and check it into GitHub with your source code. You will also give a 5-10-minute oral group presentation about the results of your experiment and a description of your new algorithm. Your presentation should focus on 1) which sorts you compared and the results of your experiment (comparison graph/chart should be included). 2) description of your new algorithm. Other things to present are how you selected your array size, challenges you faced during the project, and anything else you want to share. You can reuse material from your experiment report and your new algorithm description report. 4 Everyone on the team will need to speak about the project. You will be graded individually on how well you present your portion of the project. Grading and Rubrics Your grade is based on the team's final product, so every team member is responsible for evaluating the final product against the requirements and the rubrics. You will also be graded individually as well. This project is 10% of your grade for the course and worth 100 points. The points are allocated as follows: Artifact % of Grade Source code 30% Written Reports 30% Teamwork (Team Report + Team Evaluation) 20% Presentation 20% Source Code Rubric Exceptional (100%~90%) Good (89%~70%) Basic (70%~50%) Unsatisfactory (49%~0%) Correctness (60 pts) The program works and meets all of the specifications. The program works and produces the closeto-correct results and displays them correctly. The program works but produces incorrect results.. The program does not work. Readability (20 pts) The code is exceptionally well organized and very easy to follow. The code is fairly easy to read. The code is readable only by someone who knows the intent of the program. The code is poorly organized and very difficult to read. Documentation (20 pts) The documentation is well written and clearly explains what the code is accomplishing and how. The documentation consists of embedded comment and some simple header documentation that is somewhat useful in understanding the code. The documentation is simply comments embedded in the code with some simple header comments separating routines. The documentation is simply comments embedded in the code and does not help the reader understand the code. Programs that do not compile and execute will get 0 points. 5 Written Report Rubric Exceptional (100%~90%) Good (89%~70%) Basic (70%~50%) Unsatisfactory (49%~0%) Writing (50 pts) Writing is clear and focused Relevant, quality details give the reader important information Offers compelling conclusions and helps the reader develop insight into the topic Ideas are well organized and help the reader move along Key points are presented Coherent conclusions are offered, but does not demonstrate indepth understanding Some of the ideas are presented well Offers plausible conclusion(s) Poorly written Sequencing and pace of topics seems random Doesn't lead to clear conclusions Analysis (50 pts) Algorithms were appropriately selected, described, and classified by complexity. Data presentation (charts, tables, graphs) is easily understood and interpreted. Algorithms were appropriately selected, described, and classified by complexity. Data presentation (charts, tables, graphs) is usually easily understood and interpreted. Most algorithms were appropriately selected, described, and classified by complexity. Data presentation (charts, tables, graphs) is somewhat easy to understand. Some algorithms were appropriately selected, described, and classified by complexity. Data presentation (charts, tables, graphs) is unclear. Teamwork Rubric Exceptional (100%~90%) Good (89%~70%) Basic (70%~60%) Unsatisfactory (59%~0%) Teamwork (100 pts) Contributed to the team by accomplishing significant tasks and investing significant time. Contributed to the team at an acceptable level by accomplishing sufficient tasks and investing adequate time. Contributed to the team at a minimal level but could have contributed more by accomplishing more tasks and by investing more time. Did not contribute to the team in any significant way. 6 Hint: Each of your sorting algorithms should be in its own function with the array passed as a parameter. You need to compare sorting algorithms with the same data. Your array size needs to be large enough to show the differences in the algorithms. The timer should only time the sorting, not any of the array management. You need to explore how to use time in a C++ program. Measuring time: Option 1 This article describes how to measure in microseconds https://www.geeksforgeeks.org/measure-execution-time-function-cpp/ Measuring Time: Option 2 This option measures in seconds, which requires all of your sorts to run for at least a second. #include #include using namespace std; 7 int main() { time_t time0; // create timers. time_t time1; time(&time0); // get current time. for (int i = 0; i < 2000; i++) { std::cout << "i: " << i << ' '; } // make computer to do something so time would pass.- your sort goes here! time(&time1); // get current time after time pass. std::cout << "The time1 is: " << time1 << ' '; std::cout << "The time0 is: " << time0 << ' ';