Selectionsort - Versionsgeschichte

Akaibel: /* für Listen */

2022-11-21T21:07:32Z

für Listen

← Nächstältere Version		Version vom 21. November 2022, 21:07 Uhr
Zeile 43:		Zeile 43:
	List<Person> ergebnis = new List<>();		List<Person> ergebnis = new List<>();
	while(pList.isEmpty() == false){		while(pList.isEmpty() == false){
	Person p = ~~gibUndEntferneAlphabetischErste~~(pList);		Person p = gibAlphabetischErste(pList);
			loeschen(p, pList);
	ergebnis.append(p);		ergebnis.append(p);
	}		}
Zeile 49:		Zeile 50:
	}		}

	'''private Person ~~gibUndEntferneAlphabetischErste~~(List<Person> pList){ '''		'''private Person gibAlphabetischErste(List<Person> pList){ '''
	pList.toFirst();		pList.toFirst();
	Person ergebnis = pList.getContent();		Person ergebnis = pList.getContent();
Zeile 59:		Zeile 60:
	pList.next();		pList.next();
	}		}
	~~// jetzt~~ ergebnis ~~aus~~ pList ~~loeschen!~~		return ergebnis;
			}

			'''private void loeschen(Person pPerson, List<Person> pList){'''
	pList.toFirst();		pList.toFirst();
	while(pList.hasAccess()){		while(pList.hasAccess()){
	Person p = pList.getContent();		Person p = pList.getContent();
	if(p == ~~ergebnis~~){		if(p == pPerson){
	pList.remove();		pList.remove();
	~~break~~;		return;
	}		}
	pList.next();		pList.next();
	}		}
	~~return ergebnis;~~
	}		}
	</code>		</code>

Akaibel am 23. Januar 2022 um 16:49 Uhr

2022-01-23T16:49:54Z

← Nächstältere Version		Version vom 23. Januar 2022, 16:49 Uhr
Zeile 39:		Zeile 39:
	=Implementierung=		=Implementierung=
	==für Listen==		==für Listen==
	<code>		<code>
	'''private List<Person> sortiereDurchAuswaehlen(List<Person> pList){ '''		'''private List<Person> sortiereDurchAuswaehlen(List<Person> pList){ '''
	List<Person> ergebnis = new List<>();		List<Person> ergebnis = new List<>();
Zeile 71:		Zeile 71:
	return ergebnis;		return ergebnis;
	}		}
			</code>
	</code>

	==für Arrays==		==für Arrays==
	Hier wird die Variante B implementiert.		Hier wird die Variante B implementiert.

	<code>		<code>
	'''public int[] selectionsort(int[] pZahlen){'''		'''public int[] selectionsort(int[] pZahlen){'''
	int[] ergebnis = new int[pZahlen.length];		int[] ergebnis = new int[pZahlen.length];
Zeile 90:		Zeile 89:
	return ergebnis;		return ergebnis;
	}		}


	'''private int indexDerKleinstenZahl(int[] zahlen) {'''		'''private int indexDerKleinstenZahl(int[] zahlen) {'''
	// kleinste wird auf die groesste moegliche Int-Zahl gesetzt		// kleinste wird auf die groesste moegliche Int-Zahl gesetzt
Zeile 104:		Zeile 102:
	return indexKleinste;		return indexKleinste;
	}		}
			</code>
	</code>

Akaibel: /* Erklärvideos */

2020-05-26T14:58:25Z

Erklärvideos

