Sorts testable on the AP Computer Science Exam

Part I. Researching and Analyzing

• Investigate each of the sorts listed up above and be prepared to describe each one. You should be able to state
  • How efficient the algorithm is.
  • How does the algorithm 'work'.
    • ie. How does the algorithm sort its elements?
  • How does the efficiency of the algorithm relate to the starting order of its elements?
    • If the algorithm's efficiency varies, is the variation great or neglible?

• Useful links to help you understand the sorting algorithms
• Sorting Algorithm demonstration
• Sorts demonstrations 2
• Animated Sorts Demonstration 3
• demo 4
• Sorting algorithms at Wikepedia

II. Improve the Sort Algorithm below

Create a class that uses the snippet of code below to sort an array a[].

First, determine which sort the algorithm below uses. Your job is to rewrite the code so that it implements a more efficient use of the of the sort you just identified. ie if you determine that code below is an implementation of MergeSort, rewrite the code to become a better implementation of MergeSort.

    
for(i = 0; i <a.length -1; i++)
   for(j=i+1;j<a.length;j++)
         if(a[i] > j[i])
           swap();//implementation of swap not shown

III. Presentation of Sorting Algorithm

Download Activity