Mergesort - Versionsgeschichte

Akaibel am 15. Dezember 2022 um 17:09 Uhr

2022-12-15T17:09:26Z

← Nächstältere Version		Version vom 15. Dezember 2022, 17:09 Uhr
Zeile 3:		Zeile 3:
	[[File:Mergesort.png\|thumb\|Mergesort für das Wort "informatik" \|428px]]		[[File:Mergesort.png\|thumb\|Mergesort für das Wort "informatik" \|428px]]
	'''<font color='red'>nicht relevant fürs Zentralabitur!</font>'''		'''<font color='red'>nicht relevant fürs Zentralabitur!</font>'''

	~~<font color='red'>'''Die Schnittstellenbeschreibung entspricht dem Abi 17 (und folgenden)'''</font>~~

	= Funktionsweise =		= Funktionsweise =

Akaibel: /* Implementierung */

2022-12-15T16:58:21Z

Implementierung

Änderungen zeigen

Akaibel am 23. Januar 2022 um 16:53 Uhr

2022-01-23T16:53:38Z

← Nächstältere Version		Version vom 23. Januar 2022, 16:53 Uhr
Zeile 17:		Zeile 17:

	=Implementierung=		=Implementierung=
	<code>		<code>
	private List<Person> teile(List<Person> pList){		private List<Person> teile(List<Person> pList){
	'''//TODO'''		'''//TODO'''
Zeile 48:		Zeile 48:
	return ergebnis;		return ergebnis;
	}		}
	</code>		</code>

	mergeSort ruft die Methode verschmelzen auf:		mergeSort ruft die Methode verschmelzen auf:

	<code>		<code>
	/**		/**
	* verschmilzt zwei sortierte Listen		* verschmilzt zwei sortierte Listen
Zeile 92:		Zeile 92:
	return ergebnis;		return ergebnis;
	}		}
	</code>		</code>

Akaibel: /* Implementierung */

2018-04-05T11:58:37Z

Implementierung

← Nächstältere Version		Version vom 5. April 2018, 11:58 Uhr
Zeile 64:		Zeile 64:
	while(l1.hasAccess() && l2.hasAccess()){		while(l1.hasAccess() && l2.hasAccess()){
	// jeweils die erste Person auslesen		// jeweils die erste Person auslesen
	Person p1 = ~~(Person)~~ l1.getContent();		Person p1 = l1.getContent();
	Person p2 = ~~(Person)~~ l2.getContent();		Person p2 = l2.getContent();
	// die alphabetisch kleinere der beiden Personen		// die alphabetisch kleinere der beiden Personen
	// in die Liste ergebnis uebertragen		// in die Liste ergebnis uebertragen

Akaibel: Akaibel verschob Seite Mergesort ab Abi 2017 nach Mergesort

2016-09-12T14:19:21Z

Akaibel verschob Seite Mergesort ab Abi 2017 nach Mergesort

← Nächstältere Version	Version vom 12. September 2016, 14:19 Uhr
(kein Unterschied)

Akaibel am 12. September 2016 um 14:18 Uhr

2016-09-12T14:18:40Z

← Nächstältere Version		Version vom 12. September 2016, 14:18 Uhr
Zeile 3:		Zeile 3:
	[[File:Mergesort.png\|thumb\|Mergesort für das Wort "informatik" \|428px]]		[[File:Mergesort.png\|thumb\|Mergesort für das Wort "informatik" \|428px]]
	'''<font color='red'>nicht relevant fürs Zentralabitur!</font>'''		'''<font color='red'>nicht relevant fürs Zentralabitur!</font>'''

			<font color='red'>'''Die Schnittstellenbeschreibung entspricht dem Abi 17 (und folgenden)'''</font>

	= Funktionsweise =		= Funktionsweise =

Mgrifka am 9. August 2016 um 08:23 Uhr

2016-08-09T08:23:49Z

← Nächstältere Version		Version vom 9. August 2016, 08:23 Uhr
Zeile 16:		Zeile 16:
	=Implementierung=		=Implementierung=
	<code>		<code>
	private List teile(List pList){		private List<Person> teile(List<Person> pList){
	'''//TODO'''		'''//TODO'''
	}		}
Zeile 23:		Zeile 23:
	List<Person> ergebnis = new List<>();		List<Person> ergebnis = new List<>();
	List<Person> hintereListe = new List<>();		List<Person> hintereListe = new List<>();

	// abbruchbedingung: nur 1 element in pList		// abbruchbedingung: nur 1 element in pList
	pList.toLast();		pList.toLast();
Zeile 34:		Zeile 34:
	return pList;		return pList;
	}		}

	hintereListe = teile (pList);		hintereListe = teile (pList);

