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)
{
l2 .add(el) ;
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
;
}
l1 . add(newElement) ;
insertionSort(l1 , l2);
}
