Skip to content

Instantly share code, notes, and snippets.

@realFranco
Created January 17, 2020 14:57
Show Gist options
  • Save realFranco/5b026bf84cee2af76cdf065689bb85c9 to your computer and use it in GitHub Desktop.
Save realFranco/5b026bf84cee2af76cdf065689bb85c9 to your computer and use it in GitHub Desktop.
Dual Pivot Quick Sort - Yarovlavskiy Algorithim implementation.
/*
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment