On the fly sorting algorithm or structure

Help
1

I have a list of structs produced, length between zero and almost never longer than 50.
Each struct gets a scoring value.
After that I extract the best score each time swapping the best found each time with the current index.
Kinda:

for (0..count) |index| {
    const e = extract_next_best(index);
}

Is there some datastructure which can (very fast) sort things on the fly?

EDIT:
For completeness here the extraction. In 95% of the cases we are below 30 moves.
I don’t think anything beats a hardcoded loop…

    fn extract_next(self: *MovePicker, current_idx: usize) ExtMove {
        const ptr: [*]ExtMove = &self.extmoves;
        var best_idx: usize = current_idx;
        var max_score: Value = ptr[current_idx].score;
        for (current_idx + 1..self.count) |idx| {
            const e = ptr[idx];
            if (e.score > max_score) {
                max_score = e.score;
                best_idx = idx;
            }
        }
        if (best_idx != current_idx) {
            std.mem.swap(ExtMove, &ptr[best_idx], &ptr[current_idx]);
        }
        return ptr[current_idx];
    }
1 Like
2

What are the values used to sort? Are they in a well-defined and small-ish range? If yes, you could use radix sort / bucket sort.

Otherwise, it sounds like a heap could be a good fit for the requirements.

2 Likes
3

You could calculate that when you create the list, ofc idk how you’re doing that so it might not be possible.

1 Like
4

I think the number of structs is too low to get any performance gain i saw.
The thing is: sometimes I discard - when scoring is too low - and a full sort will only cost time.

But the bucket sort would be best I think IF I am going to use it.

5

std.PriorityQueue?

3 Likes
6

i’ll check! never looked at it. thx!

7

BTW, priority queues are usually implemented with heaps, so pretty much the same suggestion.

4 Likes