CSCI 385 Fall 2015
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

Homework 4

Details

Finish optimizing either Quicksort or Mergesort. Grades for this assignment will be based mainly on performance improvements compared to the original algorithm. I will also compare your performance with that of qsort, your classmates, and (if I get around to it) my best algorithms.

To get an 'A', you want to be the fastest algorithm. To get a 'B', you want to have made significant improvements and it should be obvious that you put effort into the improvements. (For instance, your attempts should not be limited to changing just 2 or 3 lines of code and/or implementing just one improvement.)

If you choose mergesort, you will likely not beat the best versions of quicksort. However, if you make significant enough improvements to it, that will be considered good enough (since you are limited by the algorithm). Hint: There is an improvement that can make it about twice as fast by reducing the amount of copying of arrays that is done.

Zip up the Sorting directory and submit it using handin. You can use the 385SRQ assignment.