Sorting Theory

1. Read pages 455-465 and Sorting Comparisons
   1. What are the four factors that affect sorting routines?
   2. What does Big-O notation mean? Give an example.
   3. The two classes of sorting algorithms are O(n2) and O(n log n).
   4. Give an example of each.
   5. Compare the efficiency of each.
2. What is the basic algorithm for the merge sort? quick sort?
3. If you were given the code for either, would you recognize it?
4. How do worst case times compare?
5. Given a scenario, what type of sort would you use.

Sorting Practice

1. Create a program that creates a 1-D array of 100. Create methods to:
   • Randomly generate numbers between 1 and 100 for each element.
   • Printout the array in 10 columns
2. Create a separate class (SortLibrary) of sorting methods(selection, merge sort and quick sort). Each sort should have an integer array as a parameter.
3. Instantiating the SortLibrary object, for example:
4. int [] marks = new int[10];
5. SortLibrary s=new SortLibrary();
6. s.selectionSort(marks);
7. //assuming you have a method called selectionSort
8. Create the main to:
   • Call your random filling method.
   • Print out the unsorted array.
   • Call each method in turn and print out the results