Witam mam za zadanie napisać algorytm, którego wynikiem będzie posortowana suma dwóch zbiorów liczb całkowitych:
1- sumuję zbiór A i B - powstaje mi zbiór C
2- sortuję zbiór C:
3- zwracam posortowaną sumę dwóch zbiorów
proszę o informację czy takie rozwiązanie jest prawidłowe?
Ale co to znaczy czy prawidłowe? Czy zadziała? Tak. Czy to optymalne rozwiązanie? Nie.
To co opisałeś używa bubble sort wiec masz finalnie O((n+k)^2) złożoności. Nawet jakbyś sortował lepiej to masz O((n+k)*log(n+k)) bo sortujesz cały zbiór.
Gdybyś zbudował TreeSet ze zbioru A a następnie dodawał elementy ze zbioru B to miałbyś średnio O(n*logn)+O(k*logn(n+k/2)) czyli trochę mniej.
Gdyby zakres danych w zbiorach A i B był mały, to można by zbudować HashSet w O(n) a potem złączyć ze zbiorem B w O(k) i na koniec posortować to co zostało, bo wtedy możemy oczekiwać że rozmiar sumy zbiorów jest zblizony do rozmiaru większego z nich, czyli wszystko wykona się w O(nlogn) albo O(klogk)
A czy A i B nie są posortowane wcześniej? Jeśli tak, to da się je połączyć w czasie liniowym -- mergingiem -- https://en.wikipedia.org/wiki/Merge_algorithm