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;
}

• tim: 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).

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