Introduction
Selection sort is the simplest sorting algorithm in terms of implementation.Let's consider we have a list of elements i.e. {3, 9, 0, 5, 4 }
a) Selection sort maintains two sublists, one sorted and initially empty and second unsorted sublist i.e.
[ {}, {3, 9 , 0, 5 ,4 }]
b) It searches for the minimum element (for ascending sort) OR for a maximum element( for descending sort) in the unsorted list in each step.
Step 1
[ {0 }, {9,3,5,4}]Minimum element = 0 , swapped with 3
Step 2
Minimum element = 3 , swapped with 9[{0,3) , {9,5,4} ]
Step 3
Minimum element = 4 , swapped with 9[{0,3,4} , {5,9}]
Step 4
Minimum element = 5 , swapped with itself[{0,3,4,5}, {9}]
Step 5
Minimum element = 9 , swapped with itself[{0,3,4,5,9}, {}]
Worst Complexity: O(n*n)
Best Complexity : O(n * n)
Imperative style implementation using Java 7
public class SelectionSortExample {
private static int array[] = {3,9,0,5,4};
public static void main(String[] args) {
sortAscending();
System.out.println("Ascending Sorted List");
for(int value : array) {
System.out.print(value + " ");
}
sortDescending();
System.out.println("\nDescending Sorted List");
for(int value : array) {
System.out.print(value + " ");
}
}
private static void sortAscending() {
for(int outer=0; outer<array.length; outer++) {
int minimumIndex = outer;
for(int inner = outer+1; inner < array.length;inner++) {
// array[minimumIndex] > array[inner]
if(array[minimumIndex] > array[inner]) {
minimumIndex = inner;
}
}
int temp = array[outer];
array[outer] = array[minimumIndex];
array[minimumIndex] = temp;
}
}
private static void sortDescending() {
for(int outer=0; outer<array.length; outer++) {
int minimumIndex = outer;
for(int inner = outer+1; inner < array.length;inner++) {
// array[minimumIndex] < array[inner
if(array[minimumIndex] < array[inner]) {
minimumIndex = inner;
}
}
int temp = array[outer];
array[outer] = array[minimumIndex];
array[minimumIndex] = temp;
}
}
}
Declarative Style Implementation using Java 8
import java.util.Arrays;
import java.util.stream.IntStream;
public class SelectionSortJava8Example {
private static int array[] = {0,5,2,6,3,1,-9};
static int minimumIndex = 0;
public static void main(String[] args) {
sortAscending();
System.out.println("Ascending Sorted List");
Arrays.stream(array).forEach(System.out::print);
sortDescending();
System.out.println();
System.out.println("Descending Sorted List");
Arrays.stream(array).forEach(System.out::print);
}
private static void sortAscending() {
IntStream.range(0, array.length).forEach(outer -> {
minimumIndex = outer;
IntStream.range(outer+1, array.length)
.forEach(inner -> {
// < is used for Ascedning sort
if(array[inner] < array[minimumIndex]) {
minimumIndex = inner;
}
});
//swap the elements
int temp = array[minimumIndex];
array[minimumIndex] = array[outer];
array[outer] = temp;
});
}
private static void sortDescending() {
IntStream.range(0, array.length).forEach(outer -> {
minimumIndex = outer;
IntStream.range(outer+1, array.length)
.forEach(inner -> {
// > is used for Descedning sort
if(array[inner] > array[minimumIndex]) {
minimumIndex = inner;
}
});
//swap the elements
int temp = array[minimumIndex];
array[minimumIndex] = array[outer];
array[outer] = temp;
});
}
}
Input : 3,9, 0, 5 ,4
Output: 0 3 4 5 9 (Ascending)
Output: 9 5 4 3 0 (Descending)
Output: 0 3 4 5 9 (Ascending)
Output: 9 5 4 3 0 (Descending)
Conclusion
In this tutorial, we learned how to implement Selection Sort using Java language. Please leave your comments in the comment box. Happy learning :)
Comments
Post a Comment