Home



2019/11 - DS&A #7: Selection Sort

Hey folks!

This time we'll be taking a look at the Selection Sort algorithm.

The selection sort searches for the lowest value for the remaining values in an array and inserts it into the leftmost unsorted index so far. Basically it starts on the left, grabs the lowest value every iteration, then shifts it over to the leftmost index of the unsorted side.

public class SelectionSort {
    
    int[] valuesToSort;
    
    public SelectionSort(int size) {
        valuesToSort = new int[size];
    }
    
    public static void main(String[] args) {
         
        SelectionSort selectionSort = new SelectionSort(args.length);
        
        for(int i = 0 ; i < args.length; i++) {
            selectionSort.valuesToSort[i] = Integer.valueOf(args[i]);
            System.out.print(selectionSort.valuesToSort[i]+",");
        }
        
        System.out.println("");
        System.out.println("***");
        selectionSort.sortArray() ;
            
        System.out.println("Sorted");
        for(int i = 0 ; i < selectionSort.valuesToSort.length; i++) {
            System.out.print(selectionSort.valuesToSort[i]+",");
        }
    }
   

 

The above is largely boilerplate and setup. Below is where all the actual logic takes place:

 

    public void sortArray() {
        
        int passesCompleted = 0;
        while(passesCompleted < valuesToSort.length ) {
            int lowestValueIndex= passesCompleted;
            
            for(int i = passesCompleted ; i < valuesToSort.length; i++) {
                if(valuesToSort[i] < valuesToSort[lowestValueIndex]) {
                    lowestValueIndex = i;
                }
                
            }    
            
            System.out.println("Pass: " + passesCompleted + "; switched " + valuesToSort[lowestValueIndex] + 
                    " with " + valuesToSort[passesCompleted]);
            
            switchIndices(passesCompleted, lowestValueIndex);
            passesCompleted++;
        }
            
    }
    
    public void switchIndices(int lowestValFoundIndex, int indexToBeSwitchedWith) {
        int previousIndexValue = valuesToSort[indexToBeSwitchedWith];
        int currentIndexValue = valuesToSort[lowestValFoundIndex];

        valuesToSort[lowestValFoundIndex] = previousIndexValue;
        valuesToSort[indexToBeSwitchedWith] = currentIndexValue;
        
    }

}

 

So how does the above work? We have two methods, one is a convenience method(switchIndices) to switch indexes(Yep. Indexes) and the other is the actual logic for selection sort. The sortArray method will find the lowest value and switch it with the first non-sorted value in the sorted array. "passesComplete" is never reduced, so we are always progressing through the array.

It's fairly straight-forward, so if it doesn't make sense now, just read over the code a few times and it'll click. 

 

Best of luck!

Marc