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 = 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 {
}
} ArrayList < Integer > result = quickSort(smaller);
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.

Search WWH ::

Custom Search