| Insertion Sort |
10 points
Insertion sort is, we hope, relatively simple to understand and to code.
Think about how it works if, for example, you are playing cards and cards are being dealt to you one-by-one. You may try to put them in order - sort them - as they are given to you. Kings go to the right of queens, queens go to the right of jacks, and so on. In doing that ordering, you are performing an insertion sort. Each time a new element is inserted, it is inserted into the correct position.
You'll start with an unsorted list of words. You also set up a second list that will be the sorted version of the first list. You pull one word at a time from the unsorted list and find the right place to insert it into the sorted list. Once you've done this for every word in the unsorted list, the sorted list will be an ordered version of the first list, and you'll be done.
Once you have your insertion sort program working, study how long it takes (in milliseconds) to sort different numbers of words. Try sorting 100, 1000, 10,000 and 50,000 words.
Later you will compare the efficiency of insertion sort to the efficiency of merge sort.
You can download InsertionSort.java, InsertionSortTest.java and StopWatch.java to use as starting points in writing your program. Instructions for writing the two classes are given in the .java files. StopWatch.java is complete. The data file with the unsorted words is list.dat.