7
\$\begingroup\$

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();

    }
}
\$\endgroup\$
  • \$\begingroup\$ You might have an issue if you insert more items than you have allocated room for (I.e. More than max item). So I would make a check to verify that this does not happen. In addition I'm sure you are aware that there are other structures which could have handled the list for you, but it it is good training to do it from scratch a few times in the beginning. Code looks tidy in other aspects. Do remove void comments like // insert() \$\endgroup\$ – holroy Aug 8 '15 at 0:27
7
\$\begingroup\$

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();

    }
}
\$\endgroup\$
2
\$\begingroup\$
    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)
\$\endgroup\$
  • \$\begingroup\$ If only it wasn't decidedly uglier in Java. \$\endgroup\$ – greybeard Aug 26 '17 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.