Insertion Sort Aufgabe?
Wir haben folgenden Algorithmus für Insertion-Sort:
void InsertionSort int a[], int n) {
int i, j, key;
for(j = 1; j < n; j++) {
key = a[j];
i = j-1;
while (i >= 0 && a[i] > key){
a[i+1] = a[i];
i = i-1;
}
a[i+1] = key;
}
}
Die Aufgabe lautet:
Drehen Sie die Reihenfolge bei InsertionSort: Statt uber das Maximum einzusortieren, soll uber das Minimum einsortiert werden.
Ich verstehe die Aufgabe nicht. Wo wird denn "über das Maximum einsortiert", was bedeutet das?
Ich verstehe wie der Algorithmus funktioniert ... wenn da steht 671, und man bei j = 2 angelangt ist, dann wird 671 -> 677 -> 667 -> 167.
Aber ich verstehe nicht wo da "über das Maximum einsortiert" wird, oder was ich da nun ändern soll, oder wie ich das ändern sollte.
Könnte mir das wer erklären?
2 Antworten
// int a[]: Integer-Array das sortiert werden soll
// n: Der Bereich 0..n, der sortiert werden soll
void InsertionSort(int[] a, int n)
{
int i, j, key;
// Schleife über den Sortierbereich
for (j = 1; j < n; j++)
{
// Ein Schlüssel-Array-Element nach dem anderen auswählen
// bei eins beginnend
key = a[j];
// Index des Vorgängers
i = j - 1;
// Solange Index des Vorgängers >=0 (also mid. Anfang des Arrays) und
// der Wert des Vorgängers größer als der Wert des Schlüssel-Array-Elements ist
while (i >= 0 && a[i] > key)
{
//Vorgänger nach rechts verschieben (überschreibt den Nachfolger)
a[i + 1] = a[i];
// Mit dem Vorgängers des Vorgängers weitermachen
i = i - 1;
}
//Nach der Schleife ist der Vorgänger nicht mehr grösser oder nicht vorhanden
// Hier wird nun das Schlüssel-Array-Element eingesetzt
a[i + 1] = key;
}
}
Ich verstehe die Aufgabe nicht. Wo wird denn "über das Maximum einsortiert", was bedeutet das?
Ich habe Erklärungen als Kommentare in den Code geschrieben. Du musst nun alles umdrehen. Du musst also mit dem Nachfolger arbeiten und die Bedingung umkehren (a[i] < key, i = i + 1, i <= n)
Was heißt denn "über das Maximum einsortiert" ganz konkret? Ich verstehe dieses Deutsch nicht. Was oder Wo ist das "Maximum", und was heißt "über etwas einsortieren"...
Heißt das, dass alles von kleinste Zahl -> größte Zahl sortiert wird? Und das soll ich nun umdrehen, also größte Zahl links und kleinste Zahl rechts? Oder wie?
Wie gesagt verstehe ich den Algorithmus, ich verstehe nur die Aufgabe nicht.
Was heißt denn "über das Maximum einsortiert" ganz konkret? Ich verstehe dieses Deutsch nicht.
Der Schlüssel wird solange nach links verschoben bis der linke Nachbar nicht mehr grösser ist (das ist wohl mit dem Maximum gemeint).
Jetzt musst du:
Der Schlüssel wird solange nach rechts verschoben bis der rechte Nachbar nicht mehr kleiner ist (über das Minimum).
Heißt das, dass alles von kleinste Zahl nach größte Zahl sortiert wird? Und das soll ich nun umdrehen, also größte Zahl links und kleinste Zahl rechts?
Die Sortierung soll gleich bleiben: links klein, rechts groß.
Nur die Richtung (jetzt nach rechts) soll geändert werden, dafür die Bedingung umgedreht, damit das gleiche Ergebnis entsteht