Să se memoreze într-un vector n cifre. Să se afişeze cel mai mic număr care se poate obţine cu aceste cifre. 16
Pentru a rezolva această problemă, vom folosi un algoritm de sortare prin interschimbare, care va pune cifrele în ordine crescătoare. După aceea, vom construi numărul cel mai mic posibil prin concatenarea cifrelor în ordine.
#include <iostream>
using namespace std;
int main()
{
const int MAX_N = 100;
int n, cifre[MAX_N];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> cifre[i];
}
// Sortarea cifrelor
bool schimbat;
do {
schimbat = false;
for (int i = 0; i < n – 1; i++) {
if (cifre[i] > cifre[i + 1]) {
int tmp = cifre[i];
cifre[i] = cifre[i + 1];
cifre[i + 1] = tmp;
schimbat = true;
}
}
} while (schimbat);
// Construirea numărului cel mai mic
int start = 0;
while (start < n – 1 && cifre[start] == 0) {
start++; // Trecem peste cifrele zero
}
if (start == n – 1 && cifre[start] == 0) {
// Toate cifrele sunt zero
cout << „0\n”;
} else {
// Construim numărul cel mai mic
for (int i = start; i < n; i++) {
cout << cifre[i];
}
cout << „\n”;
}
return 0;
}
Algoritmul de sortare prin interschimbare are o complexitate O(n^2), dar pentru numere cu n de ordinul zecilor sau sutelor, acesta este suficient de eficient.