Java Reference
In-Depth Information
}
A possible optimization of the method is to keep track of how many times the swap was
performed. If the swap was not performed at all during an iteration of the algorithm, then
we know that the list is already sorted. Here is how this optimization can be added to the
code.
public static void
bubbleSort(
int
[] a,
int
end)
{
while
(
true
)
{
if
(end == 0)
{
return
;
boolean
modified =
false
;
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;
modified =
true
;
}
if
(!modified)
return
;
//array not modified
end
−−
;
}
}
n
time. This means that it may take one
trillion operations to sort an array of one million integers. As we will see later, there are
more ecient ways to sort an array.
Note that the algorithm runs in roughly
n
∗
14.4.3 Selection Sort
Selection sort
works similar to the bubble sort. However, instead of moving the biggest
elements to the end of the array, the algorithm moves the smallest elements to the beginning
of the array. Consider the same array of integers as before.
105202
The algorithm goes through the whole array and finds the smallest number: 2. Next, it
swaps the smallest number with the first element of the array.
2 5 20 10
At this point, the smallest number of the array is the first element. The algorithm continues
recursively by sorting the rest of the array (i.e., all the numbers except for the 2, which is
already in the right place). The base case is when the size of the array becomes one. An
array of one element is already sorted. A recursive implementation of the algorithm follows.
public class
SelectionSort
{
public static void
main(String args [])
{
int
[] a =
{
10, 5, 20, 2
}
;
selectionSort(0, a);
for
(
int
el : a)
{
System. out . print ( el +
""
);
}
}
