Wektor o długości n nieuporządkowany

0

Hej witam wszystkich , zwracam się z prośbą o pomoc w zadaniu .
Na 1-wszym roku dostaliśmy zadanie z algorytmów które brzmi następująco

Dana jest nieuporządkowana tablica jednowymiarowa (wektor) o długości n. Tablica
ta zawiera tylko dwa rodzaje elementów. Posortuj tą tablicę w ten sposób, aby
złożoność obliczeniowa algorytmu była jak najmniejsza. Sortowanie wykonaj za
pomocą przestawiania odpowiednich elementów i bez używania pomocniczej tablicy.
Np. jeśli tablica jest typu całkowitego i zawiera tylko elementy o wartości 0 i 1 ,
{0,1,1,0, .....0,1,0} to po uporządkowaniu jest postaci {0,0,0,........,1,1,1}.

Nie programowałem w żadnym języku i jest możliwość zrobienia tego zadania w formie opisowej z narysowaniem diagramu

Czy ktoś jest w stanie mi pomóc z tym zadaniem ?
Od czego zacząć i jaką metodą je rozwiązać .

Rozumiem z zadania (chyba), że mogę z góry założyć że 1 >0 , i chce uzyskać algorytm o najmniejszej złożoności obliczeniowej.

Myślałem o sortowaniu bąbelkowym ale nie wiem czy jest to najlepsza droga...

dodanie znacznika <quote> - @furious programming

1

Prosty algorytm "autobus w polu" - dziewczynki na lewo, chłopcy na prawo.
Czasami nazywany - algorytm "Flaga Polska".

1

Każdy element 0 musi być na lewo od każdego elementu 1, więc lecisz dwoma indeksami, jeden od lewej, drugi od prawej. Jeśli lewy indeks spotyka jakiś element 1 to zamieniasz z elementem 0, który spotyka indeks prawy. Kończysz gdy oba indeksy się spotkają.

0

A jak coś takiego w pseudokodzie przedstawić?

0

Witam, ponownie udało mi się sklecić diagram pseudokod i opis słowny , kolega napisał mi to w c++ i wszystko działa <sukces> :)
Dzięki wszystkim za podpowiedzi , ale mam jeszcze jedno pytanie .
Do zadania muszę opisać jaką złożoność pamięciową i czasową ma mój algorytm,
czy mógłbym prosić o podpowiedzi ?

Mój kod:

 
#include <iostream>

using namespace std;
int main() {
	int n;
	cout<<"Podaj dlugosc tablicy:\n ";
	cin>>n;
	int tab[n];
		for	(int k=0; k<n; k++)
			{ cout<<"Prosze podac znak:\n";
			cin>>tab[k];			
			}	
		for	(int k=0; k<n; k++)
		{
			cout<<tab[k]<<" ";
		}
		cout<<endl<<"Flaga polska:\n ";		
		int i,j,z;
		i=0;
		j=n-1;
		while (i<j)
			{
				while (tab[j]==1) j--;
				while (tab[i]==0) i++;
						if (i<j)
							{
							z=tab[i];
							tab[i]=tab[j];
							tab[j]=z;
							i++;
							j--;
							}
			}
			cout<<"Podana, posortowana tablica to:\n";
				for	(int k=0; k<n; k++)z
					{
					cout<<tab[k]<<" ";
					}					
}
1

Wcięcia wołają o pomstę do nieba! Używaj formaterów typu: http://format.krzaq.cc/

Masz tylko 1 tablicę o wielkości n i jakieś pojedyncze zmienne, więc pamięciowo masz O(n).
4 razy przelatujesz przez tablicę wielkości n, więc czasowo też masz O(n).

0

A co jest tutaj operacją dominującą i skąd wiadomo że "4 razy przelatujesz przez tablicę wielkości n" ? Przepraszam za noobskie pytania ... :/

0

No to popatrz na kod.
Pierwszy raz przelatujesz jak robisz cin >> tab[k]
Drugi przy cout<<tab[k]<<" ";
Trzeci przy właściwym algorytmie.
Ostatni jak wypisujesz cout<<tab[k]<<" ";

Jako dominującą przyjąłbym tutaj porównanie wartości tablicy (tab[j] == 1 i tab[i] == 0)

0

Tu akurat nie masz racji, dominujące zdecydowanie: - cout<<tab[k]<<" "; - każdy profiler ci to powie.

0

Pod względem czasu wykonania tak, ale to nie jest potrzebne w jego algorytmie. A rozumiem, że on chce to oszacować dla swojego algorytmu.

0

Chodzi mi głównie o ten element kodu , czy tu nie ma dwóch pętli while w jednej dużej pętli while ? Czy złożoność nie powinna być O(n^2)

 
cout << endl << "Flaga polska:\n ";
int i, j, z;
i = 0;
j = n - 1;
while (i < j) {
    while (tab[j] == 1)
        j--;
    while (tab[i] == 0)
        i++;
    if (i < j) {
        z = tab[i];
        tab[i] = tab[j];
        tab[j] = z;
        i++;
        j--;
    }
}
1

No to w takim razie wprowadzenie i wyświetlenie nie należy do samego algorytmu, więc w takim razie to

twonek napisał(a):

... 4 razy przelatujesz przez tablicę wielkości n ...
nie jest prawda bo przelatuje tylko raz.

1
_13th_Dragon napisał(a):

No to w takim razie wprowadzenie i wyświetlenie nie należy do samego algorytmu, więc w takim razie to

twonek napisał(a):

... 4 razy przelatujesz przez tablicę wielkości n ...
nie jest prawda bo przelatuje tylko raz.

Masz rację. Napisałem o 4 przejściach przed jego pytaniem o operację dominującą. W momencie gdy już patrzymy tylko na właściwy algorytm to jest tylko jedno przejście.

Chodzi mi głównie o ten element kodu , czy tu nie ma dwóch pętli while w jednej dużej pętli while ? Czy złożoność nie powinna być O(n^2)
Nie, bo i nigdy nie będzie większe od j. Inaczej mówiąc te małe pętle nigdy nie przelatują przez całą tablicę. Co więcej suma ich przejść wynosi z grubsza tyle ile elementów ma tablica.

0

Czyli końcem końców złożoność czasowa to O(n) , a elementem dominującym będzie tutaj operacja sprawdzania

while (tab[j]==1) j--;

oraz

while (tab[i]==0) i++;

Ilośc tych sprawdzeń jest proporcjonalna do długości tablicy więc złożoność jest liniowa ?

dodanie znaczników <code class="cpp"> - @furious programming

0

Dzięki bardzo za pomoc wszystkim ! <dziekuje>

1 użytkowników online, w tym zalogowanych: 0, gości: 1