Sort Algorithms

Unsorted array: [5, 4, 14, 2, 8]
1st index iteration: value at 1st index = 4 which is less than 5, so array becomes [5, 5, 14, 2, 8], as we reached the start we place the value at 0th index and array becomes [4, 5, 14, 2, 8]
2nd index iteration: value at 2nd index = 14 which is greater than 5, so leave the array as it is. Now array = [4, 5, 14, 2, 8]
3rd index iteration: value at 3rd index = 2 which is smaller than 14, so array becomes [4, 5, 14, 14, 8], again 2 is smaller than 5, so array becomes [4, 5, 5, 14, 8]. Again 2 is smaller than 4, so array becomes [4, 4, 5, 14, 8]. As we reached the start of array, we place 2 at 0th index and array becomes [2, 4, 5, 14, 8]
4th index iteration: value at 4th index = 8, so array becomes [2, 4, 5, 14, 14], then 8 is greater than 5, so place 8 at the 14th place and array becomes [2, 4, 5, 8, 14]
Key points to note when writing this program:

• Start with 2nd element to the last element of the array, so use a for loop.
• Store the value into another variable to avoid it being lost when we change the index value in between.
• We need to keep changing the values until we are at 0th index or we found prior value to be greater, so we can use a while loop for this.

Here is the implementation of the insertion sort algorithm based on above example and key points.


import java.util.Arrays;
public class test{
    public static void main(String args[])
    {
        int[] arr = {2,5,3,1};

        for (int i = 1; i < arr.length; i++) {
                int valueToSort = arr[i];
                int j = i;
                while (j > 0 && arr[j - 1] > valueToSort) {
                    arr[j] = arr[j - 1];
                    j--;
                }

            arr[j] = valueToSort;
        }
    for(int c:arr)
    {
        System.out.println(c);
    }
    }
}




Source:http://www.journaldev.com/585/insertion-sort-in-java-algorithm-and-code-with-example

 Selection Sort

import java.util.Arrays;
public class test{
    public static void main(String args[])
    {
        int[] arr = {2,5,3,1};
        int n = arr.length;
        for(int i=0;i<n-1;i++)
        {
            int min = i;
            for(int j = i+1;j<n;j++)
            {
                if(arr[i]>arr[j])
                    {
                        min = j;
                    }   
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
       
        }       
        for(int c:arr)
        {
            System.out.println(c);
        }
    }
}