Searching and Sorting - A Concise and Practical Introduction to Programming Algorithms in Java - page 139

{ }

int [] array = 16 ,15 ,14 ,13 ,12 ,11 ,10 ,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ;

nboperations=0;
SelectionSort(array) ;
System . out . println ( "Number of operations:" +nboperations) ;
int nb=2 1)/2;

System . out . println ( "Number of operations:" +nb ) ;
}
}

∗ array . length ∗ (array . length −

We get (with 15 16 = 240):

12345678910111213141516
Number of operations:240
Number of operations:240

×

6.5 QuickSort: Recursive sorting

Let us now turn to a fast expected sorting algorithm often used in practice:
QuickSort. QuickSort is a recursive sorting procedure that proceeds as follows:

- First, partition the elements according to the pivot array[0] :

- those smaller than the pivot stored in arrayleft ,

- those greater than the pivot stored in arrayright ,

- those equal to the pivot (in case of ties) stored in arraypivot .

- Then solve recursively the sorting in arrays arrayleft and arrayright ,and

- Recompose the array as follows:

arrayleft arraypivot arrayright

Note that in this recursive algorithm, the terminal case is sorting a single
element. This is done trivially by doing nothing since a single element array is
a sorted array by definition. The partition procedure is done in-place without
using extra memory as follows:

Program 6.10 The partition procedure in QuickSort
static int partition( int [ ] array , int left , int right)

{ int m= l e f t ; // pivot
for ( int i=left+1; i < =r i g h t ; i ++)
{ if (GreaterThan(array [ left ] , array [ i ]) )
{ swap(array , i ,m+1);