-
Notifications
You must be signed in to change notification settings - Fork 195
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Implement counting sort for boolean and byte arrays #132
Comments
You are absolutely right. Did you do any kind of benchmark? |
@vigna After glancing at this issue, I was inspired and devised a method of sorting a public static void sort(boolean[] booleans) {
sort(booleans, 0, booleans.length - 1);
}
public static void sort(boolean[] booleans, int fromIndex, int toIndex) {
// Add appropriate range check before attempting to sort
for (int head = fromIndex, tail = toIndex; tail > head; tail--) {
if (booleans[tail]) {
continue;
}
// Move 'head' to first 'true' element in the array
while (!booleans[head]) {
if (++head == tail) {
// The array is now sorted
return;
}
}
// Swap elements at 'head' and 'tail'
booleans[head] = false;
booleans[tail] = true;
}
} |
OMG I completely lost track of that. Yes, that would be nice as a replacement for sort(). I don't understand the continue—it seems a NOP. |
@vigna I had to re-familiarize myself with what I had written since it's been so long, but it seems that I only perform a swap when This makes sense, as all If we attempt to swap when |
Ahhhh I missed the { at the and of the for. I thought the if was the only instruction 🤦🏻♂️. |
boolean and byte types have a small enough keyspace that we can reasonably always be able to quickly allocate an array for all possible elements. (or for boolean, two ints on the stack) And you can't beat O(n) for sorting.
Maybe it can be provided for short too, with a warning in Javadoc that this may allocate a lot more memory then the size of the array for small arrays.
The text was updated successfully, but these errors were encountered: