Learn Java Java Tutoring is a resource blog on java focused mostly on beginners to learn Java in the simplest way without much effort you can access unlimited programs, interview questions, examples
Implement Insertion Sort Algorithm In Java – We will discuss the various methods to Implement Insertion Sort Algorithm In Java. The compiler has been added so that you can execute the programs easily, alongside suitable examples and sample outputs. The methods are – Also check Heap Sort In Java
- Algorithm – Using Array.
- Algorithm – Using Buffered Reader.
Insertion Sort Java – Using Array
1) We are using an array for insertion sort.
2) The print method will print the array elements, the sort method will sort the array elements.
3) The elements in the array are 9, 5, 0, 1, 8.
For 1st iteration, the inner loop compares the number with the previous number, if the previous number is greater than this number then shift the least number to left.
For i=1, inner loop compares the numbers 5<9, then 5 will be shifted to left. Then the series is 5, 9, 0, 1, 8. In this sorted subarray is 5,9.
For i=2, the inner loop compares the numbers 0<9, shift 0 to left, compare 0<5, shift 0 to left. Then the sorted subarray is 0, 5, 9. The series is 0, 5, 9, 1, 8.
For i=3, the inner loop will compare the numbers 1<9, shift 1 to left, compare 1<5, shift 1 to left, compare 1,0. The sorted subarray is 0, 1, 5, 9 and the series is 0, 1, 5, 9, 8.
For i=4, the inner loop will compare the numbers 8<9, shift 8 to left. The sorted series is 0, 1, 5, 8, 9.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
import java.util.Scanner; public class ISort { public static void Sort(int a[]) { int n=a.length,i,j,p,temp; for (i = 1;i < n; i++) { for (j=i-1; j >=0 && a[j+1]<a[j]; j--) { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; } } } public static void printarray(int a[]) { for(int i=0; i < a.length; i++) { System.out.print(a[i]+" "); } } public static void main(String[] args) { int n, res,i; Scanner s = new Scanner(System.in); System.out.print("Enter number of elements in the array:"); n = s.nextInt(); int a[] = new int[n]; System.out.println("Enter "+n+" elements "); for( i=0; i < n; i++) { a[i] = s.nextInt(); } System.out.println( "elements in array "); printarray(a); Sort(a); System.out.println( "\nelements after sorting"); printarray(a); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 |
Enter number of elements in the array:5 Enter 5 elements 9 5 0 1 8 elements in array 9 5 0 1 8 elements after sorting 0 1 5 8 9 |
Insertion Sort Using Buffered Reader
1) Buffered Reader reads the data from the character-based input stream. In this program, InputStreamReader is the character based input stream.
2) Using readLine() method read the data, parseInt() method converts the data into an integer value and store the numbers into the array a[].
The given series is 10, 2, 1, 56, 48, 11.
3) For each iteration of i, the inner loop will generate a sub-sorted array in which the least number is shifted to left by comparing with previous numbers.
4) 1st iteration of i, compare 10,2 and 2 shifted to left. Then the sorted subarray is 2, 10.
- 2nd iteration of i, compare 10,1 and shift 1 to left.compare 2,1 and shift 1 to left, then the sorted subarray is 1, 2, 10.
- 3rd iteration of i, compare 56 with the previous numbers of the sorted subarray, then the sorted subarray is 1, 2, 10, 56.
- 4th iteration of i, compare 48 with previous numbers of the sorted subarray, then the subarray is 1, 2, 10, 48, 56.
- 5th iteration of i, compare 11 with the previous numbers of the subarray, then the sorted array is 1, 2, 10, 11, 48, 56.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.Scanner; import java.io.*; public class ISort { public static void Sort(int a[]) { int n=a.length,i,j,p,temp; for (i = 1;i < n; i++) { for (j=i-1; j >=0 && a[j+1]<a[j]; j--) { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; } } } public static void printarray(int a[]) { for(int i=0; i < a.length; i++) { System.out.print(a[i]+" "); } } public static void main(String[] args) throws IOException { int n,i; BufferedReader b=new BufferedReader(new InputStreamReader(System.in)); System.out.println("enter N: "); n=Integer.parseInt(b.readLine()); int a[] = new int[n]; System.out.println("enter "+n+" elements "); for(i= 0; i< n; i++) a[i] = Integer.parseInt(b.readLine()); System.out.println("elements in array "); printarray(a); Sort(a); System.out.println("\nelements after sorting"); printarray(a); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
enter N: 6 enter 6 elements 10 2 1 56 48 11 elements in array 10 2 1 56 48 11 elements after sorting 1 2 10 11 48 56 |
If you have any queries or suggestion related to Implementation of Insertion Sort Java Algorithm program & Tutorial do leave a comment here.
