sorting by smallest digit using selection sort

Question

my task is to sort an array by the smallest digit of a number using selection sort. for example: 61 < 35, because 1 < 3. in case of coincidence of digits, i have to print the smallest of 2. so this is my code:

 #include <iostream> #include <time.h> using namespace std; int smallestOfTwo(int a, int b) { if (a < b) return a; else return b; } int smallestDigit(int a) { int smallDigit = 9; while (a != 0) { if (a % 10 < smallDigit) { smallDigit = a % 10; } a /= 10; } return smallDigit; } void selectionSort(int arr[], const int size) { for (int i = 0; i < size - 1; i++) { int min = i; for (int j = i + 1; j < size; j++) { if (smallestDigit(arr[j]) == smallestDigit(arr[min])) min = smallestOfTwo(j, min); else if (smallestDigit(arr[j]) < smallestDigit(arr[min])) min = j; } if (min != i) { swap(arr[min], arr[i]); } } } int main() { srand(time(NULL)); const int size = 5; int arr[size]; for (int i = 0; i < size; i++) { arr[i] = rand() % 201; cout << arr[i] << " "; } cout << "\n--------------------------------------------------------------------------------------\n"; selectionSort(arr, size); for (int i = 0; i < size; i++) cout << arr[i] << " "; return 0; }

the problem is that for some numbers it works (for example, for 23 63 70 37 183 the output is correct: 70 183 23 37 63), but for some it doesnt work(for example, 27 26 156 178 47. the output is 156 178 27 26 47, but it should be 156 178 26 27 47 instead) and i cant figure out why. any help would be appreciated. thanks!

How to debug small programs. In addition to this, do not use random data -- use the data that actually causes the issue. The reason why you don't want to use random data to debug the problem is that random data will move the target every time you run the program. Debug data that you know gives the problem first, and when you figure that out, then you introduce random data. — PaulMcKenzie
– PaulMcKenzie, Commented Nov 13, 2020 at 20:34

Anonymous1847 · Accepted Answer · 2020-11-13 21:04:25Z

26 and 27 both have smallest digit 2, so they are equivalent and can be in any order in the result. To preserve original order, you can try looking up algorithms for "stable sort." To fall back on second smallest digit, third smallest digit, etc. you can count each digit and compare.

struct digit_counts { int counts[10]; }; digit_counts convert(int a) { digit_counts out = {}; while (a != 0) { ++out.counts[a % 10]; a /= 10; } return out; } bool operator<(const digit_counts& dc1, const digit_counts& dc2) { for (int i = 0; i < 10; ++i) { if (dc1.counts[i] > dc2.counts[i]) { return true; } else if (dc2.counts[i] > dc1.counts[i]) { return false; } } return false; }

If you want to fall back on the smaller of the two, then write your own comparison function.

bool special_less_than(int a, int b) { int small_digit_a = smallestDigit(a); int small_digit_b = smallestDigit(b); if (small_digit_a < small_digit_b) { return true; } else if (small_digit_a > small_digit_b) { return false; } else { return a < b; } }

yes, 26 and 27 both have smallest digit 2, but in this case i have to print the smallest, which is 26
@YungHurricane Instead of separating away just the key-getting (smallerDigit), separate away the whole comparison. I edited my answer.
i see your point, but i'm not quite sure how to implement this into my code. then how i should change code in that nested for loop inside the selectionSort function ?
@YungHurricane Insteadof smallestDigit(arr[j]) < smallestDigit(arr[min]) write special_less_than(arr[j], arr[min]) and instead of the equality comparison you can write !(special_less_than(arr[j], arr[min])) && !(special_less_than(arr[min], arr[j])).

Collectives™ on Stack Overflow

sorting by smallest digit using selection sort

1 Answer 1

4 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Related