Selection Sort and Insertion Sort In JAVA

Introduction

 
In today's article, you will learn about Selection Sort & Insertion Sort in JAVA.
 

Selection Sort in Java

 
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 imaginarily divided into two parts-sorted one and unsorted one. In beginning sorted part is empty, while unsorted one contains whole array. At every step, the 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.
 
Selection Sort in Java
 
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 moveit to the first position.
  2. Now increase the pointer value by 1.
  3. Again start searching for next minimal value in array (except in previousone) 
  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
  1. public class SelectionSortEx {  
  2.     public static void main(String a[]) {  
  3.         //Numbers which are to be sorted  
  4.         int n[] = {  
  5.             55,  
  6.             33,  
  7.             22,  
  8.             88,  
  9.             99,  
  10.             44,  
  11.             11,  
  12.             77,  
  13.             66  
  14.         };  
  15.         //Displays the numbers before sorting  
  16.         System.out.print("Before sorting, numbers are ");  
  17.         for (int i = 0; i < n.length; i++) {  
  18.             System.out.print(n[i] + " ");  
  19.         }  
  20.         System.out.println();  
  21.         //Sorting in ascending order using bubble sort  
  22.         initializeselectionSort(n);  
  23.         //Displaying the numbers after sorting  
  24.         System.out.print("After sorting, numbers are ");  
  25.         for (int i = 0; i < n.length; i++) {  
  26.             System.out.print(n[i] + " ");  
  27.         }  
  28.     }  
  29.   
  30.     //This method sorts the input array in descending order  
  31.     public static void initializeselectionSort(int n[]) {  
  32.         int i, j, first, temp;  
  33.         for (i = n.length - 1; i > 0; i--) {  
  34.             first = 0//initialize to subscript of first element  
  35.             for (j = 1; j <= i; j++) //locate smallest element between 1 and i.  
  36.             {  
  37.                 if (n[j] < n[first])  
  38.                     first = j;  
  39.             }  
  40.             temp = n[first]; //swap the smallest found in position i.  
  41.             n[first] = n[i];  
  42.             n[i] = temp;  
  43.         }  
  44.     }  
  45. }  
Output
 
Selection Sort in Java
 

Insertion Sort in Java

 
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 means 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
  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
 
Insertion Sort in Java
  1. public class InsertionSortEx {  
  2.     public static void main(String a[]) {  
  3.         //Numbers which are to be sorted  
  4.         int n[] = {  
  5.             124,  
  6.             23,  
  7.             43,  
  8.             12,  
  9.             177,  
  10.             25,  
  11.             2,  
  12.             1,  
  13.             67  
  14.         };  
  15.         //Displays the numbers before sorting  
  16.         System.out.print("Before sorting, numbers are ");  
  17.         for (int i = 0; i < n.length; i++) {  
  18.             System.out.print(n[i] + " ");  
  19.         }  
  20.         System.out.println();  
  21.         //Sorting in ascending order using bubble sort  
  22.         initializeInsertionSort(n);  
  23.         //Displaying the numbers after sorting  
  24.         System.out.print("After sorting, numbers are ");  
  25.         for (int i = 0; i < n.length; i++) {  
  26.             System.out.print(n[i] + " ");  
  27.         }  
  28.     }  
  29.   
  30.     //This method sorts the input array in asecnding order  
  31.     public static void initializeInsertionSort(int n[]) {  
  32.         for (int i = 1; i < n.length; i++) {  
  33.             int j = i;  
  34.             int B = n[i];  
  35.             while ((j > 0) && (n[j - 1] > B)) {  
  36.                 n[j] = n[j - 1];  
  37.                 j--;  
  38.             }  
  39.             n[j] = B;  
  40.         }  
  41.     }  
  42. }  
Output
 
Insertion Sort in Java