811312A Data Structures and Algorithms, Spring 2023, Programming Task 2 - Sorting
811312A Data Structures and Algorithms, Spring 2023, Programming Task 2 - Sorting
NOTE! When you submit:
· Zip all your files if necessary
· Do not include executable files
· Files should have file extension .c
· Use English in filenames, comments, and code
The mode of a sequence of numbers is the number that occurs most often in the sequence. For example, the mode of the sequence 3,1,2,5,3,3,4,1,4,4,3,5 is 3. In this task you will work on a program in C that finds the mode of a very large array of numbers.
In the findmode_2.c source code file, you will find implemented a program that finds mode of a randomly generated array that the user can specify the length of. The array will contain numbers from 0 to 999. Naturally, the program sorts the array first, so that it is quick to find the mode. It uses library quick sort for sorting the array.
Your tasks are the following.
1) Compile the code and run it. It will ask for you to input a size for the array. You
can run it with arrays up a length of 100 000 000. Observe the running time and see
that it is quite fast.
2) Study the code to see how it is implemented and to understand what it does. In the
main function, it allocates memory for a large array and initializes it with random numbers. The eventual size of the array is determined by your input, and it initializes it in a separate function. It then starts a clock and calls find_mode_quicksort() function. In that function, you can see that it uses library quicksort to sort the array and you will also find the logic for finding mode. Finally, it returns the mode to the main function where the clock is stopped, and mode and time for finding mode is reported to the user. See also that there are a lot of comments in the code.
3) 1 POINT! Implement recursive quick sort. As in the lecture slides, quicksort uses partition function and swap function. These have already been implemented for you. Your task is to implement the function recursive_quicksort(). The TODO is on line 48 and the function starts at line 49. The implementation is straight forward and follows almost exactly what is presented in the lecture slides. After you have implemented it, you can go to find_mode_quicksort() function and comment out the first quicksort call and uncomment the recursive_quicksort() function. Nothing else needs to be commented. Test your implementation by running the program. If you implement this successfully, you will get 1 point. Note the running time. How does it compare to the library quicksort?
4) 1 POINT! Next, implement counting sort. You can find the TODO on line 96 and the function starts on line 98. Here you will find step by step instructions for how to implement the function. It follows closely the algorithm presented in the lecture slides. Note that you do not have to implement the logic of finding mode here either,
but only the counting sort part. Once you have implemented the counting sort, you can go to the main function and uncomment the block that starts a clock, calls the counting sort function, stops the clock, and prints the result. You do not need to comment the call to the finde_mode_quicksort() function. Counting sort does not change the initial array, so it is safe to call that first, and then call quicksort. Quicksort sorts in place, so it changes the order of the elements in the initial array itself. Once you have counting sort implemented, compile and run the code again. When done successfully, you get and additional point. Compare the execution times of the two different ways to sort and then find mode. Can you see the difference? Why is there a difference?
NOTE 1! Counting sort needs an array B equal in size to array A. Reserve memory for it in the counting sort function in the same way memory is reserved for array A. NOTE 2! When you allocate memory, you always need to free memory in the end. This has already been implanted for you in the end of counting sort function.
5) 1 POINT! Finally, implement iterative quicksort. You will find the TODO on line 30 and the algorithm begins on line 32. Here you will also find further instructions as comments to help you. Use also the lecture notes from Moodle to learn how it should work. You may want to review the lecture video also. Once you have implemented this, you should go to function find_mode_quicksort() again and this time comment out the call to the recursive quicksort and uncomment the call to iterative quicksort. Again, compile and run your code. If completed successfully, you will get one more point. Note once again the running times.
5. 6) Once you are satisfied with your implementations, you can submit your solution. So, remember, 1 point for recursive quick sort, 1 pointe for counting sort, and 1 point for iterative quicksort. They must compile and function properly for you to get the points.
If you want to make sure that everything works correctly, you can “hard code” a smaller input array with numbers and include appropriate prints to debug your own solutions. Just remember, if you want to print contents of an array, DO NOT use large arrays. It is difficult to read, and printing takes a lot of time. Remove all additional “debugging code” before you submit your solution. Do not leave them into the solution because it makes code more difficult to read. Points will be deducted if you leave unnecessary code in the submission.
