Shellsort Sortierung

REC

Bekanntes Mitglied
Hallo, ich sollte als Aufgabe den Shellshort programmieren.
Doch ich habe noch ein paar Verständissfragen.

Zuerst einmal verstehe ich nicht mal ganz die Schrittweite berechnung :noe:

1,4,13,40,121,364,... -> allgemein h[k] = 3 x h[k-1]+1; h[1]=1


dabei bedeutet h[k] die Schrittweite der kten Sortierung.

Das heisst für mich mit der Schrittweite 13 "3 x 13[3-1] +1" Ist ja der 3 Durchgang
Nur leider ergibt das 79 anstatt 40?

Hingegen wenn ich immer die vorgehende Schrittweite nehme und rechne 3 x 13 +1 = 40 Dann stimmt es immer? Also kann ich auch diese Vorgehensweise nehmen?
Doch nun komm ich gleich zum nächsten Problem. Eigentlich muss ich ja mit der höchsten Zahl beginnen. Das heisst ich brauche ja eine Formel um den nächst kleineren Schritt auszurechenen.
Warum erhalten wir dann diese Formel h[k] = 3 x h[k-1]+1; h[1]=1?
Denn wenn ich es das im Java programmier brauch ich ja eine Formel um die Schrittweite jedesmal zu reduzieren bis auf 1 runter?


Die eigentliche Vorgehensweise von Shellshort geht so.
Man nimmt jede, sagen wir mal jede 13 Zahl. Das gibt dann ein paar Gruppen.
Diese Gruppen sortiert man nun.
Danach macht man wieder Gruppen mit jeder 4 Zahl.Die enstandenen Gruppen sortiert man wieder mit direktes Einfügen.
Das macht man bis man den 1 Schritt hat.

Um diese Gruppen zu sortieren brauche ich keine zusätzliche Arrays,oder? Ich kann gleich alle Zahlen an die richtigen Stellen verschieben?

So ich hoffe man hat meine 2-3 Fragen verstanden :)
 

akimoon

Aktives Mitglied
ich tippe mal, du verwendest knuths-algorithmus zum berechnen der Schrittweite? Zumindest glaube ich, dass dies die Formel war?
Wenn ja, steckt in "Das heisst für mich mit der Schrittweite 13 "3 x 13[3-1] +1" der Fehler:
h ist in deinem Fall das Array und k ist der index, nicht der wert.. das heißt: h[3] = 3*h[3-1]+1 ---> da h[2] ja 13 war ergibt das: 3*13+1 = 40.
Die nächste Zahl wird immer berechnet, indem die letzte mit 3 multipliziert wird und anschließend 1 addiert.

Um auf deine letzte Frage einzugehen: Es reicht auch ein Array dafür. Ein einfaches Beispiel hierzu wäre (Konstante SPALTEN :

Java:
    final static int[] SPALTEN = {2147483647, 1131376761, 410151271, 157840433,
        58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331,
        84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1};


public static void shellsort(long[] a) {
        long temp;
        int i, j, k, h;

        for (k = 0; k < 23; k++) {  //Spaltengröße verändern
            h = SPALTEN[k];
            // Sortiere die "Spalten" mit Insertionsort
            for (i = h; i < a.length; i++) {
                temp = a[i];
                j = i;
                while (j >= h && a[j - h] > temp) { //Elemente werden nach hinten
                    a[j] = a[j - h];              //wenn sie größer sind
                    j = j - h;
                }
                a[j] = temp;   //aktuelles Element wird dem letzt-getauschten Index zugewiesen
            }
        }
    }
 

REC

Bekanntes Mitglied
Hey Danke für eure Antworten.

Aber diese Formel braucht man ja eben um die Schrittweite zu berechnen. Das mache ich ja jedesmal vor einem erneutem Sortiervorgang?

Ich seh einfach nicht den Zusammenhang zwischen dieser Schreibweise h[3] = 3*h[3-1]+1 und der normalen Variante 3*13+1 = 40. Weil,mal ne blöde Frage wie soll ich den den Array h multiplizieren,das geht ja nicht????:L

Was genau sagt mir denn h[3] = 3*h[3-1]+1? Ich mein das ist ja einfach ein Index? Wie komme ich nun auf den nächsten Index?
Weil das 3*h[3-1]+1 ergibt für mich 7 ;)


Noch ne andere Frage,wenn ich zum Beispiel mit 100'000Einheiten anfange wie komme ich dann auf die grösste Schritteinheit. Um nachher mit der Schrittweite nach jedem durchgang kleiner zu werden?



Ach ja Danke für deinen Code.Aber ich werde versuchen ihn selber zu erarbeiten ;)
 

Mizar

