Suche Algorithmus, um ein Array nach links auszurichten

Fabulus

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

pumuckl

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';
}

volkard

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.

SeppJ

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.

Bashar

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.

pumuckl

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.

volkard

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.