Rearranges the array of w-character strings in ascending order. `a` the array to be sorted `w` the number of characters per string
(a: &mut [T], w: usize)
| 50 | /// `a` the array to be sorted |
| 51 | /// `w` the number of characters per string |
| 52 | pub fn sort<T: AsRef<str> + Copy>(a: &mut [T], w: usize) { |
| 53 | let n = a.len(); |
| 54 | |
| 55 | // a[0] just for init helper, no practical significance |
| 56 | let mut aux = vec![a[0]; n]; |
| 57 | |
| 58 | for d in (0..w).rev() { |
| 59 | // sort by key-indexed counting on d-th character |
| 60 | |
| 61 | // compute frequency counts |
| 62 | let mut count = [0; R_ASCII + 1]; |
| 63 | for it in a.iter().take(n) { |
| 64 | let c = it.as_ref().as_bytes()[d]; |
| 65 | count[c as usize + 1] += 1; |
| 66 | } |
| 67 | |
| 68 | // compute cumulates |
| 69 | for r in 0..R_ASCII { |
| 70 | count[r + 1] += count[r]; |
| 71 | } |
| 72 | |
| 73 | // move data |
| 74 | for it in a.iter().take(n) { |
| 75 | let c = it.as_ref().as_bytes()[d]; |
| 76 | aux[count[c as usize]] = *it; |
| 77 | count[c as usize] += 1; |
| 78 | } |
| 79 | |
| 80 | // copy back |
| 81 | a[..n].clone_from_slice(&aux[..n]); |
| 82 | } |
| 83 | } |
| 84 | |
| 85 | pub fn sort_i32(a: &mut [i32]) { |
| 86 | let BITS = 32; |