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);

}