I figured I'd get a rise out of someone with an O(n) bubble sort. My sort:
- Code: Select all
void SortBubble(s_move *pm1, s_move *pm2, int num) {
int swap;
s_move temp, *pm;
pm2--; //last move
while (pm1 < pm2) {
pm = pm2;
swap = FALSE;
while (pm > pm1) {
if (pm->val > (pm-1)->val) {
temp = *pm;
*pm = *(pm-1);
*(pm-1) = temp;
swap = TRUE;
}
pm--;
}
num--;
if (!swap || !num) return;
pm1++;
}
}
If I'm sorting root moves or a short list of captures I'll call it with num=0 and it is a standard bubble sort. But for normal search all moves I call it with num=5 or so.
We could argue best way to sort till the cows come home, but I figure, like Sune, if I'm not going to get a cutoff in the first few moves I'm not going to get one at all. My method actually produces a few less nodes than a full sort. This puzzled me at first till I figured out what was going on. With a full sort the losing captures went down to the rock bottom of the list. With a partial sort they end up around the middle of the list. Due to SEE inaccuracys some of those losing captures aren't really losing and they produce more cutoffs than other do-nothing moves.
Dan H.
