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