Java Program - Selection Sort
Selection sort is based on the idea of finding smallest or largest element in unsorted array and placing it at the correct position in the sorted array. This will result into increasing the length of the sorted array by one and decreasing the length of unsorted array by one after each iteration.
Example:
To understand the selection sort, lets consider an unsorted array [1, 10, 23, -2] and discuss each step taken to sort the array in ascending order. In every pass, smallest element is found in the unsorted array and swapped with first element of unsorted array.
First Pass: The whole array is unsorted array and (-2) is the smallest number in the array. After finding (-2) as smallest number, it is swapped with first element of the array.
Second Pass: In this example, the left hand side array is sorted array and length of this array increase by one after each iteration. After first pass length of the sorted array is one. Rest of the array is unsorted array. (1) is the smallest number in the unsorted array which is swapped with first element of the unsorted array. After this swap, length of the sorted array and unsorted array will be two.
Third Pass: (10) is the smallest number in the unsorted array and swapped with the first element of the unsorted array.
Fourth Pass: (23) is the only number in the unsorted array and found to be at the correct position.
Implementation of Selection Sort
public class MyClass { // function for selection sort static void selectionsort(int Array[]) { int n = Array.length; int temp; for(int i=0; i<n; i++) { int min_idx = i; for(int j=i+1; j<n; j++) { if(Array[j] < Array[min_idx]) {min_idx = j;} } temp = Array[min_idx]; Array[min_idx] = Array[i]; Array[i] = temp; } } // function to print array static void PrintArray(int Array[]) { int n = Array.length; for (int i=0; i<n; i++) System.out.print(Array[i] + " "); System.out.println(); } // test the code public static void main(String[] args) { int[] MyArray = {1, 10, 23, 50, 4, 9, -4}; System.out.println("Original Array"); PrintArray(MyArray); selectionsort(MyArray); System.out.println("\nSorted Array"); PrintArray(MyArray); } }
The above code will give the following output:
Original Array 1 10 23 50 4 9 -4 Sorted Array -4 1 4 9 10 23 50
Time Complexity:
The time complexity of selection sort is Θ(N²) in all cases even if the whole array is sorted because the entire array need to be iterated for every element and it contains two nested loops.
Recommended Pages
- Java - Swap two numbers
- Java Program - Fibonacci Sequence
- Java Program - Insertion Sort
- Java Program - Find Factorial of a Number
- Java Program - Find HCF of Two Numbers
- Java Program - Merge Sort
- Java Program - Shell Sort
- Stack in Java
- Queue in Java
- Java Program - Find LCM of Two Numbers
- Java Program - To Check Whether a Number is Palindrome or Not
- Java Program - To Check Whether a String is Palindrome or Not
- Java Program - Heap Sort
- Java Program - Quick Sort
- Java - Swap Two Numbers without using Temporary Variable
- Java Program - To Check Armstrong Number
- Java Program - Counting Sort
- Java Program - Radix Sort
- Java Program - Find Largest Number among Three Numbers
- Java Program - Print Floyd's Triangle