Zeile 40:		Zeile 40:
	List<Person> pListSortiert = mergeSort(pList);		List<Person> pListSortiert = mergeSort(pList);
	List<Person> hintersteListSortiert = mergeSort(hintereListe);		List<Person> hintersteListSortiert = mergeSort(hintereListe);

	// verschmelzen		// verschmelzen
	ergebnis = verschmelzen(pListSortiert, hintersteListSortiert);		ergebnis = verschmelzen(pListSortiert, hintersteListSortiert);
Zeile 79:		Zeile 79:
	// in ergebnis uebertragen		// in ergebnis uebertragen
	while(l1.hasAccess()){		while(l1.hasAccess()){
	ergebnis.append(l1.~~getObject~~());		ergebnis.append(l1.getContent());
	l1.remove();		l1.remove();
	}		}
Zeile 85:		Zeile 85:
	// in ergebnis uebertragen		// in ergebnis uebertragen
	while(l2.hasAccess()){		while(l2.hasAccess()){
	ergebnis.append(l2.~~getObject~~());		ergebnis.append(l2.getContent());
	l2.remove();		l2.remove();
	}		}

Mgrifka: Die Seite wurde neu angelegt: „Kategorie:Sortierverfahren 428px '''nicht relevant fürs Zentralabitu…“

2016-08-09T08:22:59Z

Die Seite wurde neu angelegt: „Kategorie:Sortierverfahren thumb|Mergesort für das Wort "informatik" |428px '''<font color='red'>nicht relevant fürs Zentralabitu…“

Neue Seite

[[Kategorie:Sortierverfahren]]

[[File:Mergesort.png|thumb|Mergesort für das Wort "informatik" |428px]]
'''<font color='red'>nicht relevant fürs Zentralabitur!</font>'''

= Funktionsweise =
Mergesort ist ein '''Divide&Conquer'''-Verfahren.

Im '''Divide''' wird die Liste in zwei gleich große Teile aufgeteilt (wenn die Anzahl der Elemente ungerade ist, dann natürlich nicht ganz gleich groß...).

Beim '''Conquer''' werden die sortierten Teillisten zusammengefügt. Durch geschickte Implementierung kann man das in O(n) Zeit bewerkstelligen.

=Laufzeit=
Mergesort hat auch im '''Worst Case''' eine Laufzeit von '''O(n*log(n))'''. <br>Für Arrays ist allerdings [[Quicksort ab Abi 2017|Quicksort]] schneller, weil man bei Mergesort ständig neue Arrays erzeugen muss - bei Quicksort dagegen kann man ''in situ'' (bzw. ''in place'') arbeiten.

=Implementierung=
<code>
private List teile(List pList){
'''//TODO'''
}

public List<Person> mergeSort(List<Person> pList){
List<Person> ergebnis = new List<>();
List<Person> hintereListe = new List<>();

// abbruchbedingung: nur 1 element in pList
pList.toLast();
Person hinten = pList.getContent();
pList.toFirst();
Person vorne = pList.getContent();
if(vorne == hinten)
{
// pList enthaelt nur ein Element!
return pList;
}

hintereListe = teile (pList);

//sortieren der Teillisten durch rekursiven Aufruf
List<Person> pListSortiert = mergeSort(pList);
List<Person> hintersteListSortiert = mergeSort(hintereListe);

// verschmelzen
ergebnis = verschmelzen(pListSortiert, hintersteListSortiert);
System.out.println("ende von mergesort:");
return ergebnis;
}
</code>

mergeSort ruft die Methode verschmelzen auf:

<code>
/**
* verschmilzt zwei sortierte Listen
* zu einer sortierten Liste
*/
private List<Person> verschmelzen(List<Person> l1, List<Person> l2) {
List<Person> ergebnis = new List<>();
l1.toFirst();
l2.toFirst();
// beide Listen parallel durchlaufen
while(l1.hasAccess() && l2.hasAccess()){
// jeweils die erste Person auslesen
Person p1 = (Person) l1.getContent();
Person p2 = (Person) l2.getContent();
// die alphabetisch kleinere der beiden Personen
// in die Liste ergebnis uebertragen
// und aus der Herkunftsliste loeschen
if(p1.getName().compareTo(p2.getName()) < 0){
ergebnis.append(p1);
l1.remove();
}
else{
ergebnis.append(p2);
l2.remove();
}
}
// den Rest der ersten Liste (wenn es einen gibt)
// in ergebnis uebertragen
while(l1.hasAccess()){
ergebnis.append(l1.getObject());
l1.remove();
}
// den Rest der zweiten Liste (wenn es einen gibt)
// in ergebnis uebertragen
while(l2.hasAccess()){
ergebnis.append(l2.getObject());
l2.remove();
}
return ergebnis;
}
</code>