Wörter nach länge im Vector sortieren ..OHNE SCHLEIFE !!!

SeppJ

Bacid90210 schrieb:

Mein Problem is erstmal wie ich überhaupt den Satz geclustert bekommen ...
Und ihn dann in den Vektor einfügen kann :-S !
Bin im moment bischen überfordert ..

Oha. Ehrlich gesagt: Dann ist die Aufgabe zu schwer für dich.

Um Wörter einzeln von der Konsole einzulesen benutzt du am besten den istream-Operator >> in Verbindung mit einem std::string. Dann wird alles automatisch nach Wörtern getrennt.

Ich wollte eigentlich gerade Rekursion als Ersatz für Schleifen vorschlagen (die Benutzung von sort ist vermutlich NICHT im Sinne der Aufgabenstellung), aber ich glaube nicht, dass du das hinbekommst.

brotbernd

den Satz geclustert bekommen... bitte was?

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main()
{
  using namespace std;
  vector<string> woerter;
  for(int i=0; i<10; ++i)
  {
    string s;
    cin >> s;
    woerter.push_back(s);
  }
  sort(woerter.begin(), woerter.end(), sortierfunktion);
  copy(woerter.begin(), woerter.end(), ostream_iterator<string>(cout,"\n"));

  return 0;
}

Die sortierfunktion darfst du noch selber schreiben;)

Bacid90210

Ich habs nun doch hinbekommen

#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

bool mysortCriterion(string s1,string s2)
{
return s1.length() < s2.length();

}

class mysorter{
public:
bool operator()(string s1, string s2){return s1.length() < s2.length();}

};

int main (int argc, char * const argv[]) {

istream_iterator<string> iit(cin);
istream_iterator<string> eos;
vector<string> v(iit,eos);
sort(v.begin(),v.end(),mysortCriterion);
sort(v.begin(),v.end(),mysorter());
copy(v.begin(),v.end(),ostream_iterator<string>(cout,";"));

return 0;
}

brotbernd

und du bist dir sicher was genau du da machst??

Fellhuhn

Doppelt sortieren hält besser?

Bacid90210

ja bin ich ...

#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

bool mysortCriterion(string s1,string s2)
{
return s1.length() < s2.length(); // returned True falls s1 kleiner s2

}

class mysorter{ // Das is mein Funktor 
public:
bool operator()(string s1, string s2){return s1.length() < s2.length();}

};

int main (int argc, char * const argv[]) {

istream_iterator<string> iit(cin); // das ist mein Istream Iterator 
istream_iterator<string> eos; // default sitream iterator aufs Ende des Istreams
vector<string> v(iit,eos); // Übergabe der Iteratoren an Konstruktor  des Vektors
sort(v.begin(),v.end(),mysortCriterion);
sort(v.begin(),v.end(),mysorter()); // Algorithmus aus STL erwartet 2 Iteraton 
und Krtiterium ind diesem falle mein Funktor , der den () Opertor unterstützen muss ...
copy(v.begin(),v.end(),ostream_iterator<string>(cout,";"));// und der rest is klar ...

return 0;
}

brotbernd

Und wieso sortierst du dann zweimal direkt hintereinander?

Fellhuhn

Ich kauf es dir nicht ab, muss ich aber auch nicht. Hoffe nur für dich das dein Lehrer/Prof/Tutor/Osterhase dir das abkauft.

SeppJ

Ich fand die Aufgabe mal interessant und habe ein Programm geschrieben, welches vollständig ohne Schleifen auskommt. Auch keine versteckten über Benutzung der Standardbibliothek. Da ich nicht annehme, dass dein Lehrer dir dies abnimmt, kann ich es wohl gefahrlos posten. Es ist bloß ein schneller Hack, es werden vermutlich einige unnötige Vektorkopien erstellt, weil ich jetzt nicht so sehr auf Optimierung geachtet habe. Wenn ich optimieren wollte, hätte ich gar nicht erst Rekursion benutzt.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void recursive_read(istream &in, vector<string> &out)
{
  string str;
  if (in >> str) 
    {
      out.push_back(str);
      recursive_read(in, out);
    }
}

void recursive_write(ostream &out, const vector<string> &in, unsigned index=0)
{
  if (index<in.size())
    {
      cout << in[index].size() << ": " << in[index] << endl;      
      recursive_write(out, in, index+1);
    }
}

void recursive_copy(const vector<string>& in, vector<string>& out, unsigned current, unsigned last)
{
  if (current==last) return;

  out.push_back(in[current]);
  recursive_copy(in, out, current+1, last);
}

