Java Reference
In-Depth Information
smaller than 20 are: 3, 5, 8, and 7. When we recursively sort them, we will get the numbers
{
3,5,7,8
}
. The numbers that are greater than 20 are
{
30,40
}
, which happen to be sorted.
Therefore, the sorted array will be
. One possible implementation is
shown next. For convenience, the implementation uses an
ArrayList
.
import
java . util .
∗
;
public class
QuickSort
{
public static void
main(String args [])
{
3,5,7,8
}
, 20,
{
30,40
}
{
int
[] a =
{
20, 3, 30, 5, 8, 40, 7
}
;
ArrayList
<
Integer
>
list =
new
ArrayList
<>
() ;
for
(
int
el : a)
{
list .add(el);
list = quickSort( list ) ;
System.out.println(list);
}
public static
ArrayList
<
Integer
>
quickSort(ArrayList
<
Integer
>
a)
{
if
(a. size()
<
=1)
return
a;
int
pivot = a. get(0) ;
ArrayList
<
Integer
>
smaller =
new
ArrayList
<>
() ;
ArrayList
<
Integer
>
greater =
new
ArrayList
<>
() ;
for
(
int
i=1; i
<
a . s i z e ( ) ;
i ++)
{
if
(a.get(i)
<
= pivot)
{
smaller .add(a. get( i )) ;
}
else
{
greater .add(a.get(i));
}
}
ArrayList
<
Integer
>
result = quickSort(smaller);
result .add(pivot);
result .addAll(quickSort(greater));
return
result ;
}
}
The recursive method first checks to see if the input array has 1 or 0 elements. If this is
the case, then nothing needs to be done because the list is already sorted. Otherwise, the
pivot element is set to the first element in the list and two empty
ArrayList
s are created.
All the elements that are smaller or equal to the pivot are added to the first list (this allows
sorting an array with duplicates), while all the elements that are bigger than the pivot are
added to the second list. Finally, the two lists are sorted and the pivot is inserted between
them to create the resulting list. The
addAll
method of the
ArrayList
classisusedto
merge two
ArrayList
s.
The quick sort behaves well when the
smaller
and
greater
lists are roughly of equal
size at every iteration. Ironically, the quick sort performs the worst when the array is already
sorted. In this case, one of the lists will contain all the elements, while the other list will be
empty at every single iteration. In this case, the performance will be comparable to that of
the previous sorting algorithms. When the two lists are roughly of the same size at every
iteration, the performance of the algorithm is roughly
n
log
(
n
) for an array of size
n
.This
means that an array of one million elements can be processed in roughly twenty million
operations, which is relatively fast. However, when the original list is close to being sorted,
the method can take roughly one trillion operations.
∗
