Question

Cerinţa
Să se ordoneze crescător elementele pătrat perfect ale unui şir dat, fără a afecta elementele care nu sunt pătrat perfect.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spaţii, reprezentând elementele vectorului.
Date de ieşire
Programul afișează pe ecran, separate prin spaţii, cele n elemente ale vectorului, după sortare.
Restricţii şi precizări 1 ≤ n ≤ 1000 cele n numere citite vor fi mai mici decât 50000
Exemplu
Intrare 8 9 15 16 4 5 1 7 9
Ieșire 1 15 4 9 5 9 7 16

Answer 1

#include <iostream>
#include <cmath>
using namespace std;

int este_patrat_perfect(int n){
double radacina;
//extragem radacina
radacina=sqrt(n);
//verificam daca radacina este nr intreg
//daca da, returnam 1, nr n este patrat perfect
if(radacina-(int)radacina==0.0){
return 1;
}
else{
return 0;
}
}
void swap(int &a,int &b){
int temp;
temp=a;
a=b;
b=temp;

}
void sort_patrate_perfecte(int n,int X[]){
int i,j,stop,prim_patrat_perfect=-1,secund_patrat_perfect,el_mai_mic,curent;
for(i=0;i<n;i++){
if(este_patrat_perfect(X[i])==1&&prim_patrat_perfect>-1){
secund_patrat_perfect=i;
break;
}
else if(este_patrat_perfect(X[i])==1){
prim_patrat_perfect=i;
}
}
for(i=secund_patrat_perfect;i<n;i++){
if(este_patrat_perfect(X[i])==1){
j=i;
el_mai_mic=j;
stop=0;
while (j>prim_patrat_perfect&&stop==0){
if(este_patrat_perfect(X[j-1])==1){
if(X[j-1]>X[el_mai_mic]){
swap(X[j-1],X[el_mai_mic]);
el_mai_mic=j-1;
}
else{
stop=1;
}
}
j--;
}
}
}
}

int main(){
int n;
cin>>n;
int i,X[n];
for(i=0;i<n;i++){
cin>>X[i];
}
sort_patrate_perfecte(n,X);
for(i=0;i<n;i++){
cout<<X[i]<<" ";
}
return 0;
}