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
l1 , ArrayList
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.
Quick sort will select the first element as the pivot: the number 20. The numbers that are
Search WWH ::

Custom Search