Aktives Mitglied
Was genau sagt mir denn h[3] = 3*h[3-1]+1? Ich mein das ist ja einfach ein Index? Wie komme ich nun auf den nächsten Index?
Weil das 3*h[3-1]+1 ergibt für mich 7 ;)
Diese Formel sagt nichts anderes aus als:
[momentane Schrittweite] = 3 * [vorherige Schrittweite] + 1
Beispiel:
Du hast die erste bzw. kleinste Schrittweite gegeben.
h[0] = 1
Und jetzt setzt du einfach ein:
h[1] = 3 * 1 + 1 = 4
h[2] = 3 * 4 + 1 = 13
h[3] = 3 * 13 + 1 = 40
h[4] = 3 * 40 + 1 = 121
usw. usf. :)
Aber diese Formel braucht man ja eben um die Schrittweite zu berechnen. Das mache ich ja jedesmal vor einem erneutem Sortiervorgang?
[...]
Noch ne andere Frage,wenn ich zum Beispiel mit 100'000Einheiten anfange wie komme ich dann auf die grösste Schritteinheit. Um nachher mit der Schrittweite nach jedem durchgang kleiner zu werden?
Die Schrittweiten musst du nicht jedesmal neu berechnen. Du kannst auch in einem Rutsch alle Schrittweiten berechnen die du für deine Anzahl an Elementen brauchst. So zum Beispiel:
Java:
public static void main(String[] args)
{
	int elements = 100000; // Deine Anzahl an "Einheiten".
	LinkedList<Integer> stepRanges = new LinkedList<Integer>();
	// Alle Schrittweiten ermitteln die kleiner sind als die Anzahl an "Einheiten". 
	for(int currentStepRange = 1; currentStepRange < elements; currentStepRange = 3 * currentStepRange + 1) {
		stepRanges.add(currentStepRange);
	}
	// Alle Schrittweiten ausgeben.
	for(Integer i: stepRanges) {
		System.out.println(i);
	}
}
 

REC

Bekanntes Mitglied
Ach so :toll:
Hey Danke für eure Erklärungen,das letzte Beispiel hat es mir endgültig verständlich gemacht.

Und die Idee ist auch ziemlich gut. Das ich zuerst alle Schrittweite berechene. Habe immer nach einer Möglichkeit gesucht das dies während dem Sortieren passiert. So ist es aber besser gelöst:)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
R Shellsort Java Basics - Anfänger-Themen 1
T sortierung der eingabe nach größe Java Basics - Anfänger-Themen 5
U Sortierung in collections testen Java Basics - Anfänger-Themen 11
A Sortierung Java Basics - Anfänger-Themen 18
G Java Sortierung Java Basics - Anfänger-Themen 3
P topologische Sortierung Java Basics - Anfänger-Themen 15
N Best Practice Ist die Sortierung richtig? Java Basics - Anfänger-Themen 3
M Topologische Sortierung Java Basics - Anfänger-Themen 1
S Sortierung Java Basics - Anfänger-Themen 4
K Sortierung eines int-Arrays von groß nach klein Java Basics - Anfänger-Themen 3
S Sortierung funktioniert nicht Java Basics - Anfänger-Themen 1
S Was ist schneller: direkte Sortierung oder indirekt ueber eine SortedMap..? Java Basics - Anfänger-Themen 10
F Collections Sortierung und Einfügen von Elementen Java Basics - Anfänger-Themen 1
L Lexikographische Sortierung eines Strings Java Basics - Anfänger-Themen 6
A Kleinste Ziffer im Array suchen um Sortierung zu erzeugen Java Basics - Anfänger-Themen 2
S Dateien/LinkedList/StringBuffer - SOrtierung klappt nicht so ganz Java Basics - Anfänger-Themen 2
D Sortieren in Abhängigkeit von einer anderen Sortierung Java Basics - Anfänger-Themen 14
K Sortierung von Zahlen Java Basics - Anfänger-Themen 13
S Sortierung funktioniert nicht Java Basics - Anfänger-Themen 9
B Hiilfee! Step by Step sortierung eines Arrays... Java Basics - Anfänger-Themen 19
G Bubblesort - Falsche Sortierung Java Basics - Anfänger-Themen 6
T Datenstruktur für Sortierung Java Basics - Anfänger-Themen 4
S Collections Sortieren von 3 Collections nach "einer Sortierung" Java Basics - Anfänger-Themen 3
K Sortierung von Anzahl der Wörtern in ArrayList Java Basics - Anfänger-Themen 4
U Alter Berechnung + sortierung Java Basics - Anfänger-Themen 6
H Sortierung eines String[][] mit Bedingung Java Basics - Anfänger-Themen 7
M Frage zur Sortierung Java Basics - Anfänger-Themen 8
S problem mit sortierung interface comperator Java Basics - Anfänger-Themen 11
B OOP Comparator - Sortierung "optisch" Darstellen Java Basics - Anfänger-Themen 17
F Treemap und Sortierung? Java Basics - Anfänger-Themen 2
L Random Sortierung Java Basics - Anfänger-Themen 9
A Sortierung (Gernerics & Liste) Java Basics - Anfänger-Themen 9
J Sortierung Java Basics - Anfänger-Themen 11
F compareTo - Sortierung nach 2 Argumenten Java Basics - Anfänger-Themen 10
? hilfe bei Fehlersuche Sortierung List Java Basics - Anfänger-Themen 5
O Sortierung Denkanstoss Java Basics - Anfänger-Themen 7
G ArrayList mit ArrayList als Inhalt - komische Sortierung? Java Basics - Anfänger-Themen 12
P Brauche Hilfe bei Sortierung eines JTrees ! Java Basics - Anfänger-Themen 14
K Kurze Frage zur Sortierung von Array-Inhalten Java Basics - Anfänger-Themen 5
G String Sortierung nach mehreren Kriterien Java Basics - Anfänger-Themen 4
G Sortierung eines Arrays nach mehreren Kriterien Java Basics - Anfänger-Themen 6
Q HashMap Sortierung Java Basics - Anfänger-Themen 11
S Sortierung Rückgängig machen?! Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben