Cześć!
Mam do napisania program, który ma przesunąć nieparzyste elementy tablicy na lewą stronę, a parzyste na prawą. Próbowałem czegoś takiego:
int tab [8]={1,2,3,4,5,6,7,8};
for(int i=0;i <=7; i++)
{
if (tab[i]%2==0) swap(tab[i], tab[i+1]);
}
Ale nie działa to poprawnie i w sumie nie wiem, dlaczego. Pewnie jest to banalne do napisania, ale jestem początkujący i mnie to przerasta. Ktoś pomoże?
Rozpisz swój algorytm na kartce to się przekonasz czemu nie działa. Wydaje się, że po prostu parami zamieniasz elementy miejscami, zamiast robić to co jest w poleceniu.
Poza tym co robi funkcja swap? Trochę dziwi mnie, że przekazujesz wartości zamiast indeksów i wskaźnika do tablicy.
W pseudo kodzie powinno to być coś w tym stylu:
swap(int tab[], int index1, int index2) {
int temp = tab[index1];
tab[index1] = tab[index2];
tab[index2] = temp;
}
Jest też możliwość zamiany elementów bez wykorzystywania zmiennej tymczasowej, używając masek bitowych, ale to trochę przerost formy nad treścią.
najłatwiej będzie utworzyć 2 tablice pomocnicze odpowienio dla wartości parzystych i nieparzystych i przeiterowanie ich do tablicy wynikowej
Masz oczywiście rację, ale tego typu rzeczy jednak najczęściej robi się bez dodatkowych struktur danych. W tym przypadku to nie jest nic szczególnie trudnego.
Przy 8 elementach 2x większe zużycie pamięci nie ma znaczenia. Ale jeśli masz ich powiedzmy 100 milionów, to już tak.
Nie za bardzo rozumiem pytanie. Swapujesz dwa elementy, o określonych indeksach, w podanej tablicy. Chyba, że swap to jakaś wbudowana funkcja w C. Jeśli tak to powinieneś do niej pewnie przekazać referencje (adresy w pamięci, które chcesz zamienić miejscami), a nie wartości.
Co to jest ten swap, którego używasz?
W kodzie napisałeś coś takiego. To ja pytam, czego używasz?
tak, tylko, że bez wykorzystania dodatkowej pamięci trochę sprawa się komplikuje(o ile dobrze myśle) biorę skrajne indeksy i wykonuje funkcje swap dopóki (tab[i]%2==0 && tab[tab.length()-i]%2 !=0) , ale co w przypadku gdy obie wartości są parzyste albo nieparzyste, musze wykonać kolejna petle, aż znajde wartośc parzystą/nieparzystą do zamiany i złożoność obliczeniowa rosnie, w moim sposobie będzie to zawsze 2n
Zgadzam się całkowicie, że sposób z dwoma pomocniczymi kolekcjami jest najprostszy i w jakimś nowoczesnym języku można to napisać w dosłownie w paru linijkach. Tyle, że moim zdaniem w tego typu zadaniach zupełnie nie o to chodzi. Przecież z “prawdziwym” programowaniem nie mają one praktycznie nic wspólnego. To są zadania z algorytmiki i lepszym rozwiązaniem wydaje mi się np. coś takiego:
Postawić dwa indeksy i oraz j, gdzie i wskazuje na pierwszy element tablicy, a j na ostatni.
Tablicę nazwijmy tab.
Robimy pętlę dopóki i nie jest równe j
W każdym kroku mamy dwie liczby tab[i] oraz tab[j]. Mogą one być:
pp - obie parzyste
np - pierwsze nieparzysta, druga parzysta
pn - pierwsza parzysta, druga nieparzysta
nn - obie nieparzyste
Robimy:
np - nic; i=i+1; j=j-1
pp - nic; i bez zmian; j=j-1
pn - swap; i=i+1; j=j-1
nn - nic; i=i+1; j bez zmian
Z rozpisania na kartce wychodzi mi że powinno działać.
Zlożoność O(N). Robiąc swapa za pomocą XOR, bez dodatkowego zużycia pamięci.
Faktycznie jest to wydajniejszy algorytm, ale nie uważam, żeby mój sposób nie ma nic wspólnego z tzw. prawdziwym progamowaniem, jeżeli nie ma ograniczeń co do złożoności obliczeniowej/pamięciowej i działa to w znośnej złożoności to nawet najprostszy algorytm jest dobry, a to, że autor zaprojektował zadanie pod inne rozwiązanie i nie przewidział tak oczywistego algorytmu to już inna sprawa
Przecież ja nie pisałem nic o twoim sposobie, który jest bardzo dobry, sam bym tak zrobił w 99% przypadków. Szczególnie, że zaprzęgając do tego wiele wątków byłoby to szybsze. Pisałem o tego typu zadaniach. Są one typowo algorytmiczne, a nie programistyczne. Zaprogramowanie tego w jakimś języku jest wisienką na torcie. Oczywiście C/C++ ze swoimi wskaźnikami, ręczną alokacją pamięci i brakiem prostych w użyciu kolekcji itp. jest do tego fatalny, ale z jakiegoś powodu nim męczą. Albo z drugiej strony patrząc, uczą tego ludzie, którzy nigdy nie mieli do czynienia z profesjonalnym programowaniem, gdzie złożoność leży zupełnie gdzie indziej niż algorytmy.
W nowoczesnym języku typu C# można to zadanie załatwić jedną imperatywną linijką kodu:
int[] unordered = new int[] { 2, 1, 2, 1, 2, 1, 2, 1};
int[] ordered = unordered.Where(x => x % 2 == 1)
.Concat(unordered.Where(x => x % 2 == 0))
.ToArray();
// Wynik [1, 1, 1, 1, 2, 2, 2, 2]Nie zapominaj, że świat programowania nie ogranicza się do PC 
Samodzielne implementowanie i tworzenie algorytmów w takich niskopoziomowych językach nie uczy programowania (jakiego oczekuje biznes) - uczy kreatywnego myślenia i kombinowania jak coś rozwiązać mając do dyspozycji ograniczone zasoby. Jak z jakiegoś powodu będziesz musiał sortować 20 mld obiektów to “zróbmy 2 nowe tablice i dokupmy kolejne 20GB RAMu” nie zadziała.
Można też dwiema:
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> unordered = {2, 1, 2, 1, 2, 1, 2, 1};
std::vector<int> ordered;
std::copy_if(unordered.begin(), unordered.end(), std::back_inserter(ordered),
[](int x) -> bool { return x % 2 == 1; });
std::copy_if(unordered.begin(), unordered.end(), std::back_inserter(ordered),
[](int x) -> bool { return x % 2 == 0; });
for(int v : ordered)
std::cout << v << " ";
std::cout << std::endl;
}
$ clang++ -o xx --std=c++14 xx.cpp && ./xx
1 1 1 1 2 2 2 2