Suche Algorithmus, um ein Array nach links auszurichten


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


Anmelden zum Antworten