What is the C plus plus program for quick sort using template function?

Answer 1

#include<iostream>

#include<time.h> // used by srand()

// Swap the given values (by reference).

template<class T>

void exch( T& x, T& y )

{

T tmp=x;

x=y;

y=tmp;

}

// Generates a pseudo-random number in the range min to max (inclusive).

int get_rand( const int range_min=0, const int range_max=RAND_MAX )

{

static bool seeded = false;

if( !seeded )

{

seeded = !seeded;

std::srand((unsigned) time(NULL));

while( get_rand() );

}

return((int)((double)std::rand() / (RAND_MAX+1) * ((range_max+1) - range_min) + range_min));

}

template<class T>

void quicksort( T a[], int l, int r )

{

int i;

static int j;

tail_call:

if(r<=l)

return;

// Select random pivot and move it to end of array.

exch( a[get_rand(l,r)], a[r] );

i = l-1;

j = r;

while(1)

{

// Locate the 1st value from left that is not less than the pivot.

while(a[++i]<a[r]);

// Locate the 1st value from right

while(a[r]<a[--j])

if(j==l)

break;

if(i>=j)

break;

exch(a[i], a[j]);

}

exch( a[i], a[r] );

// Determine the smaller subset

static int l1, l2;

l1=l, l2=i-1;

int r1=i+1, r2=r;

if(r2-r1<l2-l1)

{

l1=r1, l2=r2;

r1=l, r2=i-1;

}

// Recurse over smaller subset

quicksort( a, l1, l2);

// Tail-call over largest subset

l=r1, r=r2;

goto tail_call;

}

// Helper method: sorts an array up to the given size.

template<class T>

void quicksort( T a[], const size_t size )

{

if( size < 2 )

return;

quicksort( a, 0, size-1 );

}

template<class T>

void print_array(T a[], const size_t size)

{

for(int i=0; i<size; ++i)

std::cout<<my_array[i]<<" ";

std::cout<<'\n'<<std::endl;

}

int main()

{

size_t size=1000000;

int my_array[size];

for( int i=0; i<size; ++i )

my_array[i]=get_rand( 1, size );

print_array( my_array, size );

std::cout<<"Sorting...\n"<<std::endl;

quicksort(a,size);

print_array( my_array, size );

}