Selection Sort Implementation in Java Example

Selection Sort Implementation in Java Example:

 

Psudeocode for selection sort:

1. Take an array with N elements (say new long[]{3,3009, 76,172,271,2})
2. Outer for loop to iterate all the elements in the array. (index starts from 0)
   1. Create a currentMinimum variable with index value(initially 0)
   2. Create a nested for loop to iterate from innerIndex(index+1) (because till index it is already sorted, initially it is 0, means not sorted)
      1. 2.2.1 if array[currentMinimum] > array[innerIndex] then assign currentMinimum = innerIndex;
   3. 2.3. Outside of nested for loop, Perform swapping, here with temp variable for easiness,
      1. Create a temp variable and assign the value of array[currentMinimum]
      2. Now Move the array[innerIndex] to array[currentMinimum]
      3. And assign array[currentMinimum] to temp.
3. Once the above steps completed for all the index values of array, we get a selection sorted array :).

 

 

Selection Sort Big O Notation / Time complexity:

O(n^2) O[n-square]

 

 

Selection Sort Java Implementation Program:

I have provided the inline comments each and every line/logics of the below program. Feel free to comment if still required any helps.

[java]
package in.javadomain;

import java.util.Arrays;

public class SelectionSort {

public static void main(String[] args) {
long[] inputArray = new long[] { 3, 3009, 76, 172, 271, 2 };
System.out.println(“Before Sorting::: “);
System.out.println(Arrays.toString(inputArray));
long[] sortedElements = getSelectionSortedArray(inputArray);
System.out.println(“After Sorting::: “);
System.out.println(Arrays.toString(sortedElements));

}

private static long[] getSelectionSortedArray(long[] input) {
int currentMin = 0;
// outer for loop to iterate the given array to n times to sort the
// elements.
for (int sortedIndex = 0; sortedIndex < input.length – 1; sortedIndex++) { // first time assigning 0 (first position) to current minimum // variable. (here 0=>input[0]=>3)
currentMin = sortedIndex;

// inner for loop to iterate the array from sortedIndex+1, because
// what ever is there in the first position of the outer loop is
// assumed that it is sorted already.
for (int elementSortIndex = sortedIndex + 1; elementSortIndex < input.length; elementSortIndex++) { // only if input[currentMin] > input[elementSortIndex] then
// assign that index value to currentMin value.
// here input[0]=3 is greater only when input[5]=2 so the
// currentMin variable is assigned with 5 index value.
if (input[currentMin] > input[elementSortIndex]) {
currentMin = elementSortIndex;
}
}

// now completely get out of the inner for loop to swap the index
// positions.
long temp = input[currentMin]; // temp = input[5]=2
input[currentMin] = input[sortedIndex]; // input[5]=input[0] now
// fifth position gets the
// value 3
input[sortedIndex] = temp; // input[0]=2 now first position gets the
// value 2
}
return input;
}

}

[/java]

 

 

Sample Data Output:

[plain]
Before Sorting:::
[3, 3009, 76, 172, 271, 2]
After Sorting:::
[2, 3, 76, 172, 271, 3009]
[/plain]

 

You can also read,

Singly Linked List Algorithm Implementation Java Example

Binary Search Implementation in Java Example