# Sortierverfahren (Sortieralgorithmus)



## toxice (16. Nov 2005)

Hallo,

ich muss nächste Woche ein 10-Min Referat über 3 verschiedene Sortieralgorithmen halten.

Auf jeden Fall nehmen werde ich nen BubbleSort (den Quicksort hat schon ein Kollege).

Kennt ihr gute Internet-Seiten die verschiedene und einfach zu verstehenden Sortierverfahren beschreibt (am besten noch mit Animation und JAVA-Quellcode).

Wäre euch dankbar   

MfG toxice


----------



## Guest (16. Nov 2005)

Hast du bereits unter jdk##/demo/applets/SortDemo

:bae:


----------



## bygones (16. Nov 2005)

BubbleSort, QuickSort, MergeSort

3 Stück - bei google sollte man da einiges finden


----------



## toxice (16. Nov 2005)

Wie habe ich bereits @ gast ??


Ja den BubbleSort habe ich schon im Auge, doch den QuickSort hat mein Kollege. Jeder von uns 2 muss 3 verschiedene Sortierverfahren vorstellen.

Das Referat sollte 10 Min dauern.

Habt ihr vll allgemeine Tipps wie ich das aufbauen sollte ?!

Den InsertSort - kennt ihr den ???


----------



## The_S (16. Nov 2005)

Du hast die schon in deinem JDK Verzeichnis unter dem angegeben Pfad. Zu Quicksort könnt ich dir sogar schnell nen Quellcode geben (hab den selber für eine Präsentation in der Berufsschule gebraucht), aber den kannst du ja net brauchen.


----------



## dhachim (17. Nov 2005)

nutze mal wikipedia... da findest du ne ganze menge an sortieralgos, ausführlichst mit pseudocodes und java codes oder in welcher sprache auch immer


----------



## pogo (17. Nov 2005)

und in 10 min kannst de eh net wirklich viel zu erzählen.
deshalb würde ich mich mal garnicht verrückt machen und einfach n bissel was unter wikipedia suchen und wenn de dann noch nähere infos brauchst kannst de googeln.
damit sollte man ohne probleme genug stoff zusammen bekommen.
bei konkreten fragen zu den algorithmen kannst dann ja nochmal nachfragen.


----------



## Jockel (17. Nov 2005)

Manchmal ist es naheliegender als man denkt: http://www.sortieralgorithmen.de/


----------



## toxice (18. Nov 2005)

Bitte postet mir mal leicht übersichtliche Quellcodes für den

Bubblesort, Insertionsort und den Selectionsort !!

Bitte nur das wesentliche ! thx


----------



## pogo (18. Nov 2005)

toxice hat gesagt.:
			
		

> Bitte postet mir mal leicht übersichtliche Quellcodes für den
> 
> Bubblesort, Insertionsort und den Selectionsort !!
> 
> Bitte nur das wesentliche ! thx



http://www2.latech.edu/~box/ds/bubbleSort.java

http://www.labri.fr/perso/casteran/JavaSite/polysort/V2/src/InsertionSort.java

http://www.cs.ubc.ca/spider/harrison/Java/SelectionSortAlgorithm.java

//1 min in google und schon hat man die sachen


----------



## toxice (18. Nov 2005)

joa thx doch geht es noch ein bisschen kürzer !?!?

ich darf höchsten 1 min pro quellcode verbrauchen.


also wirklich blso den wesentlichen code !!!

THX


----------



## bygones (18. Nov 2005)

toxice hat gesagt.:
			
		

> joa thx doch geht es noch ein bisschen kürzer !?!?
> 
> ich darf höchsten 1 min pro quellcode verbrauchen.
> 
> ...


hae ? hallo ?

oben wurden dir 3 quellcodes gepostet, die codes sind knapp gehalten und erfuellen ihre Funktion, kuerzer gehts nicht... musst halt einfach schnell reden... *mannomann*


----------



## Mag1c (18. Nov 2005)

Hi,

das ist doch mal ganz nett, oder 

www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortcontest/sortcontest.htm

Gruß
Mag1c


----------



## toxice@kumpel (18. Nov 2005)

Noe ich meinte dass alles in einer Methode ist und einfahc übersichtlicher !!!

Ungefähr so wie der InsertionSort:

public class InsertionSorter {
    private static int[] a;
    private static int n;
    public static void sort(int[] a0) {
        a=a0;
        n=a.length;
        insertionsort();
    }
    private static void insertionsort() {
        int i, j, t;
        for (i=1; i<n; i++) {
            j=i;
            t=a[j];
            	while (j>0 && a[j-1]>t) {
                	a[j]=a[j-1];
                	j--;
            	}
            a[j]=t;
        }
    }
}


----------



## Mag1c (18. Nov 2005)

Hi,

also beim Herrn "Sorting contest" Lang gibts auch noch ein bisschen Dokumentation zu den Algorithmen und auch Java-Code, der je nach Algorithmus mehr oder weniger kurz ausfällt.

www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm

Gruß
Mag1c


----------



## Jockel (18. Nov 2005)

Eine Minute pro Quellcode? Wie wär's mit: "Das ist der Bubblesort-Algorithmus, der sortiert. Das ist der Quicksort-Algorithmus, der sortiert auch. Und der Insertion-Sort, den ihr hier seht, sortiert auch."
Welchen Sinn soll das denn ergeben?


----------



## bygones (18. Nov 2005)

toxice@kumpel hat gesagt.:
			
		

> Noe ich meinte dass alles in einer Methode ist und einfahc übersichtlicher !!!


es sind einfach untersch. Algorithmen, die man nicht mir nichts dir nichts in eine Methode packen kann.....


----------



## The_S (18. Nov 2005)

toxice hat gesagt.:
			
		

> joa thx doch geht es noch ein bisschen kürzer !?!?
> 
> ich darf höchsten 1 min pro quellcode verbrauchen.
> 
> ...



Schreibs halt selber!? Jetzt wo du die Funktionsweiße kennst dürfte das ja kein Thema sein!?


----------



## toxice (18. Nov 2005)

Bin ja noch nicht so fit in Java :/

auf der angegeben seite ist aber nur der Insertion sort, und da hab ich ja den quellcode her !!


wäre ultranett wenn mir einer von euch (wer lust hat) den bubblesort und den selectionsort kurz in 1-2 methoden zusammenschreibt - kurz und bündig halt !!!!!!!!!1


thx


----------



## Jockel (18. Nov 2005)

Wer lesen kann ist klar im Vorteil!!! Da haben mehrere Leute dir Links gegeben, die auch Quellcode enthalten, wenn du aber nicht gewillt bist, dir diese Seite anzuschauen, ist dir auch nicht zu helfen. [...]


----------



## steff3 (19. Nov 2005)

mussten wir auch machen, musst den code nur nach "umwandeln"


```
#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]
```


----------



## bygones (19. Nov 2005)

mhm ihm war der java code der verlinkt wurde schon zuviel - glaube nicht wirklich, dass er nun c++ code nehmen wird !


----------

