Java Reference
In-Depth Information
Next, the algorithm will compare the numbers 10 and 20. They are in the correct order,
so nothing to do. Lastly, the algorithm will compare the numbers 20 and 2. They are in the
wrong order and therefore the algorithm will swap them.
510220
After the first pass finishes executing, the biggest number will be at the end of the array
(in our case, this is the number 20). The second pass applies the same algorithm, but it is
not applied on the last number, which we already know is the biggest. If the algorithm is
implemented recursively, then the base case is when the array consists of a single element.
In this case, nothing needs to be done because an array of a single element is already sorted.
The recursive implementation follows.
public class
Test
{
public static void
main(String args [])
{
int
[] a =
{
10,5,20,2
}
;
bubbleSort(a,a. length
−
1) ;
for
(
int
el : a)
{
System. out . print ( el+
""
);
}
}
public static void
bubbleSort(
int
[]a,
int
end)
{
if
( end==0)
return
;
for
(
int
i=0;i
<
end ;
i ++)
{
if
(a[ i]
>
a[i+1])
{
int
temp = a [ i ] ;
a[i] =a[i+1];
a[i+1] = temp;
}
}
bubbleSort(a,end
−
1) ;
}
}
Note that only the index of the last element of the array to be processed changes. The
index of the first element to be processed is always 0. This is the reason why only the end
of the array is passed as a parameter. Note as well that the algorithm combines a recursive
call with a
for
statement. There is nothing that says that a recursive solution cannot be
embedded with loops.
Since the recursive call is at the end, this is again a case of tail recursion. The
bubbleSort
method can be rewritten not to use a recursion as follows.
public static void
bubbleSort(
int
[] a,
int
end)
{
while
(
true
)
{
if
(end == 0)
{
return
;
for
(
int
i=0;i
<
end ;
i ++)
{
if
(a[ i ]
>
a[i + 1])
{
int
temp = a [ i ] ;
a[i] =a[i + 1];
a[i + 1] = temp;
}
end
−−
;
}
