Page 2
Lab 8
Page 2
In class, we discussed several algorithms for sorting, including bubble sort and selection sort.
Selection sort is most commonly used in alphabetizing lists -- you have most likely alphabetized a list at some point by scanning through it repeatedly, finding the item that goes next in order on each scan. Selection sort on a computer is no different. To sort a list into increasing order, go through the list and find the largest item. Move that item to the end of the list by exchanging it with the item originally at the end. Go through the list again and find the largest item except for the one already found. Place it in the next slot by exchanging it with the item currently in that slot. Keep repeating this procedure, once for each item in the list, and you will end up with a sorted list. You will note that the principle behind bubble sort and selection sort is the same: repeatedly find the next element in sorted order, starting with the largest, and put it where it belongs. The main difference is that bubble sort does this by repeatedly exchanging neighboring items while moving down the list and selection sort does it by scanning down the list to find the next largest item and then putting that item where it belongs.
Follow this link to see visualizations of four different sorting algorithms, including a version of the program you are about to write. The Selection sort program "sweeps" through the part of the list which is not yet in order, and finds the longest line in that part of the list; it then places that line in the next position in the sorted part of the list. It does this until there is no line which has not been put in its place. Click on the box and watch it again, as many times as you like.
In order to implement this algorithm, you need to know a couple more pieces of Java, the first of which is how to use arrays. In Java, when an argument of a function is an array, it is declared as something like int a[] (which would make a an array of integer numbers) or MyLine m[] (which would make m an array of objects of the class MyLine). To refer to the first element in the array, you write a[0]; so to set the first element of the array a[] to have the integer value 9, you would say a[0] = 9. The nth element is accessed as a[n-1] because the counting starts at 0.
In Java, not only can you reference an item in an array, you can also determine the length of an array through its length field. For example, the following two lines of code print out the last item in the array named list[]. (Again, since the first item in the array has an index of 0, the last element in the array has an index one less than the array's length).
int list[];
....
last_index = list.length - 1;
System.out.println (list[last_index]);
The next bit of Java that you will find helpful is a for loop, which you have seen and used in class. In Java (just as in C) the syntax of the for loop is divided into four sections. The initialization section specifies a bit of code to execute before entering the rest of the loop. The condition section is a condition which is checked after each time the code in the body is executed (and, in fact, after the statement in the increment section is executed); if the condition statement is true, the code in the body is repeated once more; otherwise, the for loop stops. The increment section is a statement that is executed each time through the loop, after the code in the body has been executed. The body is the collection of statements which is executed each time the loop runs. The form of the for loop looks like:
for (initialization; condition; increment)
{
body
}
So a loop that prints out each element of an array called a
would look like this:
int a[];
int i;
....
for (i = 0; i < a.length; i = i + 1)
{
System.out.println(a[i]);
}
As an example, we have implemented bubble sort for you. Have a look at this file for the java code. You will see that its author used a trick in the outer for loop: i is both decremented and compared to 0 in the condition part, so the increment part is empty. You need not employ such trickery in your program!
Now you have the tools to implement the selection sort algorithm. You will actually be implementing your selection sort within a larger program that takes care of translating your integer sorting program into a "line" sorting program. You will need to download the following files onto your local computer:
All you need to do to complete your sort is to change the name of SelectionSortTemplate.java to SelectionSortAlgorithm.java and then fill in the sort method of the SelectionSortAlgorithm class. The a[] parameter of the sort method is the array of integers that you need to sort. Once you have completed enough of your sort to test, you will need to compile all of the above files and create an html file with the following applet tag:
<applet code=SortItem.class width=100 height=100> <Param name="alg" value="SelectionSort"> </applet>To implement your sorting algorithm, we suggest these steps:
| PREVIOUS | 1 | 2 | 3 | 4 | NEXT |