Issue with Radix MSD Sorting Algorithm
I'm trying to implement various sorting algorithms and Radix Sorting (by Most Significant Digit) is giving me a pain:
template <typename ITER>
void RadixSortGroup_MSD(ITER start, ITER end, int radix) {
std::array<std::vector<typename ITER::value_type>, 10> bins;
// split into bins
for(ITER idx = start; idx < end; ++idx) {
bins[(*(idx) / radix) % 10].push_back(*idx);
}
// compile them together again
for(auto bin : bins) {
for(auto val : bin) {
*start = val;
start++;
}
}
}
template <typename ITER>
void RadixSort_MSD(ITER start, ITER end) {
ITER max = SortAlgVis::max_element(start, end);
int size = std::to_string(*max).size();
for(int exp = size; exp >= 0; --exp) {
RadixSortGroup_MSD(start, end, pow(10, exp));
printPretty(testVec);
}
}
My code first finds the max element and then creates the bins using the MSD. However, when I run it with a vector of integers, it doesn't sort. The vector is printed every time is groups it by a power ( printPretty(testVec); ):
Sorted:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Run with radix of 100: (should not do anything because all nums are < 100)
20 6 9 11 31 15 16 13 8 12 24 1 2 30 14 7 26 29 17 19 22 0 5 28 18 23 27 3 4 25 10 21
Run with radix of 10:
6 9 8 1 2 7 0 5 3 4 11 15 16 13 12 14 17 19 18 10 20 24 26 29 22 28 23 27 25 21 31 30
Run with radix of 1:
0 10 20 30 1 11 21 31 2 12 22 3 13 23 4 14 24 5 15 25 6 16 26 7 17 27 8 18 28 9 19 29
I also implemented the LSD version of it and it works. The only change between the LSD version and the MSD version is the for loop:
for(int exp = 0; exp < size; ++exp) {
Any help would be greatly appreciated. I'm still learning C++ so, please let me know if It was something dumb.
EDIT: Heres the output with numbers up to 150
Sorted:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
Radix of 1000
67 52 138 64 87 63 2 45 103 41 60 106 135 120 78 36 37 57 101 0 46 7 128 93 100 133 96 10 81 79 119 28 24 12 97 77 91 83 149 102 125 84 88 143 69 131 58 16 33 73 25 85 122 18 29 113 61 90 19 148 99 105 115 59 11 126 22 75 9 27 98 124 141 104 127 5 31 134 118 136 89 30 109 112 14 35 110 49 95 140 123 56 20 48 13 62 142 130 137 145 146 21 23 40 147 3 65 6 107 114 70 94 39 55 71 74 43 139 66 108 72 54 50 15 53 44 4 111 132 38 116 117 32 68 26 51 80 121 1 34 86 17 92 47 82 76 42 8 129 144
Radix of 100
67 52 64 87 63 2 45 41 60 78 36 37 57 0 46 7 93 96 10 81 79 28 24 12 97 77 91 83 84 88 69 58 16 33 73 25 85 18 29 61 90 19 99 59 11 22 75 9 27 98 5 31 89 30 14 35 49 95 56 20 48 13 62 21 23 40 3 65 6 70 94 39 55 71 74 43 66 72 54 50 15 53 44 4 38 32 68 26 51 80 1 34 86 17 92 47 82 76 42 8 138 103 106 135 120 101 128 100 133 119 149 102 125 143 131 122 113 148 105 115 126 124 141 104 127 134 118 136 109 112 110 140 123 142 130 137 145 146 147 107 114 139 108 111 132 116 117 121 129 144
Radix of 10
2 0 7 9 5 3 6 4 1 8 103 106 101 100 102 105 104 109 107 108 10 12 16 18 19 11 14 13 15 17 119 113 115 118 112 110 114 111 116 117 28 24 25 29 22 27 20 21 23 26 120 128 125 122 126 124 127 123 121 129 36 37 33 31 30 35 39 38 32 34 138 135 133 131 134 136 130 137 139 132 45 41 46 49 48 40 43 44 47 42 149 143 148 141 140 142 145 146 147 144 52 57 58 59 56 55 54 50 53 51 67 64 63 60 69 61 62 65 66 68 78 79 77 73 75 70 71 74 72 76 87 81 83 84 88 85 89 80 86 82 93 96 97 91 90 99 98 95 94 92
Radix of 1
0 100 10 110 20 120 30 130 40 140 50 60 70 80 90 1 101 11 111 21 121 31 131 41 141 51 61 71 81 91 2 102 12 112 22 122 32 132 42 142 52 62 72 82 92 3 103 13 113 23 123 33 133 43 143 53 63 73 83 93 4 104 14 114 24 124 34 134 44 144 54 64 74 84 94 5 105 15 115 25 125 35 135 45 145 55 65 75 85 95 6 106 16 116 26 126 36 136 46 146 56 66 76 86 96 7 107 17 117 27 127 37 137 47 147 57 67 77 87 97 8 108 18 118 28 128 38 138 48 148 58 68 78 88 98 9 109 19 119 29 129 39 139 49 149 59 69 79 89 99
上一篇: 通过NSDate属性对对象数组进行排序
下一篇: 基于MSD排序算法的问题