Selection sorting an int array

Question

I'd like to improve this selection sort code

package com.arun.sort;

import java.util.Arrays;

public class SelectionSort {

    public static void main(String[] args) {

        int[] arr = { 5, 2, 131, 13, 11, 1 };

        SelectionSort sort = new SelectionSort();

        sort.selectionSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    public int[] selectionSort(int[] a) {

        int min;
        for (int out = 0; out < a.length - 1; out++) {
            min = out;
            for (int in = out + 1; in < a.length; in++) {
                if (a[in] < a[min]) {
                    min = in;

                }
            }
            int tempValue = a[out];
            a[out] = a[min];
            a[min] = tempValue;

        }

        return a;

    }

}

Answer 1

Few points.

There is no need to create a object for SelectionSort. Declare it static.

selectionSort(arr);

Your variable names should be made better. Its not recommended to use 'out' as variable, or int a[]. You can use int inputArr[] as thats more descriptive. Imagine someone is reading your code then if you make their life easy by making your code more descriptive then job is done faster.

You can create a seperate swap method. This will structure your code properly. You can reuse the swap method for other sorting methods too.

private void swap(int out, int min)
{
int temp = a[out];
a[out] = a[min];
a[min] = temp;
}

Answer 2

I think the selectionSort method better be a static method because the method does not require any internal state within sort object, which is SelectionSort class.

Answer 3

Isn't the point of selection sort to just swap the smallest? Eg. for the array [6, 2, 7, 5, 3, 1, 2, 9, 8] With your latest edit you would have 36 comparisons and 16 swaps,

public static void selectionSort(int[] arr) {
    int size = arr.length;
    for (int i = 0; i < size - 1; i++) {
        int iMin = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[iMin]) {
                swap(arr, j, iMin);
            }
        }
    }
}

but with

for(int i = 0; i < input.length; i++){
        iMin = i;
        for(int j = i+1; j<input.length; j++ ){
            comparisons++;
            if(input[j] < input[iMin]){
                iMin = j;
            }
        }

        swap(input,i,iMin);
        swaps++;

    }

would yield 36 comparisons and 9 swaps

Answer 4

I've modified my code based on the answers.

SelectionSort.java

import java.util.Arrays;

public class SelectionSort {

    public static void main(String[] args) {

        int[] inputArray = { 7, 2, 6, 4, 9, 11, 19, 13 };
        System.out.println("Before sorting " + Arrays.toString(inputArray));
        selectionSort(inputArray);
        System.out.println("After sorting " + Arrays.toString(inputArray));

    }

    public static void selectionSort(int[] arr) {
        int size = arr.length;
        for (int i = 0; i < size - 1; i++) {
            int iMin = i;
            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[iMin]) {
                    swap(arr, j, iMin);
                }
            }
        }
    }

    public static void swap(int[] arr, int j, int iMin) {
        int temp = arr[j];
        arr[j] = arr[iMin];
        arr[iMin] = temp;
    }

}

Time complexity: \$O(n^2)\$