OBJEDINJAVANJE - REŠENJE
#include <iostream>using namespace std;
int main()
{
int m,n,k;
cin>>m;
int A[m];
for(int i=0;i<m;i++){
cin>>A[i];
}
cin>>n;
int B[n];
k=m+n;
int C[k];
for(int i=0;i<n;i++){
cin>>B[i];
}
for(int i=0,p=0;i<m+n;i++){
if(i<m){
C[i]=A[i];
}
else{
C[i]=B[p++];
}
}
/* for(int i=0;i<k;i++){
cout<<C[i]<<endl;;
}*/
int j;
for(int i=1;i<k;i++){
int b=C[i];
for(j=i-1;j>=0;j--){
if(C[j]>b){
C[j+1]=C[j];
}
else{
break;
}
}
C[j+1]=b;
}
// cout<<"Sortiran:"<<endl;
for(int i=0;i<k;i++){
cout<<C[i]<<endl;
}
return 0;
}
Opis zadatka
Zadatak je da se spaja dva sortirana niza brojeva u jedan, koji treba takođe da bude sortiran. Ovo je uobičajen problem spajanja u sortirane nizove.
Objašnjenje koda
- Unos podataka:
- Program unosi broj učenika u grupi A (m), zatim m brojeva (poeni učenika iz grupe A).
- Zatim unosi broj učenika u grupi B (n), zatim n brojeva (poeni učenika iz grupe B).
- Inicijalizacija i unos nizova:
cin >> m;
int A[m];
for (int i = 0; i < m; i++) {
cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
Ovdje se unose dva niza A i B, sa brojem elemenata m i n respektivno. Svaki niz je već sortiran.int A[m];
for (int i = 0; i < m; i++) {
cin >> A[i];
}cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
cin >> B[i];
}Kombinovanje i sortiranje
Program kombinuje nizove A i B u jedan niz C:
int k = m + n;
int C[k];
for (int i = 0; i < m; i++) {
for (int i = 0, p = 0; i < n; i++) {
Zatim se niz C sortira pomoću sortiranja umetanja:int C[k];
for (int i = 0; i < m; i++) {
C[i] = A[i];
}for (int i = 0, p = 0; i < n; i++) {
C[m + i] = B[i];
}
int j;
for (int i = 1; i < k; i++) {
Ispis rezultata:for (int i = 1; i < k; i++) {
int b = C[i];
for (j = i - 1; j >= 0 && C[j] > b; j--) {
C[j + 1] = b;
}for (j = i - 1; j >= 0 && C[j] > b; j--) {
C[j + 1] = C[j];
}C[j + 1] = b;
for (int i = 0; i < k; i++) {
cout << C[i] << endl;
}
Komentar za kod
Kod je skoro ispravan, ali postoji greška u kombinovanju nizova. Trebalo bi da se koristi metoda "spajanje sortirane liste" umesto sortiranja celog niza nakon spajanja, jer su ulazni nizovi već sortirani.
Optimizacija:
S obzirom da su ulazni nizovi već sortirani, možete koristiti efikasniji algoritam za spajanje, što je O(m + n), umesto O((m + n)²) koji se koristi u trenutnom kodu. Ovo se može postići koristeći dva pokazivača za prolazak kroz nizove A i B.
Optimizovan kod
#include < iostream >
using namespace std;
int main() {
using namespace std;
int main() {
int m, n;
cin >> m;
int A[m];
for (int i = 0; i < m; i++) {
cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
int i = 0, j = 0;
while (i < m && j < n) {
while (i < m) {
while (j < n) {
return 0;
}cin >> m;
int A[m];
for (int i = 0; i < m; i++) {
cin >> A[i];
}cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
cin >> B[i];
}int i = 0, j = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
}
cout << A[i++] << endl;
} else {
cout << B[j++] << endl;
}while (i < m) {
cout << A[i++] << endl;
}while (j < n) {
cout << B[j++] << endl;
}return 0;
Objašnjenje optimizovanog koda
- Inicijalizacija i unos: Unos podataka je isti kao u prvom kodu.
- Spajanje i ispis:
- Koristimo dva pokazivača i i j za prolazak kroz nizove A i B.
- Upoređujemo trenutne elemente i ispisujemo manji, dok ne obradimo jedan od nizova.
- Nakon toga, ispisujemo preostale elemente iz preostalih nizova.