Goals: Review and practice the linked list concept.
Part 1 Describe your sort algorithm in pseudo code.
Part 2 Answer the following questions (See below)
1. Which sorting method did you choose?
2. The sorts we discussed were selection, insertion, bubble, merge, quick, and shell. In about a paragraph, discuss why the ones that you didnt choose would have been less appropriate?
3. How much slower would you expect bubble sort of 10,000 elements to be than merge sort?
4. What is the fastest algorithm for finding the kth largest element of N numbers?
5. What is the primary disadvantage of Quick Sort? How could this disadvantage be eliminated?
6. What is an advantage of bubble sort over selection sort? What is an advantage of selection sort over bubble sort?
7. Why is a hybrid algorithm combining insertion sort with quick sort often faster than solely using quick sort?
8. Describe how radix sort of integers can be implemented to require only twice memory, rather than ten times memory.
9. State one or two problems that you can think of that are associated with sorting a linked list as compared with arrays?
10. Give one or two advantages that the linked list implementation has over arrays.
Part 3 Implement the program. Turn in the working program by e-mailing your zipped lab3 folder to harveyd@sou.edu. Include files containing the typed answers to the part 1 questions, the pseudo-code, and the extra analysis (if this is the project that your chose to do the analysis). Make sure to name your files so I can easily recognize them.
Hints and Instructions
1) Implement your employee list program using a linked list instead of an array. We will also add a sort option. Your menu will look something like the following:
Employee Maintenance
1) Add Employee
2) Remove Employee
3) Display Employee
4) Display Employee List
5) Reset List
6) Create Initial List
7) Sort Employee List
8) Help
9) Quit
Please Select:
2) The sort option will put the employee list in order of ascending item numbers. Pick the sort that you think is most efficient for this project, but do not copy to an array and sort the array. The lab requirement is to sort the linked list directly, without using arrays.
Extra Analysis
Do this part if this to be your longer project or if you are a graduate student. Otherwise this will be for extra credit.
Implement the employee list using an unordered array. Your implementation should include the 'Create' and the 'Sort' options. Time how long it takes to sort using linked list and array implementations.
When comparing algorithms, normally large data set sizes are needed. Also, picking array sizes that vary exponentially is useful to capture the attributes of the algorithms. For example, picking array sizes as 100000, 200000, 400000, 800000, etc. would be appropriate (Assuming that C allows array sizes that large).
You can use the C clock() for timing purposes, including
clock_t start = clock();
/* do some cool stuff here */
clock_t end = clock();
double time = 1.0*(end - start)/CLOCKS_PER_SEC;
printf("The algorithm took %lf timen", time);
fflush(stdout);
Write a one or two page paper that analyzes the linked list sort as compared to the unordered array implementation and draw some conclusions.