Dual Pivot Quick Sort - Yarovlavskiy Algorithim implementation.

dual_pivot_quick_sort.c

/* 	
	Code Name:	dual_pivot.c
	Developer:	franco Gil
	Date:		18*2*17
	Edited: 	1*12*18
	Concept:    Dual pivot Quicksort. (Yarovlavskiy)

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

	Compilation way # 1: 

		gcc dual_pivot.c -DD -DSize=x
			
		Those macros are optional:

		 -DD is to get a cCOMPLETA OUTPUT from the array 
		 -DSize is the size of the array on compiltation time

		By default  is  2 Millions > 'Size' < 2.1 Millions

	Execution way:

		Linux: ./a.out > out

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

	Compitalion way # 2:

		gcc dual_pivot.c

		Also you can use the macro -DSize on the line to compile

	Execution way ( output is too big ):

		Linux: ./a.out > out 
*/

#include <stdio.h>
#include <time.h>	
#include <stdlib.h>	

#define LIMIT 2093000

void swap( int A[ ],  int i, int j);
void fillarray(int v[ ],  int n);
void genRndArray( int v[ ], int size);
void DUALPIVOT( int a[ ],  int left,  int right);
void print( int a[], int M );

int main()
{
	int a[ LIMIT ], left, M;
	left=0;
	M=2093000;

	#ifdef Size
		M=Size;
	#endif
	printf("Elements on the array: %d\n", M);
	printf("\n");
	fillarray(a, M);
	genRndArray(a, M);
	#ifdef D
		printf("Array on the input: "); 
		print( a, M );
		printf("\n");
	#endif
	clock_t tic = clock(); DUALPIVOT(a, left, M); clock_t toc = clock();
	printf("Soting time using quick-sort_dualP %f seconds\n\n", (double)(toc - tic) / CLOCKS_PER_SEC);
	#ifdef D
		printf("Array on the output: "); 
		print( a, M );
	#endif

	return 0;
}

void print( int a[], int M )
{
	for( int i = 0; i < M; i++ )
		printf("%d ", a[ i ]);
	printf("\n");
}

void swap( int A[ ],  int i,  int j)
{
   	int tmp = A[i];
    A[i] = A[j]; 
    A[j] = tmp;
}

void fillarray( int v[ ],  int n)
{
	int temp;

	for(temp=0; temp < n; temp++)
		v[ temp ] = temp;
}

void genRndArray( int v[ ],  int size)
{
	int i, temp;

	// Fischer - Yate implementation
	for(i=0; i < size-2; i++)
	{
		temp = rand()%(size-i+1) + i;
		swap(v, i, temp);
	}	
}

void DUALPIVOT(  int a[ ], int left,  int right)
{
	int p, q, l, g, k;

	if((right - left) >= 1)
	{
		if( a[ left ] > a[ right ]) swap(a, left, right);
		p = a[ left ]; 
		q = a[ right ];
		l = left + 1; 
		g = right - 1;
		k = l;
		while( k <= g)
		{
			if( a[ k ] < p)
			{
				swap(a, k, l);
				++l;
			}
			else if(a[ k ] >= q)
			{
				while(( a[ g ] > q) && (k < g)) --g;
				swap(a, k, g);
				--g;
				if(a[ k ] < p)
				{
					swap(a, k, l);
					++l;
				}
			}
			++k;
		}
		--l;
		++g;
		swap(a, left, l); 
		swap(a, right, g);
		DUALPIVOT(a, left, l-1);
		DUALPIVOT(a, l+1, g-1);
		DUALPIVOT(a, g+1, right);
	}
}