Selection Sort algorithm in Java

Question

I'm relatively young in Java, and am familiar with only the basics of the language, yet. I've started studying data structures, and I've made an attempt to create a solution for the selection sort algorithm. After many attempts with errors and exceptions, I've managed to come up with what looks like a working solution.

I realize that having the swap implemented as a separate method call in the sort function causes some additional overhead, instead of having the swap directly in the loop. But this version helps me follow along the logic clearly, as I'm not that experienced yet.

 package Chap_3; /** * Created by user1 on 8/7/15. * my selection sort version */ class MySelSort { //reference to array private int[] arr; //num. of elements private int n; //constructor public MySelSort(int max) { //create array with size arr = new int[max]; //set current items to 0 n = 0; } //-------------------------------------------------- //insert() public void insert(int key) { //insert key to relevant place in array arr[n] = key; //increase size of array n++; } //-------------------------------------------------- //display() public void display() { System.out.println("The items in the array are: "); for(int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } System.out.println(); } //------------------------------------------------- //sort() using selection sort public void selSort() { int in, out; //int min = 0; for(out = 0; out < n - 1; out++) { int min = out; for(in = out+1; in < n; in++) { if(arr[min] > arr[in]) { min = in; } } if(arr[out] > arr[min]) { swap(out, min); } } } //------------------------------------------------ //swap() public void swap(int one, int two) { int temp = arr[one]; arr[one] = arr[two]; arr[two] = temp; } } public class MySelSortApp { public static void main(String[] args) { //create array MySelSort sel = new MySelSort(100); //insert 8 items sel.insert(40); sel.insert(60); sel.insert(90); sel.insert(10); sel.insert(80); sel.insert(70); sel.insert(20); sel.insert(50); //display items sel.display(); //sort items sel.selSort(); //display again sel.display(); } } 

Answer 1

Your logic seems fine to me, but bear in mind I'm not very experienced in that either, so perhaps someone more experienced with algorithms will find some ways to improve.

---

Documentation & Naming

It's clear from your code that your intention is to have well-documented code (with is a great habit). It's the first thing that I noticed looking at your code so that's why I am mentioning it specifically.

It feels a bit like your documentation is overcompensating for things that could be just named a bit more clearly. For example:

/** * Created by user1 on 8/7/15. * my selection sort version */ class MySelSort { //reference to array private int[] arr; //num. of elements private int n; 

I think something like this would be better:

class SelectionSort { private int[] arrayToBeSorted; private int numberOfElements; 

It's a bit more wordy, but completely unambiguous on the other hand. I would also encourage to use Javadoc.

While something like this is OK:

//constructor public MySelSort(int max) { //create array with size arr = new int[max]; //set current items to 0 n = 0; } 

This would be more like what you see in bigger Java programs:

/** * Constructor. * <p> * Creates an array of integers with a maximum size. * The beginning index of the array is initialized to 0. * * @param maxSize The maximum size of the array, not null */ public SelectionSort(int maxSize) { arrayToBeSorted = new int[maxSize]; numberOfElements = 0; } 

---

This method's parameter naming is misleading:

//-------------------------------------------------- //insert() public void insert(int key) { //insert key to relevant place in array arr[n] = key; //increase size of array n++; } 

What you call the key is actually rather the value to be inserted at the current key (or index). This would be a bit easier to spot with better naming. Going back to the top, we could name n to elementNumber instead of numberOfElements (which I first named only accordingly to your comment, which again was a bit misleading).

/** * Inserts a value at a given key in the array. * * @param value The value to be inserted, not null */ public void insert(int value) { arrayToBeSorted[elementNumber] = value; elementNumber++; } 

---

And so on with documentation and naming. When you get to the end, you get a much clearer picture of what is happening, with no comments needed at all in your main class:

public class SelectionSortApp { public static void main(String[] args) { SelectionSort arrayToBeSorted = new SelectionSort(100); arrayToBeSorted.insert(40); arrayToBeSorted.insert(60); // ... System.out.println("Prior to sorting..."); arrayToBeSorted.display(); arrayToBeSorted.selSort(); System.out.println("After sorting..."); arrayToBeSorted.display(); } } 

Answer 2

 sel.insert(40); sel.insert(60); sel.insert(90); sel.insert(10); sel.insert(80); sel.insert(70); sel.insert(20); sel.insert(50); 

Don't repeat yourself, in pseudocode:

for item in [10, 30 .. ]: sel.insert(item)