Quicksort ins Template

apfelkuchen

Hallo. Wir auf der uni haben eine aufgabe bekommen einen quicksort code in c++ mit der benutzung eines templates zu schreiben.

Der Kollege aus der Gruppe hat den Quicksort code schon geschrieben, nur sind wir beim Template stecken geblieben.

Kann mir jemand helfen dieses Problem zu lösen?

das template:

http://farukp.com/cpp/AbstractContainer.h

und unser code:

http://farukp.com/cpp/Quick.cpp
http://farukp.com/cpp/Quick.h
http://farukp.com/cpp/quicksort.cpp

Ich bin durchaus dankbar für jede hilfe!!

golden_jubilee

ich habe mal nach altem code geguckt und siehe da ich hab das auch mal gemacht und sogar mit template
naja jedenfalls biste dir sicher, dass du das geschrieben hast, die kommentare sind jedenfalls untypisch für einen deutschen studenten

naja ich hoffe es funktioniert

#include "StdAfx.h"

template<class T>

class CQuick_Sort {

public:

	CQuick_Sort(vector<T> v)
	{		
		m_vector = v;
	};

	~CQuick_Sort(void){};

	vector<T> output(void)
	{
	sortieren(0 ,m_vector.size()-1);

	/*for(unsigned int i = 0; i < m_vector.size(); i++)
	{
	cout << m_vector.at(i)<<endl;
	}*/
	return m_vector;

	}

private:	void sortieren( int pli, int pre)
	{
		int testwert = 0;

		int li = pli;
		int re = pre;

		testwert  
			=(m_vector.at(pli) + m_vector.at(pre)) /2;

		while(li <= re)
		{
			while(m_vector.at(li) < testwert)
			{
				li +=1;
			}
			while(m_vector.at(re)> testwert)
			{
				re -=1;

			}
			if(li <= re)
			{

/*
				T temp = m_vector.at(li);
				m_vector.at(li) = m_vector.at(re);
				m_vector.at(re) = temp;
*/
				T temp = m_vector[li];
				m_vector[li] = m_vector[re];
				m_vector[re] = temp;

				li +=1;
				re -=1;

			}
		}
		if(pli< re)
		{
			sortieren(pli, re);
		}

		if(li < pre)
		{
			sortieren(li, pre);
		}

	}
private:

	vector<T> m_vector;

};

Jester

steff3, bist Du sicher, daß der Code korrekt ist? Der sieht mir ziemlich labil aus.

Was macht er aus folgendem Array: {100000,3,2,1,0}?

Im ersten Durchlauf mir wird die 0 mit der 100000 vertauscht. Im zweiten Durchlauf dann wir li so lange weiter erhöht, wie m_vector.at(li) < testwert gilt. Und das gilt ab dann immer. Er läuft also über's Ende raus, es fliegt ne Exception beim at und das Array ist nicht sortiert.

Übersehe ich jetzt grad was wichtiges? Ich hab grad keine Lust das zu testen, aber für micht sieht das Teil falsch aus.

golden_jubilee

keine ahnung ob das stimmt, der code ist alt, hat aber damals scheinbar funktioniert - vlt nur für bestimmte werte

apfelkuchen

steff3 schrieb:

ich habe mal nach altem code geguckt und siehe da ich hab das auch mal gemacht und sogar mit template
naja jedenfalls biste dir sicher, dass du das geschrieben hast, die kommentare sind jedenfalls untypisch für einen deutschen studenten

naja ich hoffe es funktioniert

#include "StdAfx.h"

template<class T>

class CQuick_Sort {

public:

	CQuick_Sort(vector<T> v)
	{		
		m_vector = v;
	};

	~CQuick_Sort(void){};

	vector<T> output(void)
	{
	sortieren(0 ,m_vector.size()-1);

	/*for(unsigned int i = 0; i < m_vector.size(); i++)
	{
	cout << m_vector.at(i)<<endl;
	}*/
	return m_vector;

	}

private:	void sortieren( int pli, int pre)
	{
		int testwert = 0;

		int li = pli;
		int re = pre;

		testwert  
			=(m_vector.at(pli) + m_vector.at(pre)) /2;

		while(li <= re)
		{
			while(m_vector.at(li) < testwert)
			{
				li +=1;
			}
			while(m_vector.at(re)> testwert)
			{
				re -=1;

			}
			if(li <= re)
			{

/*
				T temp = m_vector.at(li);
				m_vector.at(li) = m_vector.at(re);
				m_vector.at(re) = temp;
*/
				T temp = m_vector[li];
				m_vector[li] = m_vector[re];
				m_vector[re] = temp;

				li +=1;
				re -=1;

			}
		}
		if(pli< re)
		{
			sortieren(pli, re);
		}

		if(li < pre)
		{
			sortieren(li, pre);
		}

	}
private:

	vector<T> m_vector;

};

Hallo Steff3. Bei meinem Kollegen in der Gruppe handelt es sich nicht um einen Deutschen Studenten. Wir machen das zu Zweit. Was die Kommentare heissen sollen, kann ich immer nachfragen.

apfelkuchen

Hallo!

Kann mir jemand vielleicht sagen wo ich anfangen könnte?

Danke

CStoll

Als erstes kannst du deine Funktion so entwickeln, daß sie mit int-Werten arbeitet:

void quicksort(int* start, int* ende)
{
  ...
  //sortiere alle Elemente im Bereich [start,ende[
}

Um diese Funktion für beliebige Datentypen verwenden zu können, passt du die Parametertypen und verwendeten Hilfsvariablen geeignet an:

template<typename It>
void quicksort(It start, It ende)
{
  typedef typename iterator_traits<It>::value_type;

  ...
  //Sortierung wie oben
  /*Ersetze verwendete Typen:
    int* -> It
    int  -> value_type (außer bei Zählvariablen)
  */
}

(und anschließend müsstest du nur darauf achten, daß die benötigten Operationen unterstützt werden)

PS: Zum Vertauschen von Werten bietet sich "std::swap()" an, das ist mitunter schneller als "tmp=x;x=y;x=tmp;".