By hand. Sort the sequence 5, 6, 2, 9, 5, 1, 4, 1, 3 using quick sort, by using the code below. Please show steps, thank you!

----------------------------------------------------------------------------------------------------

template

void quicksort( vector & a, int left, int right ){

//Use quick sort if we have at least four elements.

if( left + 3 <= right ){

const Comparable & pivot = median3( a, left, right );

//Begin partitioning

int i = left, j = right - 1;

for( ; ; ){

while( a[ ++i ] < pivot ) { }

while( pivot < a[ --j ] ) { }

if( i < j )

std::swap( a[ i ], a[ j ] );

else

break;

}

std::swap( a[ i ], a[ right - 1 ] ); // Restore pivot

quicksort( a, left, i - 1 ); // Sort small elements

quicksort( a, i + 1, right ); // Sort large elements

}

else // Do an insertion sort on the subarray

insertionSort( a, left, right );

}

template

const Comparable & median3( vector & a, int left, int right ){

int center = ( left + right ) / 2;

if( a[ center ] < a[ left ] )

std::swap( a[ left ], a[ center ] );

if( a[ right ] < a[ left ] )

std::swap( a[ left ], a[ right ] );

if( a[ right ] < a[ center ] )

std::swap( a[ center ], a[ right ] );

// Place pivot at position right - 1

std::swap( a[ center ], a[ right - 1 ] );

return a[ right - 1 ];

}