Selection Sort

Selection sort is an intuitive sort that most of us use day to day. For example, want to sort a stack of papers? You find the paper that has a last name that starts with an A, and keep incrementing until it's sorted. In this case we're going to use java to sort an array of integers.The algorithm runs as follows

Before looking at the code below ask yourself: "How can I accomplish this on my own?"

Solution:

We first need a swap method that will be called once the min element has been found. Then we keep looking through the rest of the list always replacing the current number with the next smallest.

private void swap(int[] nums, int ind1, int ind2){
    int temp = nums[ind1];
    nums[ind1] = nums[ind2];
    nums[ind2] = temp;
}

private void selectionSort(int[] nums){
    // find the min and put it in the ith spot
    for(int i = 0; i<nums.length; i++){
        int minIndex = i;
        for(int m = i; m<nums.length; m++){
            if(nums[m] < nums[minIndex]){
                minIndex = m;
            }
        }
        swap(nums, i, minIndex);
    }

    // display the sorted list
    for (int num : nums) {
        System.out.print(num + " ");
    }
}

Selection sort is not an optimal sorting algorithm, but is one of the easiest to implement. Why is it not optimal? Well, the best sorting runtime is O(nlog(n)) and selection sort runs in O(n^2) since it must look N steps every Nth step (look at the code and find a for loop inside a for loop).