Sortieralgorithmus von rekursiv auf iterativ?

[Frager]

Folgende Aufgabe:

Ich soll einen Sortieralgorithmus schreiben, der erst die 1.2-drittel, dann die 2.2-drittel und dann wieder die 1. 2-drittel sortiert.

rekursiv war des kein problem, nun sollen die anfangs und endwerte in einem keller gespeichert werden, da bin ich schon fast am ziel.

nur ist mir nciht klar, wie ich das dann sortieren soll? also wenn ich so lange werte im keller speicher bis sich anfang und ende des teilbereichs nur noch um max 1 unterscheiden kann ich natürlich das sortieren, sind dann ja 2 ints. aber dann kommt ausm keller ja sowas wie zb 2 und 5 also mit 4 zahlen, wovon jeweils 2 pärchen sortiert sind, was soll cih dann da sortieren?

Das macht für mcih alles keinen sinn

 

[hdi]

nun sollen die anfangs und endwerte in einem keller gespeichert werden

Was genau meinst du damit? Welche Anfangs- und Endwerte? Also Stoogesort ist eigentlich
ein rekursiver Algorithmusm, iterativ heisst ja quasi nur schrittweise ohne Wiederaufrufen der Funktion.
Also in einer Art while-Schleife, denk ich jetz, aber steh auch grad etwas neben mir hier :autsch:
Ich versteh nich was du mit diesem "Keller" willst?

 

[Ebenius]

Kellerspeicher, aka. Stapelspeicher, aka. Stack

 

[hdi]

Ja ne schon klar Aber was will er damit bei diesem Sortieralgorithmus, das check ich grad nicht

 

[Gast]

achso, der keller muss eingebaut werden, ist teil der aufgabe.
Anstatt des Rekursionsaufrufs werden in einer Schleife die beiden Grenzen der noch zu sortierenden Teilfolgen bis zur Weiterverarbeitung in einem Keller abgelegt. Sie werden bei Bedarf wieder herausgeholt. Auf diese Art und Weise wird der Laufzeitkeller der Rekursion nachgebildet.

also muss ich erstmal den keller mit werten füllen, die dann wieder rausholen und damit dann i-wie sortieren...

 

[Gast]

zu triplesort siehe hier:

http://www.java-forum.org/de/viewtopic.php?t=80592&highlight=triplesort

 

[mahe]

Wenn Deine Funktion endrekursiv ist, brauchst Du lediglich die Parameter der Rekursionsaufrufe im Stack ablegen und den Funktionsrumpf so umschreiben, dass er den Stack abarbeitet. Die Abbruchbedingungen beenden dann nicht die Funktion sondern lediglich diesen Schleifendurchlauf.

Da ich für den anderen Thread schon mal ein Triple-Sort geschrieben hatte (und weil ich nicht schlafen kann ), hier auch in iterativer Variante:

class TripleSort {

	public static void sortIt(int[] numbers) {
		Stack<Integer> sStart = new Stack<Integer>();
		Stack<Integer> sLength = new Stack<Integer>();
		sStart.push(0);
		sLength.push(numbers.length);

		while(!sStart.isEmpty()) {
			int start  = sStart.pop();
			int length = sLength.pop();

			if (length < 2) {
				continue;
			} else if (length == 2) {
				if (numbers[start] > numbers[start+1]) {
					switchNr(numbers, start, start+1);
				}
				continue;
			}

			int third = length/3;
			int twoThirds = length-third;

			sStart.push(start);
			sLength.push(twoThirds);

			sStart.push(start+third);
			sLength.push(twoThirds);

			sStart.push(start);
			sLength.push(twoThirds);
		}
	}

	public static void sortRek(int[] a) {
		sortRek(a, 0, a.length);
	}

	private static void sortRek(int[] numbers, int start, int length) {
		if (length < 2) {
			return;
		} else if (length == 2) {
			if (numbers[start] > numbers[start+1]) {
				switchNr(numbers, start, start+1);
			}
			return;
		}

		int third = length/3;
		int twoThirds = length-third;
		
		sortRek(numbers, start, twoThirds);
		sortRek(numbers, start+third, twoThirds);
		sortRek(numbers, start, twoThirds);
	}

	private static void switchNr(int[] numbers, int a, int b) {
		int t = numbers[b];
		numbers[b] = numbers[a];
		numbers[a] = t;
	}
}

Selbverständlich würde ein Stack ausreichen, zur Verdeutlichung hier aber zwei.

 

[Gast]

ui, danke, guck ich mir mal an ^^

 

[Gast]

ist das nicht auch wieder rekursiv? du rufst ja in der sortRek wieder sortRek auf... man soll es aber mit ner while-schleife machen, gerade das versteh ich ja nicht

 

[mahe]

Da ist sowohl die rekursive als auch die iterative Version in der Klasse (damit Du siehst wie das funktioniert).
sortRek ist rekursiv und sortIt ist iterativ (mit while-Schleife).
sortIt ruft lediglich die switch-Funktion auf welche die Werte vertauscht.

Der Algorithmus ist in beiden Versionen exakt derselbe.

 

[Gast]

hmm, ok, nun uss ich ja die stacvks noch in "unsere" keller umschreiben, beim compilieren gibt er folgende fehlermeldung

need int but found void an der stelle

int start = sStart.pop();

habs versucht so zu casten:

int start = (Integer)sStart.pop();

aber dat geht auch net

 

[Gast]

oh, fehler gefunden, bei uns is pop löschen und top das oberste element nehmen ^^

 

[Ebenius]

Wenn auch langsam: Hier nochmal die Implementierung mit nur einem Stack:

@SuppressWarnings("boxing")
private static void sortIterative(int[] array) {
  final Stack<Integer> stack = new Stack<Integer>();
  stack.push(array.length - 1);
  stack.push(0);
  do {
    int start = stack.pop();
    int end = stack.pop();
    if (array[start] > array[end]) {
      flip(array, start, end);
    }

    if (start + 1 < end) {
      final int k = (end - start + 1) / 3;
      stack.push(end - k);
      stack.push(start);
      stack.push(end);
      stack.push(start + k);
      stack.push(end - k);
      stack.push(start);
    }
  } while (!stack.isEmpty());
}

private static void flip(int[] a, int i, int j) {
  final int e = a[i];
  a[i] = a[j];
  a[j] = e;
}

Ebenius

 

[gast]

habs jetzt so umgeschrieben, aber hängt beim ausführen in ner endlosschleife

import AlgoTools.IO;
public class TripleSortIterativ{
    public static void sort(int[] numbers) {
      Keller sStart = new VerweisKeller();
      Keller sLength = new VerweisKeller();
      sStart.push(0);
      sLength.push(numbers.length);

      while(!sStart.empty()) {
         int start  = (Integer)sStart.top();
         int length = (Integer)sLength.top();

         if (length < 2) {
            continue;
         } else if (length == 2) {
            if (numbers[start] > numbers[start+1]) {
               switchNr(numbers, start, start+1);
            }
            continue;
         }

         int third = length/3;
         int twoThirds = length-third;

         sStart.push(start);
         sLength.push(twoThirds);

         sStart.push(start+third);
         sLength.push(twoThirds);

         sStart.push(start);
         sLength.push(twoThirds);
      }
   } 
   private static void switchNr(int[] numbers, int a, int b) {
      int t = numbers[b];
      numbers[b] = numbers[a];
      numbers[a] = t;
   } 
}

 

[Ebenius]

Du musst natürlich auch noch pop() aufrufen nach dem top().

 

[Gast]

stimmt, sonst wirds ja nie leer ^^

 

[Gast]

also das mit 2en funktioniert ^^ werd mir jetzt nochmal alles anschauen und auf der basis von den 2 beispielen was eigenes konstruieren, aber ich danke euch 2en schonmalganz herzlichst, habt mir den tag(oder die nacht^^) gerettet

 

[Leroy42]

Du musst natürlich auch noch pop() aufrufen nach dem top().

... also:

         int start  = (Integer)sStart.top(); sStart.pop();
         int length = (Integer)sLength.top(); sLength.pop();

Edit: Huch! :shock: Mal wieder verpennt, daß es schon eine zweite Seite gab!

 

[Ein-doofer-Tutor]

SUPER!
Immerhin dieses Mal die Aufgabenstellung nicht 1:1 kopiert, sondern sinngemäß wiedergegeben!
http://www.java-forum.org/de/viewtopic.php?p=480959#480959

Inzwischen den Tutornamen gelernt?!

In der Klausur werden übrigens keine Computer zugelassen sein. Nur so als kurze Anmerkung...

 

[mahe]

Wo ist diese Uni (?) überhaupt?

Wenns nicht zu weit weg ist komme ich zur Klausur.
Genug Punkte müsste ich inzwischen ja haben :wink:

 

[nohfreak]

Osnabrück.

Aber wenn er sich hier weiterhin alles vorsagen lässt wird er wohl in der Klausur Probleme bekommen, ich hab heute paar alte KLausuren gesehen. :>

 

[mahe]

Oje, das ist mir doch zu weit: Strecke

Wenn es alte Klausuren zur Einicht gibt kann man die Programme ja auswendig lernen.
So haben sich bei uns schon einige durchgemogelt :lol: