One more simple form of sorting algorithm is Selection Sort.
For in-place implementation in java, starting from 1st index, find the smallest element (takes O(n) ) and put it at the first index of unsorted sub array. So there will be 2 parts of main array, left one will have sorted element and right one will have unsorted. We choose smallest from the right one and will put it at the beginning of the unsorted sub array. Now Sorted array will have one more element and unsorted array will have one less. Continue this process till we reach the end of element. ( takes O(n)).
So finding smallest for one loop will take O(n) and there will be at most n loop so it total time in worst case will be O(n^2)
SelectionSort.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
package daa; import java.util.ArrayList; public class SelectionSort { private ArrayList<Integer> inputArray = new ArrayList<Integer>(); //Just To fetch display purpose public ArrayList<Integer> getSortedArray() { return inputArray; } public SelectionSort(ArrayList<Integer> inputArray){ this.inputArray = inputArray; } public void sortGivenArray(){ int smallInt = 0; int j=0; int smallIntIndex = 0; for(int i=1;i<inputArray.size();i++){ smallInt = inputArray.get(i-1); smallIntIndex = i-1; for(j=i;j<inputArray.size();j++){ if(inputArray.get(j)<smallInt){ smallInt = inputArray.get(j); smallIntIndex = j; } } //Swap the smallest element with the first element of unsorted subarray swap(i-1, smallIntIndex); } } public void swap(int sourceIndex,int destIndex){ int temp = inputArray.get(destIndex); inputArray.set(destIndex, inputArray.get(sourceIndex)); inputArray.set(sourceIndex, temp); } } |
MainPractise.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.util.ArrayList; import daa.SelectionSort; public class MainPractise implements Cloneable { public static void main(String[] args) { ArrayList<Integer> unsortedArray = new ArrayList<Integer>(); unsortedArray.add(8); unsortedArray.add(7); unsortedArray.add(6); unsortedArray.add(5); unsortedArray.add(4); unsortedArray.add(0); unsortedArray.add(2); SelectionSort ss = new SelectionSort(unsortedArray); System.out.println("---------Initial Unsorted Array---------"); for(int i:ss.getSortedArray()){ System.out.print(i+" "); } ss.sortGivenArray(); System.out.println("\n------------Sorted Array------------"); for(int i:ss.getSortedArray()){ System.out.print(i+" "); } } } |
Output:
|
1 2 3 4 |
---------Initial Unsorted Array--------- 8 7 6 5 4 0 2 ------------Sorted Array------------ 0 2 4 5 6 7 8 |
You can have above code from GIT.
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git