#include "StdAfx.h"
template<class T>
class CHeap_Sort
{
public:
CHeap_Sort(vector<T> v) {
m_vector = v;}
~CHeap_Sort(void) {};
vector<T> sortieren(void)
{
m_size = m_vector.size();
buildHeap(m_size);
while (m_size >1)
{
m_size--;
change (0, m_size);
downheap (0);
}
return m_vector;
}
private:
void change(int x, int y){//keine fragen
T temp = m_vector[x];
m_vector[x] = m_vector[y];
m_vector[y] = temp;
}
void buildHeap(int n){//solange wie root >0 wird immer wieder ein neuer heap gebaut
for (int x=n/2-1; x>=0; x--){
downheap (x);
}
}
void downheap(int v)
{
int child=2*v+1; // das erste kind
while (child<m_size)
{
if (child+1 < m_size){ // wenn kind +1 < size dann muss daneben noch eins sein
if (m_vector[child+1]>m_vector[child])
child++;
/*wenn ja dann vetausche sie , so dass das linke das größte ist*/
}
if (m_vector[v]>=m_vector[child]) {//wenn die wurzel größer als das linke ist, dann ist alles okay
return; //isn super heap
}
change(v, child); // sonst tauschen und nochmal gucken
v=child; // weiterrutschen
child=2*v+1;
}
}
vector<T> m_vector;
unsigned int m_size;
};
#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;
};
#include "StdAfx.h"
template<class T>
class CSelection_Sort
{
public:
//CSelection_Sort();
CSelection_Sort(vector<T> a)
{
m_vector = a;
};
~CSelection_Sort(void){};
/*void output()
{
sortieren();
for(unsigned int i = 0; i < m_vector.size(); i++)
{
cout << m_vector.at(i)<<endl;
}
}*/
vector<T> sortieren(void)
{
for(unsigned int i = 0; i < m_vector.size()-1; i++)
{
int x = i;
for(unsigned int j = i+1; j < m_vector.size(); j++)
{
if(m_vector.at(x) > m_vector.at(j))
{
x = j;
}
}
{
T temp;
temp = m_vector[i];
m_vector[i] = m_vector[x];
m_vector[x] = temp;
/*temp = m_vector.at(i);
m_vector.at(i) = m_vector.at(x);
m_vector.at(x) = temp;*/
}
}
return m_vector;
}
private:
vector<T> m_vector;
};
#include "StdAfx.h"
template<class T>
class CInsertion_Sort
{
public:
//CInsertion_Sort();
CInsertion_Sort(vector<T> v)
{
m_vector = v;
};
~CInsertion_Sort(void){};
/*void output()
{
sortieren();
for(unsigned int i = 0; i < m_vector.size(); i++)
{
cout << m_vector.at(i)<<endl;
}
}*/
vector<T> sortieren(void)
{
int k = 0;
T x;
for(unsigned int j = 1; j < m_vector.size(); j++)
{
x = m_vector.at(j);
k = j-1;
while( k >= 0 && x < m_vector.at(k))
{
m_vector[k+1] = m_vector[k];
/*m_vector.erase(m_vector.begin() +k+1);
m_vector.insert(m_vector.begin()+k+1,m_vector.at(k)); */
k = k-1;
}
m_vector[k+1] = x;
/*m_vector.erase(m_vector.begin() +k+1);
m_vector.insert(m_vector.begin()+k+1,x);*/
}
return m_vector;
}
private:
vector<T> m_vector;
};
#include <vector>
using namespace std;
template<class T>
class CBubble_Sort
{
public:
//CBubble_Sort() {};
CBubble_Sort(vector<T> v)
{
m_vector = v;
};
~CBubble_Sort(void){};
vector<T> sortieren(void)
{
bool bbreak = true;
for(unsigned int j = 0; j < m_vector.size(); j++)
{
for(unsigned int i = 0; i < m_vector.size()-1; i++)
{
if(m_vector.at(i) > m_vector.at(i+1))
{
T temp;
temp = m_vector.at(i);
m_vector.at(i) = m_vector.at(i+1);
m_vector.at(i+1) = temp;
bbreak = false;
}
}
if(bbreak == true)
{
break;
}
}
return m_vector;
}
private:
vector<T> m_vector;
};
[quote][/quote]