Quote:

---

I'll be honest guys, I'm incredibly dissapointed! I thought I had something near optimum, but I must be missing something obvious! My meak 15 million per second is not much compared to your dozens of millions!

Anyway, incase any of you are interested, this is the best way to sort 7 cards. Please note, this sort algorithm I wrote beats all the classic sorting algorithms (quick sort, merge, insertion, std::Sort). It's basically a precomputed LUT for a pigeonhole sort.

// Represent the hand
sevenCardHand = ((__int64)1 << c1) | ((__int64)1 << c2) | ((__int64)1 << c3) | ((__int64)1 << c4) | ((__int64)1 << c5) | ((__int64)1 << c6) | ((__int64)1 << c7);

// Split 64 bit int into 4 chunks of 16 bits
firstChunk = (sevenCardHand & 0xFFFF);
secondChunk = (sevenCardHand & 0xFFFF0000) >> 16;
thirdChunk = (sevenCardHand & 0xFFFF00000000) >> 32;
fourthChunk = (sevenCardHand & 0xFFFF000000000000) >> 48;

// Reset pointer to sorted hand array
sortedPointer = 0;

// Retrieve records
numToLoop = intToIndexArr_L1[firstChunk][0];
for(anotherCounter = 1; anotherCounter < numToLoop; anotherCounter++)
sortedHand[sortedPointer++] = intToIndexArr_L1[firstChunk][anotherCounter];

numToLoop = intToIndexArr_L1[secondChunk][0];
for(anotherCounter = 1; anotherCounter < numToLoop; anotherCounter++)
sortedHand[sortedPointer++] = intToIndexArr_L1[secondChunk][anotherCounter] + 16;

numToLoop = intToIndexArr_L1[thirdChunk][0];
for(anotherCounter = 1; anotherCounter < numToLoop; anotherCounter++)
sortedHand[sortedPointer++] = intToIndexArr_L1[thirdChunk][anotherCounter] + 32;

numToLoop = intToIndexArr_L1[fourthChunk][0];
for(anotherCounter = 1; anotherCounter < numToLoop; anotherCounter++)
sortedHand[sortedPointer++] = intToIndexArr_L1[fourthChunk][anotherCounter] + 48;

---

Quote:

---

Network for N=7, using Bose-Nelson Algorithm:
SWAP(1, 2);
SWAP(0, 2);
SWAP(0, 1);
SWAP(3, 4);
SWAP(5, 6);
SWAP(3, 5);
SWAP(4, 6);
SWAP(4, 5);
SWAP(0, 4);
SWAP(0, 3);
SWAP(1, 5);
SWAP(2, 6);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);

---

Even though it takes 16 compare and swap operations, it can actually be done in 6 parallel steps (ie: it's depth) and a modern compiler should be able to get close to this by utilizing CPU pipelines. Overall, for very small n I've always found them to be the most efficient sort in terms of CPU cycles.

Juk

Post Extras