Page 3
Lab 8
Page 3
Insertion sort is the computer science equivalent of a typical card sorting algorithm: Insertion sort involves examining each item of the list in turn and placing that item in its proper place among the already sorted elements. Consider arranging a hand of cards as they are dealt to you: you might pick up each card one at a time and insert each card in its proper place amongst the cards in your hand. This is the basic algorithm of insertion sort, which is about the fastest algorithm available for sorting a bunch of data where most (but not all!) of the elements are already in order - an extremely important real-world case.
Computers, however, cannot just look at a list and judge automatically where the card belongs. To implement insertion sort in Java, you need to move each item in turn down the already sorted list, comparing it to each already sorted item. Once you find an item that is larger than the item in question or you reach the end of the list, insert the item at that position. Use the sorting demo program available by following this link to get a sense of how insertion sort moves each line down the already sorted list to find its place and then try to write an insertion sort of your own.
Extra Credit (20 percent): Replace the selection sort you implemented in the regular portion of this lab with insertion sort. Download another copy of SelectionSortTemplate.java, rename it InsertSortAlgorithm.java, change the class name to "InsertSortAlgorithm", and fill in the sort method with an insertion sort routine. Compile the Java files as you did for your selection sort implementation. Then run your applet by using an HTML file which includes the tag
<applet code=SortItem.class width=100 height=100> <Param name="alg" value="InsertSort"> </applet>Note: Do not change your file SelectionSortAlgorithm.java containing your implementation of selection sort.
If you've played around with the various sorts in the demo program, you've probably noticed that some sorts take longer than others to complete. Speed is a very important factor in sorting and in computer science in general. In fact, the sorts you have written today are generally not used for sorting significant amounts of numbers because they are too slow. Instead, a recursive sort like merge sort or quick sort, which are less intuitive but far faster, is usually used.
To figure out the speed of a sort, look at the number of compares and swaps necessary to complete the sort. In the case of selection sort, the program will compare each item with half of the other items, on average (the first item gets compared with all other items whereas the last time does not have to be compared to anything). Selection sort, however, requires only as many swaps as it does items, for it swaps only once during each pass. Therefore, the sorting time for one selection sort is (N^2)/2 + N where N equals the number of lines sorted. Notice the (N^2)/2 portion of the equation, for this portion will quickly dominate as N increases. Some more complicated sorts, like quicksort, have a largest factor of only Nlog(N), which is quickly dwarfed by the (N^2)/2 in selection sort.
Extra credit (a few percent): Try to figure out the speed of insertion sort and include an explanation of your result in some text in the the HTML file from which you run your insertion sort.
QuickSort is perhaps the most used sort because it is so efficient; at any rate, it is certainly one of the most-studied by computer scientists. In this recursive algorithm, the array is first "partitioned" into two segments with a "pivot" element in between. Elements to the left of the pivot are all less than or equal to it; elements to its right are all greater. The pivot element itself is in its final position. Once the array is partitioned in this way, QuickSort calls itself on the two segments to sort them.
Try running QuickSort (by following this link again and you will soon see that QuickSort handily beats each of the others. Quick sort relies on recursion, a powerful tool in computer science and the subject of the next lab. (Caveat: regular QuickSort has one major weakness, in that it performs worse than either selection sort or insertion sort on data which is already almost in order. Much study has been devoted to figuring out ways to make QuickSort work well on this type of data, too.)
| PREVIOUS | 1 | 2 | 3 | 4 | NEXT |