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
