# Shellsort Sortierung



## REC (12. Feb 2011)

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


----------



## HoaX (12. Feb 2011)

Schau doch mal hier, da gibts super Erklärungen:
Sequentielle und parallele Sortierverfahren


----------



## akimoon (13. Feb 2011)

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 :


```
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 (13. Feb 2011)

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 (14. Feb 2011)

REC hat gesagt.:


> 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. 


REC hat gesagt.:


> 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:

```
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 (20. Feb 2011)

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


----------

