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

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.