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.

 

 

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

 

 

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

 

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