I've been busy as of late with new job etc... However, I did want to post a bit of code I have been working on. This is open source stuff and for an algorithm I have been working on. This is for a Kth selection algorithm for finding the median of a list of floating point numbers.

As some might be aware, one of the most famous Kth selection routines is Quick Select. The originator of this algorithm is Tony Hoare. It was optimized by Niklaus Wirth. It was again optimized by Robert Floyd and Ronald Rivest to what is known as one of the Fastest Selection routines available. Lefteris Stamatogiannakis produced an even faster version of the Wirth routine (known as Lefselect) that was even faster than Robert Floyd's routine.

My routine is faster than all of those (though it might not be that fastest yet), however mine is open source and available to use for anything.

Of course for Vanity's sake I'll name it after myself

Here's the code

- Code: Select all
` float Dansby_kth(float array[], const unsigned int length, const unsigned int kTHvalue) `

{

#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

unsigned int left = 0;

unsigned int left2 = 0;

unsigned int right = length - 1;

unsigned int right2 = length - 1;

unsigned int kthPlus = kTHvalue;

unsigned int kthMinus = kTHvalue;

while (right > left)

{

//Median of 3 optimization

if( array[right] < array[left] ) F_SWAP(array[left],array[right]);

if( array[right] < array[kTHvalue] ) F_SWAP(array[kTHvalue],array[right]);

if( array[kTHvalue] < array[left] ) F_SWAP(array[left],array[kTHvalue]);

//Median of 3 optimization

const float temp = array[kTHvalue];//this is pivot

kthPlus = kTHvalue + 1;

kthMinus = kTHvalue - 1;

while ((right2 > kTHvalue) && (left2 < kTHvalue))

{

do

{

left2++;

}while (array[left2] < temp);

do

{

right2--;

}while (array[right2] > temp);

F_SWAP(array[left2],array[right2]);

}

left2++;

right2--;

if (right2 < kthMinus)

{

while (array[left2] < temp)

{

left2++;

}

left = left2;

right2 = right;

kthMinus --;

}

else

if (kthPlus < left2)

{

while (array[right2] > temp)

{

right2--;

}

right = right2;

left2 = left;

kthPlus ++;

}

else

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

{

F_SWAP(array[right],array[left]);

}

}

#undef F_SWAP

return array[kTHvalue];

}

to call the routine, you will need to keep track of the number of elements in the array. The middle element variable just points to the center of the list.

- Code: Select all
`//points to the center value (median)`

int middleElement = elementsinarray / 2;

Dansby_kth(redArray, elementsinarray,middleElement);

Dansby_kth(greenArray, elementsinarray,middleElement);

Dansby_kth(blueArray, elementsinarray,middleElement);

Any other optimization enhancements, just post.

Enjoy

Andy Dansby

7-18-15 edited the code to remove

if (rightleft < kTHvalue) as the code performed better without it.