Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Sorts array of n values.
- */
- void sort(int values[], int n)
- {
- // At Zamyla's suggestion, we implement the Counting Sort algorithm
- // Step 1: Zero-initialize array of LIMIT size.
- static int count[65537];
- int output[n];
- // Step 2: increment the counting element at index values[i] each
- // time that value appears in values.
- for (int i = 0; i < n; i++) {
- count[values[i]]++;
- }
- // Step 3: To determine where to place each element, we can calculate the
- // number of elements with a lower value, we do this by incrementing each
- // value in the count array by the previous value.
- for (int i = 1; i <= LIMIT; i++) {
- count[i] += count[i - 1];
- }
- // Step 4: Place each item in the input array at the index of the output
- // array that was specified in the count array, subtracting 1 from the
- // counting array value each time so we avoid overwriting.
- for (int i = n; i >= 0; i--) {
- output[count[values[i]]] = values[i];
- if (count[values[i]] > 0) count[values[i]]--;
- }
- // Step 5: Copy values from output array to input array
- for (int i = 0; i < n; i++) {
- values[i] = output[i];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement