InsertionSort

[babuschka]

Ich soll in einer Methode eine Liste mit InsertionSort sortieren und habe vorgegeben, dass ich Collections.sort und ähnliches nicht verwenden darf.

Kann mir jemand dabei mit dem Ansatz helfen?

public static void sortInsertionSort(List<int> zahl) {

???

}

Wie gesagt, nur einen Ansatz bräuchte ich

 

[eRaaaa]

Wie gesagt, nur einen Ansatz bräuchte ich

Insert-sort with Romanian folk dance - YouTube
Insertionsort ? Wikipedia

 

[Timothy Truckle]

Durchsuche die schon vorhanden Listeneinträge und füge das neue Element vor dem ersten
ein, das "größer" als das neue ist.

bye
TT

 

[SlaterB]

> Ich soll in einer Methode eine Liste mit InsertionSort sortieren

hmm, was wähle ich nun als Titel für das Thema, InsertionSort, welches klar den gesuchten Sortieralgorithmus umwinkt
oder nenne ich das Thema 'Liste'?
meine Güte.., Thementitel geändert

Tipp: wenn du einen Sortieralgorithmus in einer Suchmaschine suchtest, worauf du offensichtlich nicht selber kommst,
dann wäre 'Liste' auch ein schlechter Suchbegriff

harte Worte, aber müssen anscheinend sein,
so nun weiter in der Arbeit

 

[Spin]

Fertig ? Java
Mal für die Scala Neugierigen

 

[Xalker]

Ich bin auch Anfänger und habe versucht das Problem zu lösen. Es klappt auch. Ich würde nur gerne wissen, ob der Code so ok ist oder ob man das optimieren kann.

Wäre es unfair gegenüber den Beitragsersteller, wenn ich meinen Code hier poste ?

 

[SlaterB]

nicht viel unfairer als dass du mit deinem Posting eh schon 'störst'

fertiger Code scheint hier eh erwünscht, also mach ruhig

 

[Xalker]

Ok, nächste mal halte ich mich zurück. Ist das Forum überhaupt geeignet um Hinweise für besseren Code zubekommen oder ist es eher für Lösungsansätze gedacht ?

Die Methode "einfuegen", habe ich gemacht, weil ich gelesen habe, das "break" (Hatte ich vorher in der Schleife anstelle von return) nicht erwünscht ist.

public class TestMain {


	public static void main(String[] args) {
		List<Integer> zahlen = new ArrayList<Integer>();
		zahlen.add(5);
		zahlen.add(3);
		zahlen.add(1);
		zahlen.add(8);
		zahlen.add(0);

		System.out.println("Unsort:" + zahlen);

		zahlen = sortInsertionSort(zahlen);
		System.out.println("Sort  :" + zahlen);
	}

	private static List<Integer> sortInsertionSort(List<Integer> zahlen) {
		List<Integer> temp = new ArrayList<Integer>();
		for (Iterator<Integer> iterator = zahlen.iterator(); iterator.hasNext();) {
			Integer integer1 = (Integer) iterator.next();
			
			einfuegen(temp, integer1);
		}
		return temp;
	}

	private static void einfuegen(List<Integer> temp, Integer integer1) {
		for (Iterator<Integer> iterator2 = temp.iterator(); iterator2.hasNext();) {
			Integer integer2 = (Integer) iterator2.next();
			if (integer2 > integer1) {
				temp.add(temp.indexOf(integer2), integer1);
				return;
			}
		}
		temp.add(integer1);
	}

}

 

[SlaterB]

> Ist das Forum überhaupt geeignet um Hinweise für besseren Code zubekommen oder ist es eher für Lösungsansätze gedacht ?

selbstverständlich für alles, die Frage ist hier nur ob du dich reindrängst, Aufmerksamkeit abziehst usw.

-----
Konstrukte wie

        for (Iterator<Integer> iterator = zahlen.iterator(); iterator.hasNext();) {
            Integer integer1 = (Integer) iterator.next();

sind ganz übel, das kannst du auch als

        for ( Integer integer1 : zahlen) {

schreiben, alternativ wäre selbst eine klassische for-i-Schleife besser (wenn man mit ArrayList rechnen kann, keine Performance-Probleme befürchten muss),
besonders in der einfuegen()-Methode, wo es dir die Suche nach dem Index einsparen würde

ansonsten ist wohl nicht viel zu bemeckern da, sofern es funktioniert

 

[Timothy Truckle]

Konstrukte wie

        for (Iterator<Integer> iterator = zahlen.iterator(); iterator.hasNext();) {
            Integer integer1 = (Integer) iterator.next();

sind ganz übel,

sind sie nicht, weil

for (ListIterator<Integer> iterator = zahlen.listIterator(); iterator.hasNext();) 
      Integer integer2 = iterator.next();
      if (integer2 > integer1) 
        iterator.add(integer1);

im Gegensatz zum gezeigten Code nicht zu einer

ConcurrentModificationException

führt.

bye
TT

 

[SlaterB]

im gezeigten Code kann es wegen des returns nicht wirklich zu einer ConcurrentModificationException kommen,

dein Code ist letztlich aber noch eine dritte Variante, mit gewissen Nutzen, gerne

 

[Timothy Truckle]

im gezeigten Code kann es wegen des returns nicht wirklich zu einer ConcurrentModificationException kommen,

Doch, denn das

add

auf die selbe Liste kommt vor dem

return

.

bye
TT

 

[SlaterB]

man kann den Code doch kopieren und ausprobieren?
ich habe das freilich nicht gemacht da Xalker zuversichtlich klingt ("Es klappt auch.")

wenn du vermutest, dass der Code direkt zu einer Exception führt, wäre es etwas sicherer, das durch Ausprobieren zu bestätigen

das add() macht direkt keine Probleme, die Liste kümmert sich nicht um evtl. offene Iteratoren,
erst wenn man im Iterator einen Schritt weiter ginge käme es dort zur Prüfung

etwas unschön ist das ganze gewiss, hatte ich ursprünglich nicht gesehen