# Selection sorting an int array

Posted on

Problem

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;

}

}


Solution

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


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.

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

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(n2)$O\left({n}^{2}\right)$$O(n^2)$