Stable Sorting in Java

In this tutorial, we will learn some basic concepts of stable sorting in Java with an example program.
For understanding this we will take the example of insertion sort, which is one of the types of stable sorting algorithms.
In this tutorial, we will look at its working, examples, along with proper understandable code.

The logic of Stable sorting

Let’s suppose we have some data and we want to arrange in ascending or descending order. There are many sorting algorithms through which we can easily sort our array.
But sorting through something called stable sorting is pretty much easier.
Let’s suppose we have some cards and we want to arrange in increasing order of ranks
, We will consider that our left hand is unsorted and our right hand is sorted.
Sorting could be easily done in 2 ways.
In our first way, we draw a card one by one from the unsorted subset and try to check its correct place to be filled in our next hand.
At the end of the process, we will get a sorted set of cards.

In our second way, we will divide our cards into 2 subsets and imagine a line just next to our first card.
after doing this we will compare ranks of all the cards which are placed right to it.
If the card has a less degree then we will swap with the boundary value in the left after comparing.
The same process is done in Insertion sort.

Understanding Insertion Sort

Flowchart of stable sorting in Java

Let’s suppose we want to sort a given list of numbers having values[10, 9 , 5, -2, 8, 6].
Firstly we will divide our array into 2 iterations.
array with [0] index or 10 is in the sorted part because a single element is always sorted

Step 2-We will shift our imaginary line into its right and by that time we will check if the element present in the right is lesser than the element before the boundary.
if it so then swaps the element before the boundary element and shifts the boundary one step ahead.

Step 3-Compare the next element to the element before the boundary or flag value.
If it is less then swapping is till done till we found the exact index of the element.

Step 4-Repeat the process till the end.

The drawback of Insertion Sort

It is not the best in terms of performance, but it is efficient than the Selection sort and Bubble sort.
If we compare these in practical scenarios.
The time complexity of its worst case is exactly the same as its average case.

Time Complexity

  • Worst Case Complexity [Big-O]:-O(n square)
  • Best Case Complexity Big-Omega]:- O(n)
  • Average Case Complexity [Big-theta]:- O(n square)

Stable sort program in Java

import java.util.*;
class insertion
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int n,key,j;
System.out.println("***Enter the size of the array***");
n=sc.nextInt();
int arr[]=new int[n];
System.out.println("***Enter the array***");
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
for (int i=1;i<n;++i)
{ 
key=arr[i]; 
j=i-1; 
while(j >= 0 && arr[j]>key)
{ 
arr[j+1]=arr[j]; 
j=j-1; 
} 
arr[j+1]=key; 
} 
System.out.println("***Printing the array***");
for(int i=0;i<n;i++)
{
System.out.println(arr[i]);
}
}
}

OUTPUT

***Enter the size of the array***
6
***Enter the array***
10
9
5
-2
8
6
***Printing the array***
-2
5
6
8
9
10

Hope this tutorial helped you.

Leave a Reply

Your email address will not be published. Required fields are marked *