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.

finding the minimum value in the unsorted array and move it to the first position.
Now increase the pointer value by 1.
Again start searching for next minimal value in array (except in previous one)
If found minimal swap the value to second position element
Else leave it move pointer next
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

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

Code description

Start inserting the values in array.
Assign the first value to first index.
For next value compare it with previous values.
If it is small from previous swap it from previous.
Else assign that value to next index.
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