void recursive_merge(const vector<string> &left, const vector<string> &right, vector<string> &merged, unsigned index_left=0, unsigned index_right=0)
{
  if ((index_left < left.size()) && (index_right < right.size()))
    {
      if (left[index_left].size() < right[index_right].size())
        {
          merged.push_back(left[index_left]);
          recursive_merge(left, right, merged, index_left+1, index_right);
          return;
        }
      else
        {
          merged.push_back(right[index_right]);
          recursive_merge(left, right, merged, index_left, index_right+1);
          return;
        }
    }
  if (index_left < left.size())
    {
      merged.push_back(left[index_left]);
      recursive_merge(left, right, merged, index_left+1, index_right);
      return;
    }
  if (index_right < right.size() )
    {
      merged.push_back(right[index_right]);
      recursive_merge(left, right, merged, index_left, index_right+1);
      return;
    }
}

vector<string> recursive_sort(const vector<string> &in)
{
  if (in.size() <= 1) return in;

  vector<string> left, right;
  unsigned middle = in.size() / 2;
  recursive_copy(in, left, 0, middle);
  recursive_copy(in, right, middle, in.size());

  left = recursive_sort(left);
  right = recursive_sort(right);

  vector<string> result;
  recursive_merge(left, right ,result);

  return result;
}

int main()
{
  vector<string> words;
  recursive_read(cin, words);
  words = recursive_sort(words);
  recursive_write(cout, words);
}

(Ok, streng genommen haben std::string, std::vector und std::istream bestimmt noch irgendwo Schleifen drin, aber man kann's auch übertreiben )

Fellhuhn

Um Rekursion zu verstehen musst du erst Rekursion verstehen.

Das mit der Rekursion geht auch eleganter unter Verwendung eines Omicronap.

class Omicronap
{
public:
	Omicronap(std::vector<std::string> & iv):v(iv),ic(v.begin()),il(ic){}
	operator bool() const
	{
		return ic != v.end();
	}
	Omicronap operator ++()
	{
		++ic;
		return *this;
	}

	Omicronap operator --()
	{
		il=v.begin();
		return *this;
	}

	Omicronap const operator --(int)
	{
		Omicronap tmp(*this);
		tmp.ic=tmp.il;
		return tmp;
	}

	Omicronap const operator ++(int)
	{
		Omicronap tmp(*this);
		if ((*ic).length()<(*il).length() )
			std::swap(*il,*ic);
		++il;
		return tmp;
	}

private:
	std::vector<std::string> &v;
	std::vector<std::string>::iterator ic;
	std::vector<std::string>::iterator il;
};

void rob(int s, Omicronap & om)
{
	switch(s)
	{
	default:
		om++;
		rob(om--,om);
	case 0:
		--om;
	}
}

void sort(Omicronap & om)
{
	rob(om--,om);
	++om;
	if(om)
		sort(om);
}

int main()
{
	std::vector<std::string> v;
	v.push_back("2fafasfasfas");
	v.push_back("dsd1");
	v.push_back("sd5dfsfsd");
	v.push_back("1");
	v.push_back("sd5dfsfsdsssssssssssss");
	v.push_back("sd5dfsfsd1");
	v.push_back("sdsdas3");

	Omicronap m(v);
	sort(m);
	copy(v.begin(),v.end(),ostream_iterator<string>(cout,"\n"));
}

Bacid90210

weil ich das ganze auch mit Hilfe einen Funktoren testen wollte ...

#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

typedef std::vector<std::string> VecType;

void sort(VecType& vec, size_t start = 0)
{
	if (vec.size() - 1 > start)
	{
		if (vec[start].length() > vec[start + 1].length())
		{
			std::swap(vec[start], vec[start + 1]);

			sort(vec, 0);
		}

		sort(vec, ++start);
	}
}

int main()
{
	VecType inVec;

	inVec.push_back("abs");
	inVec.push_back("asasdasd");
	inVec.push_back("a");
	inVec.push_back("dsabs");
	inVec.push_back("ab23423s");
	inVec.push_back("absasda");
	inVec.push_back("a12312312312bs");
	inVec.push_back("bbs");
	inVec.push_back("asdasd");

	sort(inVec);

	std::copy(inVec.begin(), inVec.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
}

He, keine Lösungen die man als Hausaufgabe abgeben kann.

SeppJ

Sehe ich das richtig? Rekursives Bubblesort?

Cool .

Athar

RekursionsFachmann schrieb:

He, keine Lösungen die man als Hausaufgabe abgeben kann.

War das eine Feststellung oder eine Aufforderung?
Im zweiten Fall: würde den Lehrer wahrscheinlich sowieso misstrauisch stimmen.