Suche Algorithmus, um ein Array nach links auszurichten



  • Hallo Community,

    der Threadtitel ist velleicht etwas verwirrend, aber ich weiß nicht, wie ich es sonst nennen sollte.

    Ich habe folgendes Problem:
    Ich habe ein Array, welches entweder die Länge 6 oder 7 besitzt. In diesem Array sind integer gespeichert, die Zustände repräsentieren.

    Sei das gegebene Array meinetwegen (-1, 1, 1, -1, 2, 3).

    Jetzt suche ich eine Möglichkeit, möglichst effizient die Zahlen >0 nach links rücken zu lassen.
    Das Resultat wäre dann (1, 1, 2, 3, -1, -1)
    Also dass die -1 wegfallen und die Zahlen rechts "nachrücken". Versteht ihr, was ich meine?

    Meine Idee war:

    Es können ja maximal size()/2 "Löcher" entstehen. Demnach erstelle ich ein Array oder Vector mit dieser Größe, und alle Werte dieses Vektors werden vorerst mit 0 initialisiert. Gleichzeitig initialisiere ich einen Zähler für diesen Vektor (k). Dieser Vector beinhaltet an der k. Stelle die zusammenhängenden Löcher + die vorherigen Löcher

    Bei dem oben gegebenen Array sollte der Vektor also am Ende so aussehen:
    (1, 2, 2)

    D.h. es sind von links 1 Element frei. Damit die Zahlen hinter dem 2. Loch aber richtig verschoben werden, müssen die ja um 1 (erstes Loch) und noch 1 (zweites Loch) verschoben werden. Ich hoffe, mein Gedankengang ist verständlich.

    Jetzt gehe ich in eine Schleife, die jedes Element des zu rückenden Arrays durchgeht. Im Schleifendurchlauf wird getestet, ob der Wert eine -1 ist. Wenn dem so ist, soll das vektorelement[k] um eins erhört werden.

    Wenn dem nicht so ist, soll geprüft werden, ob vektor[k]=vektor[k-1] ist. Denn dann sind ja zwei aufeinanderfolgende Elemente gefunden und der Zähler soll nicht erhöht werden. Ist dem nicht so, wird k um eins erhöht.
    Leider funktioniert der Algorithmus leider nicht so, wie ich es mir vorstellen, habt ihr da eine bessere Idee, wie ich mein Problem löse?

    Hier mal mein Code:

    const int LEN=6;
    
        int a[LEN]={-1, 1, 1, -1, 2, 3};
        int size=LEN;
    
        vector<int> abstand(LEN/2);
    
        for(int i=0;i<LEN/2;i++) { abstand[i]=0; } // Alle Elemente des Vektors sollen 0 sein
    
        // In dieser Schleife wird nach Luecken gesucht und im Vektor
        // gespeichert
        for(int k=0;k<LEN;k++) { // gehe jedes einzelne Element durch
    
            if(a[k]==-1) { // es wurde eine -1 gefunden
    
                abstand[k]++;
    
            } else {
    
                if(k!=0) {
    
                    // Hier wird geprueft, ob bisher "neue" Luecken dazugekommen sind
                    // Wenn die Zahlen gleich sind, wurden 2 aufeinanderfolgende Zahlen
                    // >0 entdeckt, und es wird das nächste Element betrachtet
                    if(abstand[k]==abstand[k-1]) {
                        continue;
                    } else {
                        abstand[k]=abstand[k-1];
                    }
    
                }
    
            }
    
        }
    

    Jetzt weiß ich aber noch nicht genau, wann ich alles verschieben soll? Am Ende in einer neuen Schleife oder schon während des Suchprozesses?

    Oder ist mein Ansatz komplett daneben?



  • Habe kaum was verstanden, nur das (1, 1, 2, 3) ging noch.
    Warum Du auf (1, 2, 2) kommen willst, ist mir nicht klar.

    Das (1, 1, 2, 3) würde ich inplace erzeugen.

    #include <iostream>
    #include <alcorithm>
    
    using namespace std;
    
    int main()
    {
        const int LEN=6;
        int a[LEN]= {-1, 1, 1, -1, 2, 3};
    
        int newlen=0;
        for(int i=0; i!=LEN; ++i)
            if(a[i]>=0)
                swap(a[newlen],a[i]),++newlen;
    
        for(int i=0; i!=newlen; ++i)
            cout<<a[i]<<' ';
        cout<<'\n';
    }
    

  • Mod

    Ich bin mir nicht ganz sicher, ob ich dich richtig verstanden habe. Meinst du so:

    #include <iostream>
    #include <algorithm>
    
    template<typename T> void range_links_ausrichten(T begin, T end)
    {
      while(begin != end)
        {
          if (*begin<0)  // Tauschen mit Ende
            {
              --end;     // end zeigt hinter das Ende, daher erstmal eins abziehen
              std::swap(*begin, *end);
            }
          else
            ++begin;     // Ansonsten eins weitergehen
        }
    }
    
    int main()
    {
      const int LEN=6;
    
      int a[LEN]={-1, 1, 1, -1, 2, 3};
      int size=LEN;
    
      range_links_ausrichten(&a[0], &a[LEN]);
    
      for(int i=0; i<LEN; ++i) std::cout<<a[i]<<" ";
      std::cout<<'\n';
    
    }
    

    Auf die Weise braucht man maximal LEN Durchgänge.

    edit: Och, volkard. Jetzt wo du wieder da bist, muss ich mich viel mehr beeilen mit meinen Lösungen 🙂 . Meine ist quasi identisch mit deiner, aber dafür habe ich algorithm richtig geschrieben :p .



  • Also der Vektor zum Speichern der Lücken war dafür gedacht, dass ich weiß, wie viele Positionen man nach links verschieben muss.

    Bei dem Array (-1, 1, 1, -1, 2, 3) müssten ja die 2 und die 3 um 2 Positionen nach links verschoben werden müssen. Warum dann das letzte Element vom Vektor 2 ist, war wohl ein großer Denkfehler von mir.
    Dieser Algorithmus funktioniert natürlich und ist um weiten schneller. Danke jedenfalls, so einfach kann es gehen. (Ich hatte zwar über swap gedacht, aber wusste nicht, wie ich da die alte und neue Position bestimmen kann.)



  • Warum von hand sortieren? Dafür gibts doch sort 😉

    #include <iostream>
    #include <algorithm>
    
    //moeglichkeiten:
    // - + ---> false
    // + - ---> true
    // + + ---> less
    // - - ---> less
    
    template <typename Num>
    bool positive_lesser_negative(Num const& lhs, Num const& rhs)
    {
      return !(lhs<0 && rhs>0) && (lhs>0 && rhs<0) || (lhs<rhs);
    }
    
    int main()
    {
      const int LEN=6;
    
      int a[LEN]={-1, 1, 1, -1, 2, 3};
    
      std::sort(a, a+LEN, positive_lesser_negative<int>);
    
      for(int i=0; i<LEN; ++i) std::cout<<a[i]<<" ";
      std::cout<<'\n';
    }
    


  • Es gibt etliche Möglichkeiten, einen O(n)-Algo aus std dazu zu benutzen. Manche wie std::partition klingen naheliegender als andere. Aber std::sort begeistert mich hier nicht.


  • Mod

    Aber das Sortierproblem ist dadurch dass nur 2 "Werte" (negativ und nicht negativ) vorkommen können sehr stark vereinfachbar gegenüber dem sort aus der STL. Ich mag es nicht, solche Zusatzinformationen ungenutzt zu lassen.

    edit: Ach, zweimal im gleichen Thread kommt volkard mir mit einer fast gleichen Antwort zuvor.



  • pumuckl, besser stable_sort . Oder noch besser stable_partition . Oder gleich remove_if , es hört sich so an, als würden die negativen Elemente nicht mehr gebraucht.



  • volkard schrieb:

    Es gibt etliche Möglichkeiten, einen O(n)-Algo aus std dazu zu benutzen. Manche wie std::partition klingen naheliegender als andere. Aber std::sort begeistert mich hier nicht.

    Zugegeben, sd::partition wäre hier wohl ausreichend, da er die Negativen ja ganz weg haben möchte.



  • std::erase verschiebt die zutreffenden Elemente (<=0) ans Ende.



  • fdfdg schrieb:

    std::erase verschiebt die zutreffenden Elemente (<=0) ans Ende.

    Nein.



  • Ups, ich meinte std::remove_if.



  • fdfdg schrieb:

    Ups, ich meinte std::remove_if.

    Ne, auch nicht. Sorry, ich probier erst mal aus, bevor ich hier weiter rede.


Log in to reply