Java Reference
In-Depth Information
14.4.4 Insertion Sort
The insertion sort method works by keeping two lists. At the beginning, the first list
will be empty, while the second list will contain the unsorted elements. At every iteration,
the first element of the second list is removed from the second list and inserted in its proper
place in the first list (i.e., the first list is always sorted). When the second list becomes
empty, the first list will contain all the elements sorted. Here is an example run of insertion
sort.
initial list : { 23,2,4,65,3 }
l1: {} l2= { 23,2,4,65,3 }
after 1 iteration : l1: { 23 } l2= { 2,4,65,3 }
after 2 iteration : l1= { 2,23 } ,l2= { 4,65,3 }
after 3 iterations : l1=
{
}
{
}
2,4,23
,l2=
65,3
after 4 iterations : l1=
{
2,4,23,65
}
,l2=
{
3
}
after 5 iterations : l1=
{
2,3,4,23,65
}
,l2=
{}
Let us look at a real-world example of how to apply insertion sort. Suppose that we are
given a deck of cards and we want to sort them. We can take the first card and put it in
the resulting list. Next, we will take the next card and put it again in the resulting list in
the right order and so on. At the end, all the cards will be sorted.
Since this algorithm involves adding and removing elements from lists, it can be more
easily implemented by using ArrayList s instead of arrays. If we want to solve the problem
recursively, we can create a method that moves the first number from the l2 list to the
correct position in the l1 list and then applies the algorithm recursively. The base case will
be when the l2 list becomes empty.
import java . util . ;
public class InsertionSort {
public static void main(String args [])
{
int [] a = { 23,2,4,65,3 } ;
ArrayList < Integer > l1 = new ArrayList <> () ;
ArrayList < Integer > l2 = new ArrayList <> () ;
for ( int el :a)
{
insertionSort(l1 , l2);
System. out . println ( l1 ) ;
} public static void insertionSort(ArrayList
<
Integer
>
l1 , ArrayList
<
{
if ( l 2 . s i z e ( )==0)
Integer
>
l2)
{
return ;
int newElement = l2 . get (0) ;
l2 .remove(0) ;
for ( int i=0;i < l 1 . s i z e ( ) ; i ++) {
if (newElement < l1 .get( i )) {
l1 . add( i , newElement) ;
insertionSort(l1 , l2);
return ;
}