Java Reference

In-Depth Information

}

The
insertionSort
method moves the elements from the
l2
listintothe
l1
list. Every

time an element is inserted into the
l1
list, it is inserted in the right place so that the

elements of the
l1
list are sorted. The base case is when the
l2
list becomes empty. The

method iterates through all the elements of the
l1
list and finds the correct place to insert

the first element of the
l2
list. If such a place is not found, then the element is inserted at

the end. At the same time, this first element is removed from the
l2
list. Note that once

the insertion point is found, the recursive call is made. When we return from the recursive

call, we simply exit the method by calling the
return
statement.

Once again, this is an example of tail recursion. The recursive calls are made at the

end of the two execution paths of the method. The code can be rewritten to use an infinite

while
loop as follows.

public static void
insertionSort(ArrayList

<

Integer

>

l1 , ArrayList

<

Integer

>

l2)

{

while
(
true
)

{

if
(l2.size() == 0)
{

return
;

int
newElement = l2 . get (0) ;

l2 .remove(0) ;

int
i;

for
(i = 0; i
<
l 1 . s i z e ( ) ;

i ++)

{

if
(newElement
<
l1 .get( i))

{

l1 . add( i , newElement) ;

break
;

}

if
(i == l1.size())
{

l1 . add(newElement) ;

}

}

}

Note that there is a non-cosmetic change to the code. Since we want our algorithm to go

to the next iteration when we discover the insertion point, we moved the variable
i
outside

the
for
statement. In this way, we can check if the element was already inserted into the

l2
list or if it needs to be inserted at the end of the list. Recall that the
add
method for an

ArrayList
inserts the element at the end of the list if the insert location is not specified.

Similar to the bubble and selection sort, the insertion sort takes roughly
n

∗

n
time for an

array of
n
elements.

14.4.5 Quick Sort

Quick sort
starts by making the first element the pivot. Then it finds all the elements

that are smaller than the pivot and puts them before the pivot. All the elements that are

larger than the pivot are put after the pivot. The elements before and after the pivot are

sorted recursively. Since there are two recursive calls at the end, the tail recursion principle

does not apply and a non-recursive solution to the problem cannot be easily found.

Consider the following array of numbers.

2033058407

Quick sort will select the first element as the pivot: the number 20. The numbers that are