Quicksort mit Stacks
Sortieren Sie einen gegebenen Stack mit Quicksort. Das bedeutet: Nach der Ausführung der zu implementierenden Methode quicksort() soll das oberste Element des Stack das kleinste sein, das zweitoberste das zweitkleinste, usw. Verwenden Sie hierzu ausschließlich die Methoden empty(), size(), pop() und push() der Klasse Stack. Sie dürfen temporäre Stacks zur Hilfe anlegen - allerdings keine anderen Datenstrukturen wie Arrays o.ä.
Hinweise
- Da Sie ja nur immer das oberste Element des Stacks sehen und manipulieren können, können Sie nicht das Schema von Hoare anwenden. Behalten Sie aber die generelle Strategie von Quicksort bei (Sortieren anhand eines Pivots).
- Sie dürfen annehmen dass die zu sortierenden Zahlen paarweise verschieden sind.
package de.hsrm.ads;
import java.util.Stack;
public class StackSort {
public static void quicksort(Stack<Integer> stack) {
// FIXME
}
public static void main(String[] args) {
Stack<Integer> s = new Stack<Integer>();
s.push(2);
s.push(1);
s.push(4);
s.push(3);
quicksort(s);
// Sollte 1,2,3,4 ausgeben.
while (!s.empty()) {
System.out.println(s.pop());
}
}
}
Subato
