Sorting algorithms - Data Structures and Problem Solving Using Java - page 366

1 public static void sort( List<Integer> items )
2 {
3

if( items.size( ) > 1 )

{ 4

List<Integer> smaller = new ArrayList<Integer>( );

5

List<Integer> same = new ArrayList<Integer>( ); 6

List<Integer> larger = new ArrayList<Integer>( );

7

8
9

Integer chosenItem = items.get( items.size( ) / 2 );

for( Integer i : items ) 10

{

11

if( i < chosenItem ) 12

smaller.add( i );

13

else if( i > chosenItem ) 14

larger.add( i );

15

else 16

same.add( i );

17

} 18

19
20 sort( smaller ); // Recursive call!

sort( larger ); // Recursive call! 21

22
23 items.clear( );

items.addAll( smaller ); 24

items.addAll( same ); 25

items.addAll( larger ); 26

} 27

28 }

figure 8.10
Simple recursive sorting algorithm

duplicates with relatively few distinct items, as is sometimes the case, then
the performance is extremely good.
The algorithm we have described forms the basis of the classic sorting
algorithm, quicksort . However, by making the extra lists, and doing so recur-
sively, it is hard to see how we have improved upon mergesort. In fact so far,
we really haven't. In order to do better, we must avoid using significant extra
memory and have inner loops that are clean. Thus quicksort is commonly
written in a manner that avoids creating the second group (the equal items),
and the algorithm has numerous subtle details that affect the performance.
The rest of the section describes the most common implementation of quick-
sort, namely one in which the input is an array, and which no extra arrays are
created by the algorithm.