Selection Sort and Insertion Sort In JAVA

Introduction

In Today's article you learn about Selection Sort & Insertion Sort in JAVA.

1. Selection sort

Selection Sort is a sorting algorithm that sorts data items into ascending or descending order. Sorting takes place through all the data items one-by-one while looking for either largest or smallest data values and making only one swap after finding either largest or smallest data values. Hence, this sorting algorithm is referred to as the selection sort because on each pass this algorithm selects either largest or smallest of the remaining unsorted data values and places them in the right order.

Code description

Concept of Selection Sort is simple. Now, array is imaginary divided into two parts-sorted one and unsorted one. In begining sorted part is empty, while unsorted one contains whole array. At every step, algorithm finds minimal element in the unsorted part and adds it to the end of the sorted one. When unsorted part becomes empty, algorithm stops.

When algorithm sorts an array, it swaps first element of unsorted part with minimal element and then it is included to the sorted part. This implementation of selection sort in not stable. In case of linked list is sorted, and, instead of swaps, minimal element is linked to the unsorted part, selection sort is stable.

Let us see an example of sorting an array to make the idea of selection sort clearer.

Example

Sort the array {5, 1, 12, -5, 16, 2, 12, 14} using selection sort.

Working of the selection sort :

Say we have an array unsorted A[0],A[1]................ A[n-1] and A[n] as input. Then the following steps are involved by selection sort algorithm.

 1. finding the minimum value in the unsorted array and move it to the first position.
 2. Now increase the pointer value by 1.
 3. Again start searching for next minimal value in array (except in previous one)
 4. If found minimal swap the value to second position element
 5. Else leave it move pointer next
 6. Sort the remaining values of data set (excluding the previous value).

Example

public class SelectionSortEx
 {
   public static void main(String a[])
    {
      //Numbers which are to be sorted
      int n[] = {55,33,22,88,99,44,11,77,66};
      //Displays the numbers before sorting
      System.out.print("Before sorting, numbers are ");
      for(int i = 0; i < n.length; i++)
       {
         System.out.print(n[i]+" ");
       }
      System.out.println();
      //Sorting in ascending order using bubble sort
      initializeselectionSort(n);
      //Displaying the numbers after sorting
      System.out.print("After sorting, numbers are ");
      for(int i = 0; i < n.length; i++)
       {
         System.out.print(n[i]+" ");
       }
    }

   //This method sorts the input array in descending order
   public static void initializeselectionSort( int n[])
    {
     int i,j,first,temp;
     for (i=n.length-1;i >0; i--)
      {
        first=0; //initialize to subscript of first element
        for(j=1;j<=i;j++) //locate smallest element between 1 and i.
         {
           if(n[j]<n[first])
           first=j;
         }
        temp=n[first]; //swap the smallest found in position i.
        n[first]=n[i];
        n[i] = temp;
      }
   }
}

Output

2. Insertion Sort

Insertion sort is a good choice for small values and for nearly-sorted values. Insertion sorting algorithm is similar to bubble sort. But insertion sort is more efficient than bubble sort because in insertion sort the comparisons are less. In insertion sorting algorithm compare the value until 
all the prior elements are lesser than compared value is not found. This mean that all the past values are smaller than compared value. Insertion sort is a good choice for small values and for nearly-sorted values. There are more efficient algorithms such as heap sort, quick sort, or
merge sort for large values.

Advantages of insertion sorting: 

1. It is easy to implement 
2. It is efficient on data values which are nearly sorted. 
3. It is efficient on (quite) small data sets

Code description as shown in example

1. Start inserting the values in array.
2. Assign the first value to first index.
3. For next value compare it with previous values.
4. If it is small from previous swap it from previous.
5. Else assign that value to next index.
6. Do that for all remaining values.

example

Sort {7, -5, 2, 16, 4} using insertion sort

Example

public class InsertionSortEx
 {
  public static void main(String a[])
   {
     //Numbers which are to be sorted
     int n[] = {124,23,43,12,177,25,2,1,67};
         //Displays the numbers before sorting
     System.out.print("Before sorting, numbers are ");
     for(int i = 0; i < n.length; i++)
      {
        System.out.print(n[i]+" ");
      }
     System.out.println();
     //Sorting in ascending order using bubble sort
     initializeInsertionSort(n);
     //Displaying the numbers after sorting
     System.out.print("After sorting, numbers are ");
     for(int i = 0; i < n.length; i++)
      {
        System.out.print(n[i]+" ");
      }
    }

   //This method sorts the input array in asecnding order
  public static void initializeInsertionSort(int n[])
   {
     for (int i = 1; i < n.length; i++)
          {
             int j = i;
             int B = n[i];
             while ((j > 0) && (n[j-1] > B))
              {
                  n[j] = n[j-1];
                  j--;
               }
             n[j] = B;
         }
    }
}

Output