Using the quicksort implementation, determine the running time of quicksort for random input, sorted input and reverse-order input.

Question

This is the implementation.

template <typename Comparable>

void SORT( vector<Comparable> & items )

{

if( items.size( ) > 1 )

{

vector<Comparable> smaller;

vector<Comparable> same;

vector<Comparable> larger;

auto chosenItem = items[ items.size( ) / 2 ];

for( auto & i : items )

{

if( i < chosenItem )

smaller.push_back( std::move( i ) );

else if( chosenItem < i )

larger.push_back( std::move( i ) );

else

same.push_back( std::move( i ) );

}

SORT( smaller ); // Recursive call!

SORT( larger ); // Recursive call!

std::move( begin( smaller ), end( smaller ), begin( items ) );

std::move( begin( same ), end( same ), begin( items ) + smaller.size( ) );

std::move( begin( larger ), end( larger ), end( items ) - larger.size( ) );

}

}

Answer 1

it is O(N*logN)

How many records are in the array?

suppose you have 1000 records...

then 1000 * log 1000 = 1000*3 = 3000 ms

it will sort the array is 3000 ms = 3 secs