Lab 7
Page 4

Selection Sort

Selection Sort

In class, we discussed several algorithms for sorting, including insertion 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.

See the program work

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.

Bubble Sort implemented in Java

As an example, we have implemented a sorting algorithm called bubble sort for you. 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. The inner loop of bubble sort runs down the list from top to bottom comparing adjacent items; at any time that a pair of adjacent items is out of sorted order, the pair is exchanged. The first pass through the list "bubbles" the maximum item to the bottom, the second pass "bubbles" the second largest item to its proper position, and each successive pass bubbles the next largest item to its proper position. Once (length-1) passes have been made, the list is sorted. Have a look at this file for the java code.

Implementing Selection Sort in Java: Your Assignment

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:

SortAlgorithm.java

SortItem.java

SelectionSortTemplate.java

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 by editing SelectionSortAlgorithm.java (with Textpad). The a[] parameter of the sort method is the array of integers that you need to sort. Recall that comments are a part of the code not looked at by the compiler when generating the .class file. We have already put in comments (with //) to describe most of what you will have to do exactly in the places you need to do it. 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:

• Before you even start typing, make sure you have the algorithm down pat. Write some pseudo-code for the algorithm first. Then refine it so it is close to Java syntax. Then translate it into Java. Now you are just about ready to start coding.
• To get used to arrays, write a bit of code to swap the first and last elements of the array and return. Compile and run your applet.
• Write a for loop that walks through the list once, remembering the index of the largest encountered array item, and then swaps this largest item with the last item in the list. Compile and run your applet.
• Write code that keeps looping through, finding the next longest item and moving it to the next spot in the list, bottum-up, until all the items are sorted. Compile and run your applet.
• Pat yourself on the back. You're done!