← Nächstältere Version		Version vom 26. Mai 2020, 14:58 Uhr
Zeile 8:		Zeile 8:
	=Erklärvideos=		=Erklärvideos=

	* [https://youtu.be/oiMPMjXpVD8 Selectionsort ~~Erklärvideo~~]		* [https://youtu.be/oiMPMjXpVD8 Selectionsort Prinzip und Algorithmus]

			* [https://youtu.be/dMbm0ZTyfmI Selectionsort Implementierung für Arrays]

	=Fachbegriffe=		=Fachbegriffe=
	Sortieren durch Auswählen (=Selectionsort), Array, Liste		Sortieren durch Auswählen (=Selectionsort), Array, Liste

Akaibel: /* Fachbegriffe */

2020-05-26T14:57:02Z

Fachbegriffe

← Nächstältere Version		Version vom 26. Mai 2020, 14:57 Uhr
Zeile 6:		Zeile 6:
	<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>		<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>

			=Erklärvideos=

			* [https://youtu.be/oiMPMjXpVD8 Selectionsort Erklärvideo]
	=Fachbegriffe=		=Fachbegriffe=

	Sortieren durch Auswählen (=Selectionsort), Array, Liste		Sortieren durch Auswählen (=Selectionsort), Array, Liste

Akaibel: /* für Listen */

2019-12-02T11:52:04Z

für Listen

← Nächstältere Version		Version vom 2. Dezember 2019, 11:52 Uhr
Zeile 35:		Zeile 35:
	==für Listen==		==für Listen==
	<code>		<code>
	private List<Person> sortiereDurchAuswaehlen(List<Person> pList){		'''private List<Person> sortiereDurchAuswaehlen(List<Person> pList){ '''
	List<Person> ergebnis = new List<>();		List<Person> ergebnis = new List<>();
	~~pList.toFirst();~~		while(pList.isEmpty() == false){
	while(pList.~~hasAccess~~()){		Person p = gibUndEntferneAlphabetischErste(pList);
	Person ~~aktuell~~= gibUndEntferneAlphabetischErste(pList);		ergebnis.append(p);
	ergebnis.append(~~aktuell);~~
	~~pList.toFirst(~~);
	}		}
	return ergebnis;		return ergebnis;
	}		}

	private Person gibUndEntferneAlphabetischErste(List<Person> pList){		'''private Person gibUndEntferneAlphabetischErste(List<Person> pList){ '''
	pList.toFirst();		pList.toFirst();
	Person ergebnis = pList.getContent();		Person ergebnis = pList.getContent();
Zeile 56:		Zeile 54:
	pList.next();		pList.next();
	}		}
			// jetzt ergebnis aus pList loeschen!
	pList.toFirst();		pList.toFirst();
	while(pList.hasAccess()){		while(pList.hasAccess()){

Akaibel: /* Verfahren */

2019-06-23T13:59:32Z

Verfahren

← Nächstältere Version		Version vom 23. Juni 2019, 13:59 Uhr
Zeile 5:		Zeile 5:
	[[Kategorie:Sortierverfahren]]		[[Kategorie:Sortierverfahren]]
	<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>		<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>

			=Fachbegriffe=

			Sortieren durch Auswählen (=Selectionsort), Array, Liste

	=Verfahren=		=Verfahren=

	'''Selectionsort -> Sortieren durch Auswählen''' (des jeweils kleinsten Elements aus dem unsortierten Teil)		'''Selectionsort -> Sortieren durch Auswählen''' (des jeweils kleinsten Elements aus dem unsortierten Teil)

Akaibel: Akaibel verschob Seite Selectionsort ab Abi 2017 nach Selectionsort

2016-09-12T14:17:17Z

Akaibel verschob Seite Selectionsort ab Abi 2017 nach Selectionsort

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

Akaibel am 12. September 2016 um 14:16 Uhr

2016-09-12T14:16:57Z

← Nächstältere Version		Version vom 12. September 2016, 14:16 Uhr
Zeile 4:		Zeile 4:
	[[Kategorie:Informatik-Abitur]]		[[Kategorie:Informatik-Abitur]]
	[[Kategorie:Sortierverfahren]]		[[Kategorie:Sortierverfahren]]
			<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>

	=Verfahren=		=Verfahren=
	'''Selectionsort -> Sortieren durch Auswählen''' (des jeweils kleinsten Elements aus dem unsortierten Teil)		'''Selectionsort -> Sortieren durch Auswählen''' (des jeweils kleinsten Elements aus dem unsortierten Teil)

			== Selectionsort auf Listen ==
			Bei SelectionSort wird in einer gegebenen Liste das kleinste Element gesucht, gelöscht und an die Ergebnisliste angehangen.

			Das wird so oft wiederholt, bis die ursprüngliche Liste leer ist.

	== Selectionsort auf Arrays ==		== Selectionsort auf Arrays ==
Zeile 18:		Zeile 23:
	** im ursprünglichen Array wird das kleinste Element gesucht und durch eine SEHR große Zahl ersetzt (auf jeden Fall größer als alle Elemente des Arrays).		** im ursprünglichen Array wird das kleinste Element gesucht und durch eine SEHR große Zahl ersetzt (auf jeden Fall größer als alle Elemente des Arrays).
	** das kleinste Element wird in das Ergebnis-Array geschrieben.		** das kleinste Element wird in das Ergebnis-Array geschrieben.

	~~== Selectionsort auf Listen ==~~
	~~Bei SelectionSort wird in einer gegebenen Liste das kleinste Element gesucht, gelöscht und an die Ergebnisliste angehangen.~~

	~~Das wird so oft wiederholt, bis die ursprüngliche Liste leer ist.~~

	=Laufzeit=		=Laufzeit=

Mgrifka: Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-EF Kategorie:Informatik-Q1 Kategorie:Informatik-Abitur Kategorie:Sortierverfahren =Verfahren= '…“

2016-08-09T08:17:55Z

Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-EF Kategorie:Informatik-Q1 Kategorie:Informatik-Abitur Kategorie:Sortierverfahren =Verfahren= '…“

Neue Seite

[[Kategorie:Informatik]]
[[Kategorie:Informatik-EF]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Sortierverfahren]]

=Verfahren=
'''Selectionsort -> Sortieren durch Auswählen''' (des jeweils kleinsten Elements aus dem unsortierten Teil)

== Selectionsort auf Arrays ==
'''Variante A: Sortieren innerhalb eines Arrays:''' 
Bei Selectionsort wird vorne im Array begonnen und das kleinste Element im Array gesucht. Dieses wird dann mit dem ersten Element im Array vertauscht. In jedem weiteren Schritt wird dann aus dem hinteren, unsortierten Teil des Arrays das kleinste Element gesucht und mit dem ersten Element (am weitesten Links) des unsortierten Teils vertauscht. Dadurch wächst der vordere, sortierte Teil des Arrays in jedem Schritt um eins.

'''Variante B: Erzeugen eines neuen sortierten Arrays:''' 
* Es wird ein Ergebnis-Array gleicher Länge erzeugt.
* dann wiederholt man n-mal:
** im ursprünglichen Array wird das kleinste Element gesucht und durch eine SEHR große Zahl ersetzt (auf jeden Fall größer als alle Elemente des Arrays).
** das kleinste Element wird in das Ergebnis-Array geschrieben.

== Selectionsort auf Listen ==
Bei SelectionSort wird in einer gegebenen Liste das kleinste Element gesucht, gelöscht und an die Ergebnisliste angehangen.

Das wird so oft wiederholt, bis die ursprüngliche Liste leer ist.

=Laufzeit=
O(n2), d.h. der Aufwand wächst quadratisch mit der Zahl der zu sortierenden Elemente.

=Implementierung=
==für Listen==
<code>
private List<Person> sortiereDurchAuswaehlen(List<Person> pList){
List<Person> ergebnis = new List<>();
pList.toFirst();
while(pList.hasAccess()){
Person aktuell= gibUndEntferneAlphabetischErste(pList);
ergebnis.append(aktuell);
pList.toFirst();
}
return ergebnis;
}

private Person gibUndEntferneAlphabetischErste(List<Person> pList){
pList.toFirst();
Person ergebnis = pList.getContent();
while (pList.hasAccess()){
Person p = pList.getContent();
if(p.getName().compareTo(ergebnis.getName())<0){
ergebnis = p;
}
pList.next();
}
pList.toFirst();
while(pList.hasAccess()){
Person p = pList.getContent();
if(p == ergebnis){
pList.remove();
break;
}
pList.next();
}
return ergebnis;
}

</code>

==für Arrays==
Hier wird die Variante B implementiert.

<code>
'''public int[] selectionsort(int[] pZahlen){'''
int[] ergebnis = new int[pZahlen.length];
for (int i = 0; i < pZahlen.length; i++) {
int indexKleinsteZahl = indexDerKleinstenZahl(pZahlen);
int dieKleinsteZahl = pZahlen[indexKleinsteZahl];
ergebnis[i] = dieKleinsteZahl;
// damit dieselbe Zahl nicht nochmal "gefunden" wird
// wird sie durch die hoechste Integerzahl ersetzt.
pZahlen[indexKleinsteZahl] = Integer.MAX_VALUE;
}
return ergebnis;
}

'''private int indexDerKleinstenZahl(int[] zahlen) {'''
// kleinste wird auf die groesste moegliche Int-Zahl gesetzt
int kleinste = Integer.MAX_VALUE;
int indexKleinste = -1;
for (int i = 0; i < zahlen.length; i++) {
if(zahlen[i] < kleinste){
kleinste = zahlen[i];
indexKleinste = i;
}
}
return indexKleinste;
}

</code>