0
\$\begingroup\$

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;

    }

}
\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think he got the idea for "out" in this question. But your right, out is not a good variable name (could very well be short for output). Same with "in" (sounds too much like input). and generally, I really like extracting methods. But if this code is performance-critical, this might not be too good an idea (in that case, a comment might be better). \$\endgroup\$
    – tim
    Jul 29 '14 at 9:16
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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)\$

\$\endgroup\$

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.