-
Notifications
You must be signed in to change notification settings - Fork 0
Counting Sort
Note: largest_value = Value of greatest integer in array.
This version of Counting Sort (which I got from here) is most likely the fastest possible sorting algorithm for numbers. It only works on the set of natural numbers, and negative integers would cause it to fail.
This implementation of Counting Sort is one that completely prioritizes speed over memory usage. Its buckets are based on the individual values, and not the most significant digit or some other identifier like other implementations. The number of buckets is equal to the largest integer in the array. Its time complexity varies greatly depending on the value of the greatest element in the array.
The largest_value could be 10. Or it could be Integer.MAX_VALUE. We don't know up front.
It splits elements into "buckets" based on their values. It basically counts how many of each value exists, and place that count in buckets. The index in the array of buckets is the elements value.
Let's say we have the following array:
4, 1, 5, 1, 9
Bucket sort would create ten buckets for this (because 9 is the greatest value). It would then count the number of each value, and place them at the index of that value, in a bucket array. It starts the buckets array at all 0s.
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
There is one 4 in the array. So it increments index 4 (the fifth element) in the buckets array.
Original array: 4, 1, 5, 1, 9
Bucket Array: 0, 0, 0, 0, 1, 0, 0, 0, 0, 0
Then the next item in the original array is 1. So it increments index 1 (the second element).
Original array: 4, 1, 5, 1, 9
Bucket Array: 0, 1, 0, 0, 1, 0, 0, 0, 0, 0
Then the next item in the original array is 5. So it increments index 5 (the sixth element).
Original array: 4, 1, 5, 1, 9
Bucket Array: 0, 1, 0, 0, 1, 1, 0, 0, 0, 0
Then the next item in the original array is 1. So it increments index 1 (the second element).
Original array: 4, 1, 5, 1, 9
Bucket Array: 0, 2, 0, 0, 1, 1, 0, 0, 0, 0
Then the next item in the original array is 9. So it increments index 9 (the tenth element).
Original array: 4, 1, 5, 1, 9
Bucket Array: 0, 2, 0, 0, 1, 1, 0, 0, 0, 1
The bucket array has been completed. Now it places items back into a new array based on their indices. Index 0 has no items. Index 1 (the second element) has two items. Since it is index 1, it places the value 1 into the new array twice, starting at the left.
New array: 1, 1, -, -, -
Bucket Array: 0, 2, 0, 0, 1, 1, 0, 0, 0, 1
Next, it keeps going. It finds that at index 4 there is a 1 in the Bucket Array, so it places one 4 in the array at the next index.
New array: 1, 1, 4, -, -
Bucket Array: 0, 2, 0, 0, 1, 1, 0, 0, 0, 1
Next, it finds a 1 at index 5, so it places one 5 next in the new array, immediately after the element it just placed.
New array: 1, 1, 4, 5, -
Bucket Array: 0, 2, 0, 0, 1, 1, 0, 0, 0, 1
Finally, it sees the 1 in the Bucket Array at index 9. So it places a 9 into the new array.
New array: 1, 1, 4, 5, 9
The array is now sorted.