Wektor o długości n nieuporządkowany

2014-11-18 09:15
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

edytowany 2x, ostatnio: furious programming, 2014-11-18 12:41

Pozostało 580 znaków

2014-11-18 09:23
1

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-11-18 09:43
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ą.

Pozostało 580 znaków

2014-11-19 17:05
Vryndo
0

A jak coś takiego w pseudokodzie przedstawić?

Pozostało 580 znaków

2014-11-19 17:20
0

http://bit.ly/1uwbp9C


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-08 15:39
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]<<" ";
                    }                   
}

Pozostało 580 znaków

2015-01-08 15:49
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).

Pozostało 580 znaków

2015-01-08 21:07
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 ... :/

edytowany 3x, ostatnio: Vikmar, 2015-01-09 15:15

Pozostało 580 znaków

2015-01-09 15:25
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)

Pozostało 580 znaków

2015-01-09 15:31
0

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-09 15:35
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.

Pozostało 580 znaków

Liczba odpowiedzi na stronę

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