Continue to read and experiment with most of the exercises in the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne. I am currently reading chapter 2.1 Elementary Sorts. I just finished the section that deals with Selection sort. The subject matter is well described and a set of methods (with possible some exceptions) will be used to implement all the sorting algorithms in this chapter. That is quite nice because it emphasizes on the concept of hiding data and the actual algorithm from clients.
The following methods are common to all sorting algorithms described in the second chapter:
| Method | Description |
| sort() | Sort the elements of the array. |
| less() | Checks if an element is less than other. |
| exch() | Exchanges to elements in the array. |
| show() | Display all the elements in the array / collection. |
| isSorted() | Test is the elements in the array are sorted. |
The Selection sorting algorithm is as simple as it gets. The array is divided into sorted and unsorted. Initially all the array is unsorted. The algorithm traverses the unsorted section looking for the smallest value. After the entire traversal it exchanges / swaps the first unsorted element with the minimum element. The border between sorted and unsorted is moved down one position. The process repeats until the sorted area includes all elements in the array. The algorithm has O(n**2). It is quite slow compared to others.
Following is the output (with the show() method commented out) of the Selection sort algorithm captured from the console of the Eclipse IDE:
readStrings <<< al.size: 4411
main <<< elapsed: 390 ms
In this case I am using a random text file with 4,411 words. The average run is about 390 ms.
The Java code for the test and the method that reads words into the array to be sorted follows:
package john.canessa.sort;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class Sort {
/*
* read strings from the specified file
*/
static String[] readStrings(String fileName) throws FileNotFoundException {
File file = new File(fileName);
if ((!file.exists()) || (file.isDirectory())) {
throw new FileNotFoundException(“readStrings <<< fileName ==>” + fileName + “fileName”);
}
Scanner sc = new Scanner(file);
ArrayList<String> al = new ArrayList<String>();
while (sc.hasNext()) {
al.add(sc.next().toLowerCase());
}
sc.close();
System.out.println(“readStrings <<< al.size: ” + al.size());
String[] a = new String[al.size()];
return a = al.toArray(a);
}
/*
* test
*/
public static void main(String[] args) throws Exception {
final String fileName = “c:\\temp\\document.txt”;
boolean done = false;
int i = 0;
do {
switch (i++) {
case 0:
// **** read an array of strings ****
String[] a = readStrings(fileName);
// **** allocate the Selection class ****
Selection selection = new Selection();
// **** sort the array ****
long begin = System.currentTimeMillis();
selection.sort(a);
long end = System.currentTimeMillis();
// **** determine if the array is not sorted ****
if (!selection.isSorted(a)) {
System.out.println(“main <<< array NOT sorted”);
throw new Exception(“array not sorted”);
}
// **** show the array ****
// selection.show(a);
System.out.println(“main <<< elapsed: ” + (end – begin) + ” ms”);
break;
default:
done = true;
break;
}
} while(!done);
}
}
Following is the Java code implementing the Selection sort algorithm:
package john.canessa.sort;
public class Selection {
/*
* constructor
*/
public Selection() {
}
/*
* sort array
*/
public void sort(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
if (less(a[j], a[i])) {
exch(a, i, j);
}
}
}
}
/*
* exchange the elements in array
*/
private void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/*
* show the array
*/
public void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.println(“show <<< a[” + i + “] ==>” + a[i] + “<==”);
}
}
/*
*
*/
public boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/*
* determine if the array is sorted or not
*/
public boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i – 1])) {
return false;
}
}
return true;
}
/*
* test
*/
public static void main(String[] args) {
Selection selection = new Selection();
String[] a = new String[2];
a[1] = “one”;
a[0] = “two”;
if (!selection.isSorted(a)) {
System.out.println(“main <<< not sorted”);
} else {
System.out.println(“main <<< sorted”);
}
}
}
The authors of the book do a great job in describing this algorithm.
If you have a copy of the book and are looking at the web site, you will notice that I am not using all the libraries provided. For simplicity I am just using Java classes. Also, I am not building a JAR for testing. Testing within the Eclipse IDE is faster, so the name of the file holding the data is specified as a constant (final String) inside the source code.
If you have comments or questions please let me know.
John
john.canessa@gmail.com