Quick Sort insitu < Java < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Implementieren Sie eine Klasse public class QuickSort implements Sorter, welche den
QuickSort-Algorithmus in-situ implementiert. Testen Sie Ihren Algorithmus mit Hilfe einer Klasse
public class TestSorter. Schreiben Sie dazu eine Methode boolean istAufsteigendSortiert
(Comparable[] array), die uberpruft, ob das ubergebene Array aufsteigend sortiert ist (also
ob fur das gesamte Array an an+1 gilt).
Hinweis:
Der Algorithmus soll mithilfe von drei Methoden innerhalb der Klasse QuickSort realisiert
werden:
Die Partitionsmethode private int partition(Comparable[] values, int start, int
ende) erhalt die Parameter start und ende, diese beschreiben den Bereich fur den values
betrachtet werden soll. Das Element values[ende] soll als Pivot-Element gewahlt werden.
Die Methode soll den angebenen Bereich von values derart sortieren, dass nach der Sortierung
alle Elemente, die kleiner-gleich dem Pivot-Element sind, links von diesem stehen und alle die
groer sind rechts. Es gibt aber keine Sortierung in den Bereichen selbst. Die Methode gibt den
aktuellen Index des Pivot-Elements zuruck.
Die Rekursionsmethode private void quickSort(Comparable[] values, int i, int j)
soll unter Nutzung der Methode partition das Array baumartig rekursiv sortieren.
Die Aufrufmethode public int sort( Comparable[] array ) startet die Rekursion. Die
Ruckgabe stellt die Anzahl der Rekursionsaufrufe dar und wird ebenfalls fur den Contest
benotigt. Fur diese Aufgabe kann er ebenfalls auf 0 gesetzt werden.
gegeben ist das interface sorter:
interface Sorter {
/**
* Sortiert das uebergebene array aufsteigend.
*/
public int sort(Zahlen[] array);
} |
hallo,
ich habe die obenstehende aufgabe zu lösen und brauche hilfe :)
für die klasse quicksort habe ich folgendes als lösungsansatz:
public class QuickSort implements Sorter{
private int partition(Comparable[] values, int start, int ende){
int pivot= values[ende];
int i,g;
for(i=start,g=start; i<ende; i++){
if(values[i].compareTo(pivot)<0){
swap(values, i , g);
g++;}
else if(values[i].compareTo(pivot)>0){
}
else{
swap(values, g, pivot);
}
}
return pivot;}
private void quickSort(Comparable[] values, int i, int j){
int pivot;
if(i<j){
pivot=partition(values, i ,j);
quickSort(values, i, pivot-1);
quickSort(values, pivot+1, j);
}}
public int sort( Comparable[] array ){
int i = 0;
int j = array.length-1;
quickSort(array, i, j);
return 0;
}
}
was ich leider nicht verstehe ist, wie ich mit dem datentyp comparable umgehen soll... comparable ist ja ein interface, dessen methode ich noch implementieren muss...:
public int compareTo(Object o){
if( o instanceof ?){
? a = (?) o;
int s1=this.?;
int s2=a.?;
if(s1 >s2){return 1;}
else if (s1 < s2) {return -1;}
else {return 0;}
}
else {return 1;}
}}
die methode soll also 2 instanzen miteinander vergleichen aber ich brauche doch erstmal eine klasse um die methode des interfaces comparable implementieren zu können, oder?
und für die methode mit dem rückgabewert boolean habe ich folgendes :
public static boolean istAufsteigendSortiert (Comparable[] array){
for(int i = 0; i<array.length-1; i++){
if (array[i].compareTo(array[i+1]) > 0) {
return false;
}
}
return true;
}
weitere fragen wären:
1. die methoden sind nichtstatische methoden... wie sollte ich sie denn dann aufrufen wenn ich keine weitere klasse habe, von denen ich objekte instanziieren kann?
2.darf man eine schnittstelle als datentyp für ein array benutzen und wenn, wie soll das gehen? ein interface hat ja nur methodenköpfe und konstanten...
ich würde mich rieseg auf antworten freuen und bedanke mich voraus :)
mfg ETlearner
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:22 Mo 14.05.2012 | | Autor: | rainerS |
Hallo!
> Implementieren Sie eine Klasse public class QuickSort
> implements Sorter, welche den
> QuickSort-Algorithmus in-situ implementiert. Testen Sie
> Ihren Algorithmus mit Hilfe einer Klasse
> public class TestSorter. Schreiben Sie dazu eine Methode
> boolean istAufsteigendSortiert
> (Comparable[] array), die uberpruft, ob das ubergebene
> Array aufsteigend sortiert ist (also
> ob für das gesamte Array an an+1 gilt).
> Hinweis:
> Der Algorithmus soll mithilfe von drei Methoden innerhalb
> der Klasse QuickSort realisiert
> werden:
> Die Partitionsmethode private int partition(Comparable[]
> values, int start, int
> ende) erhalt die Parameter start und ende, diese
> beschreiben den Bereich fur den values
> betrachtet werden soll. Das Element values[ende] soll als
> Pivot-Element gewahlt werden.
> Die Methode soll den angebenen Bereich von values derart
> sortieren, dass nach der Sortierung
> alle Elemente, die kleiner-gleich dem Pivot-Element sind,
> links von diesem stehen und alle die
> groer sind rechts. Es gibt aber keine Sortierung in den
> Bereichen selbst. Die Methode gibt den
> aktuellen Index des Pivot-Elements zuruck.
> Die Rekursionsmethode private void quickSort(Comparable[]
> values, int i, int j)
> soll unter Nutzung der Methode partition das Array
> baumartig rekursiv sortieren.
> Die Aufrufmethode public int sort( Comparable[] array )
> startet die Rekursion. Die
> Ruckgabe stellt die Anzahl der Rekursionsaufrufe dar und
> wird ebenfalls fur den Contest
> benotigt. Fur diese Aufgabe kann er ebenfalls auf 0
> gesetzt werden.
>
> gegeben ist das interface sorter:
> interface Sorter {
>
> /**
> * Sortiert das uebergebene array aufsteigend.
> */
> public int sort(Zahlen[] array);
>
> }
> hallo,
> ich habe die obenstehende aufgabe zu lösen und brauche
> hilfe :)
>
> [...]
Ein Tipp: schreibe Programmcode immer zwischen [code]...[/code] .
> was ich leider nicht verstehe ist, wie ich mit dem datentyp
> comparable umgehen soll... comparable ist ja ein interface,
> dessen methode ich noch implementieren muss...:
> | 1: | public int compareTo(Object o){
| | 2: | if( o instanceof ?){
| | 3: | ? a = (?) o;
| | 4: | int s1=this.?;
| | 5: | int s2=a.?;
| | 6: |
| | 7: | if(s1 >s2){return 1;}
| | 8: | else if (s1 < s2) {return -1;}
| | 9: | else {return 0;}
| | 10: | }
| | 11: | else {return 1;}
| | 12: | } |
>
> die methode soll also 2 instanzen miteinander vergleichen
> aber ich brauche doch erstmal eine klasse um die methode
> des interfaces comparable implementieren zu können, oder?
Du musst die Klasse nicht implementieren. Wenn jemand deine Quicksort-Klasse benutzen will, muss sie die öffentliche Methode sort aufrufen und dabei ein Array eines von Comparable abgeleiteten Typs übergeben. Das geht nur, wenn dieser abgeleitete Typ die Methode Comparator implementiert. Aber darum musst du dich gar nicht kümmern.
Wenn du deine Klasse testen willst, dann nimmst du am besten eine der Klassen, die Comparable implementiert, z.B. Integer, rufst also sort mit einem Integer-Array als Parameter auf.
Wenn du eine solche Klasse selbst implementierst, dann musst du die Methode Comparator definieren. Aber dann weisst du auch, wie deine Klasse heisst. Z.B in einer Klasse Zahlen weisst du, dass du Objekte vom Typ Zahlen vergleichen willst:
if( o instanceof Zahlen)
Oder du bestimmst die Klasse dynamisch (solange es keine statische Methode ist):
if( o instanceof this.getClass())
Allerdings machst du einen bösen Fehler, wenn o keine Instanz von Zahlen ist: indem du in diesem Fall 1 zurückgibst, tust du so, als hättest du erfolgreich verglichen. Wenn du nicht vergleichen kannst, musst du eine ClassCastException werfen, die ist im Interface Comparator ja explizit vorgesehen. Also:
| 1: | public int compareTo(Object o){
| | 2: | if( o instanceof Zahlen()){
| | 3: | Zahlen a = (Zahlen) o;
| | 4: | Zahlen s1=this;
| | 5: | Zahlen s2=a;
| | 6: |
| | 7: | // hier musst du geeignete Vergleiche durchführen.
| | 8: | // Du kannst ja nicht einfach s1<s2 vergleichen
| | 9: | //
| | 10: | }
| | 11: | else {throw new ClassCastException("Kann Klasse "+o.getClass().getName() + " nicht mit "+this.getClass().getName()+" vergleichen")}
| | 12: | } |
> und für die methode mit dem rückgabewert boolean habe ich
> folgendes :
>
> | 1: | public static boolean istAufsteigendSortiert (Comparable[] array){
| | 2: | for(int i = 0; i<array.length-1; i++){[/i][/i]
| | 3: | if (array[i].compareTo(array[i+1]) > 0) {
| | 4: | return false;
| | 5: | }
| | 6: | }
| | 7: | return true;
| | 8: | } |
Sieht gut aus.
> weitere fragen wären:
> 1. die methoden sind nichtstatische methoden... wie sollte
> ich sie denn dann aufrufen wenn ich keine weitere klasse
> habe, von denen ich objekte instanziieren kann?
Die Methoden sind doch innerhalb der Klasse Quicksort definiert, da kannst du sie einfach aufrufen. Oder verstehe ich dich falsch?
> 2.darf man eine schnittstelle als datentyp für ein array
> benutzen und wenn, wie soll das gehen? ein interface hat ja
> nur methodenköpfe und konstanten...
Das darfst du in deiner Klassendefinition. Zur Laufzeit muss dann eine Instanz einer echten Klasse übergeben werden. Ein Interface hat keine Instanzen, kann also zur Laufzeit auch keine aktueller Parameter sein. Aber das ist zunächst nicht dein Problem; erst wenn du testen willst.
Viele Grüße
Rainer
|
|
|
|
