Quicksort In-Situ mit Comparables

[lesni]

Liebe Java-Gemeinde,

es wäre toll, wenn der ein oder andere mir bei folgendem Problem mit ein paar Denkanstößen weiterhelfen könnte. Ich soll einen Quicksort-Algorithmus für "Comparable[] values" schreiben - leider hat der Compiler bisweilen etwas dagegen. Hier erstmal der Code:

public class QuickSort implements Sorter{
	
	public static void swap(Comparable[] values, int pos_1, int pos_2){
		Comparable tmp = values[pos_1];
		values[pos_1] = values[pos_2];
		values[pos_2] = tmp;
	}

	// QuickSort IN SITU
		
	private int partition(Comparable[] values, int start, int ende){
		int part = start;
		Comparable pivot = values[ende];
		for(int i = start; i < ende; i++){
			if(values[i].compareTo(pivot) <= 0){
				swap(values, i, part);
				part++;
			}
			return part;
		}
	}
	
	private void quickSort(Comparable[] values, int i, int j){
		int part;
		if(i < j){
			part = partition(values, i, j);
			swap(values, part, j);
			quickSort(values, i, part-1);
			quickSort(values, part+1, j);
		}
	}
	
	public int sort(Comparable[] array){
		int i = 0;
		int j = array.length-1;
		quickSort(array, i, j);		
		return 0;
	}
}

public class TestSorter{

	boolean istAufsteigendSortiert(Comparable[] array){
		for(int i = 0; i<array.length; i++){
			if(array[i].compareTo(array[i+1]) < 0){
				return true;
			}
			else
				return false;
		}
	}

	public static void main(String[] args){
		Comparable[] c = {1,2,3};
		QuickSort.sort(c);
		
		if(istAufsteigendSortiert(c))
			System.out.println("Das Array ist aufsteigend sortiert.");
		else
			System.out.println("Das Array ist NICHT aufsteigend sortiert.");
	}	
}

interface Sorter {
	
	// Sortiert das übergebene array aufsteigend.
	
	public int sort(Comparable[] array);

}

Erstmal habe ich Probleme mit dem Anfängerfehler "non-static methode ... from static context". Das verstehe ich schonmal nicht, da ich doch in der main-Methode "c" klar definiert habe. Darüber hinaus wird mir vorgeworfen "unchecked and unsafe operations" zu verwenden - das würde ich nie tun (wollen)!

Ich befürchte, dass der Code wahrscheinlich nur so vor Fehlern wimmelt. Also seid nicht zimperlich und übt schonungslos konstruktive Kritik. Ich will's ja kapieren!

 

[Innocent92]

Hallo du,

INFO II hausaufgabe 4???
Naja wo auch immer deine Frage aufgetaucht ist..

1. Frage: das static Problem

Du versuchst auf die Methode istAufsteigendSortiert der Klasse TestSorter zuzugreifen.
Allerdings hast du kein Objekt dieser Klasse instanziiert.
Möchtest du aber die Methode einer klasse aufrufen, die sich nicht auf ein spezielles
Objekt bezieht aufrufen, so muss diese als static deklariert werden.
Versuch mal

static boolean istAufsteigend...

2. Frage: unchecked warnings

Der Compiler wünscht sich eine genauere Beschreibung des Comparable Objekts wäre es zb
ein Integer wäre Comparable<int> besser geeignet um Fehler zu vermeiden. Da wir aber grund-
sätzlich nichts über das Objekt wissen ist es nicht verkehrt diese Typisierung wegzulassen.
Du wirst sehen bei Standardeinstellung im Compiler werden die .Class files trotz Warnung erzeugt.

Ansonsten wirst du auch noch ein Wenig rumprobieren müssen, bis dein Algorithmus läuft denke ich.

Gleich ins Auge gefallen ist mir der return innerhalb der for-Schleife in der partition Methode.. Unsinnig.
Interessante Lektüre: wikipedia Stichwort quicksort.. hier findest du auch pseudocode der sehr
hilfreich ist um die Implementierung nachzuvollziehen.

Deine Rekursionsmethode quickSort sieht schon recht gut aus, nur warum tauscht du die Elemente??
Außerdem ist in meinem Aufgabenblatt ein Zähler verlangt der die Rekursionen zählt, Stichwort globale
Variable..

In der Partition Methode fehlt dir noch der richtige logische Aufbau. Du benötigst zwei Laufvariablen,
die jeweils hoch bzw runter gezählt werden bis auf der linken Seite ein Objekt ist dass größer ist als Pivot und
auf der rechten eines, das kleiner als Pivot ist. Wenn die Variablen sich noch nicht getroffen haben, werden diese Elemente anschließend getauscht und die variablen "weiter" gezählt.

Auch in deiner TestSorter musst du die Forschleife überprüfen.. Hier möchtest du doch einfach nur die Elemente durchgehen, deine Bedingung prüfen und nur falls diese verletzt ist möchtest du mit false zurückkehren. Nur wenn die Schleife ohne eine solche Verletzung durchläuft möchtest du true zurückkehren.
In deiner Lösung wird nach dem ersten Element, das die Bedingung erfüllt ausgegeben, dass dies für alle gilt!!

Da die Methoden in QuickSort nicht statisch sind musst du erst ein Objekt instanziieren, dem du dann über die Methode sort ein Array "fütterst".



Falls du noch Fragen hast/deine Probleme weiterbestehen schreib doch nochmal..

Viel Spaß noch und Liebe Grüße,
Kai

 

[lesni]

Vielen Dank - hab's hinbekommen. Beginne langsam, die Logik hinter den static/non-static-Fehlermeldungen zu verstehen.

Eine Anmerkung noch: Die Implementierung der Partitionsmethode bei Wikipedia unterscheidet sich m.E. stark von der im Tutorium behandelten Handsimulation, in der beide Laufindizes am Anfang des Arrays starten - das hat mich verwirrt. Zudem wird in den Folien eine andere Implementierung der Partitionsmethode angeführt, an der ich mich zunächst orientiert hatte.

Trotzdem: Die Sonne scheint, und bekomme sie heute vielleicht sogar mal zu Gesicht!