Algorithmen

[Anna65]

Kann jemand mir helfen, ob ich die Implementierung richtig gemacht habe.
Das ist mein Code:

/** Alternative Implementierung zweier Sortierverfahren. */
public class Sort
{
/**
* Sortieren durch Einfügen entsprechend der natürlichen Ordnung der
* Elemente eines Arrays.
* Das Suchen nach der Einfügestelle hat hier nur den Aufwand O(log N).
* Das Verschieben hat aber weiterhin den Aufwand O(N).
* @param a Das Array, das sortiert wird.
* @param <T> Der Typ der Elemente des Arrays.
*/
public static <T extends Comparable<T>> void insertionSort(final T[] a)
{
// Implementierung hier einfügen
if(a== null || a.length== 0 || a.length == 1)

return;

insertionSort(a, 0, a.length -1);
}

private static <T extends Comparable<T>> int findInsertionPoint(T[] a, int leftIndex, int rightIndex)
{
int i = leftIndex;
int j = rightIndex;

if (rightIndex <= leftIndex)
return -1; // Ersetzen
}

/**
* QuickSort entsprechend der natürlichen Ordnung der Elemente eines
* Arrays.
* @param a Das Array, das sortiert wird.
* @param <T> Der Typ der Elemente des Arrays.
*/
public static <T extends Comparable<T>> void quickSort(final T[] a)
{
// Implementierung u.a. hier einfügen


quickSort(a, 0, a.length-1);
}

private static <T extends Comparable<T>> void quickSort( final T[]a, int leftIndex, int rightIndex) {

if (rightIndex > leftIndex) {
int pivot = selectPivot( a,leftIndex,rightIndex);
quickSort(a,leftIndex,pivot-1);
quickSort(a,pivot+1,rightIndex);
}
}

}

private static <T extends Comparable<T>> T selectPivot(T[]a, int leftIndex, int rightIndex )
{
T pivot = a[rightIndex];
int mid = leftIndex;

for (int i=mid; i< rightIndex; i++){
if (a.compareTo(pivot)<=0){
swap(a, i, mid++);
}
}
swap(a, rightIndex, mid);
return mid; // Ersetzen
}

/**
* Tauscht zwei Elemente eines Arrays aus.
* @param a Das Array, in dem die beiden Elemente getauscht werden.
* @param i Der Index des einen Elements.
* @param j Der Index des anderen Elements.
*/
private static void swap(final Object[] a, final int i, final int j)
{
final Object temp = a;
a = a[j];
a[j] = temp;
}
}

 

[Marinek]

Die Frage, die sich hier stellt, wie teste ich das.

Ich würde sagen im trivialen Fall reicht es aus, wenn

0) Sind die Aufgaben alle berücksichtigt?
Die Aufgabe 1.2 verlangt danach, dass ein System.arrayCopy verwendet wird. Du verwendest es nicht, absicht?
Mindestens eine Frage, die in der Aufgabe steht, wurde nicht beantwortet.
1) Das Programm kompiliert?

2) Was passiert, wenn du dort als Eingabe ein Array 9, 8, 7, 6, 5,4,3,2,1 übergibst? Es müsste immer sortiert aufsteigend passieren.

3) Was erwartest du hier als Antwort?

if (a.compareTo(pivot)<=0){
    swap(a, i, mid++);
}

pivot ist T und a ist ein Array von T wie vergleicht man ein einzelenes Element mit einem Array?

(Wundert man sich an der Stelle nicht, dass der Quellcode 0 formatiert im Forum steht? Obwohl alle anderen Beiträge so putzige Formate haben?)

Ich würde allein aus diesen 2 Minuten drauf schauen sagen, dass es nicht richtig implementiert ist.

Weiter würde ich behaupten, dass du es nie ausgeführt hast.

 

[mihe7]

pivot ist T und a ist ein Array von T wie vergleicht man ein einzelenes Element mit einem Array?

Der kursiven Schreibweise nach zu urteilen, steht da eigentlich:

if (a[i].compareTo(pivot)<=0){
    swap(a, i, mid++);
}