Przesunięcie elementów tablicy w C++


(koot) #1

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?


(kowgli) #2

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ą.


(karnistery) #3

najłatwiej będzie utworzyć 2 tablice pomocnicze odpowienio dla wartości parzystych i nieparzystych i przeiterowanie ich do tablicy wynikowej


(kowgli) #4

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.


(koot) #5

@kowgli W swapie mogą być użyte trzy argumenty?


(kowgli) #6

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?


(koot) #7

W kodzie napisałeś coś takiego. To ja pytam, czego używasz?


(karnistery) #8

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


(kowgli) #9

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.


(karnistery) #10

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


(kowgli) #11

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]

(hindus) #12

Nie zapominaj, że świat programowania nie ogranicza się do PC :wink: 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. :wink:


(tomms) #13

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