Shellsort erweitern
Sascha
ich versuche seit Sonntag einen Shellsort zum laufen zu bekommen, von
dem ich ursprünglich dachte er funktioniert, es ist der Shellsort (bzw.)
beide aus C von A-Z, jedoch haben beide einen Fehler wodurch sie nicht
richtig sortieren.
Ich habe schon gegoogelt und fand keine Lösung.
Habe nun letzten Endes folgenden Shellsort der läuft hinbekommen, dies
ist der aus Algorithmen in C, nachdem ich noch nen Fehler verbessern musste.
> void shellsort (int a[], int N) {
>
> int i, j, h, v;
> for (h = 1; h <= N/9; h = 3*h+1) ;
> for (; h > 0; h /= 3)
> for (i = h+1; i <= N; i++) {
> v = a[i];
> j = i;
> while (j >= h && a[j-h] > v) {
> a[j] = a[j-h];
> j -= h;
> }
> a[j] = v;
> }
> }
Nun möchte ich diesen Shellsort gerne so implementieren, dass ich die
Distanz als Parameter übergeben, bekam es bis jetzt jedoch nicht hin.
Hätte gerne, dass ich z.B. 9 übergebe, er zuerst im 9er Schritt durch
das Array geht, dann 5er (distanz/2+1),dann 3er und am Ende aber
1er(distanz/2).
Habe es bis jetzt nicht geschafft :(
Hier mal die version aus dem Buch, die so (falsch) arbeitet:
> void shellsort(int array[], int elemente, int distanz)
> {
> int i,j,temp,n;
> n=elemente;
> for(; n>0; n/=distanz)
> for(i=n+1; i<=elemente; i++)
> {
> temp=array[i];
> for(j=i; j>=n && array[j-n]>temp; j-=n)
> array[j]=array[j-n];
> array[j]=temp;
>
> }
>
> }
mfg Sascha Friedmann
Sascha
noch einmal in der Hoffnung dass es richtig aussieht:
void shellsort (int a[], int N) {
int i, j, h, v;
for ( h = 1; h <= N/9; h = 3*h+1);
for (; h > 0; h /= 3) {
for (i = h; i <= N; i++) {
Horst Kraemer
> Hallo alle,
> ich versuche seit Sonntag einen Shellsort zum laufen zu bekommen, von
> dem ich ursprünglich dachte er funktioniert, es ist der Shellsort (bzw.)
> beide aus C von A-Z, jedoch haben beide einen Fehler wodurch sie nicht
> richtig sortieren.
Normal. Glaube keinem Buch eines Sortieralgorithmus, wenn das Buch
nicht von Knuth oder Sedgewick stammt ;-)
Bei Knuth stimmt alles, bei Sedgewick stimmt der Algorithmus, aber bei
der Implementierung koennte es haken.
> Ich habe schon gegoogelt und fand keine Lösung.
> Habe nun letzten Endes folgenden Shellsort der läuft hinbekommen, dies
> ist der aus Algorithmen in C, nachdem ich noch nen Fehler verbessern musste.
> > void shellsort (int a[], int N) {
> >
> > int i, j, h, v;
> > for (h = 1; h <= N/9; h = 3*h+1) ;
> > for (; h > 0; h /= 3)
> > for (i = h+1; i <= N; i++) {
> > v = a[i];
> > j = i;
> > while (j >= h && a[j-h] > v) {
> > a[j] = a[j-h];
> > j -= h;
> > }
> > a[j] = v;
> > }
> > }
>
> Nun möchte ich diesen Shellsort gerne so implementieren, dass ich die
> Distanz als Parameter übergeben, bekam es bis jetzt jedoch nicht hin.
Nein. Das willst Du nicht aus den unten geschilderten Gruenden. Man
muss die Inkrementfolge von *unten* aufbauen, damit sichergestellt
ist, dass sie mit 1 endet. Wenn Du mit der Iteration
while (n/=distanz)
arbeitest, ist dies nicht gewaehrleistet. Beachtet die Inkrementfolge
z.B. bei n=8 und distanz 3: 8/3=2 , 2/3 = 0. Peng. Es werden nur die
geraden Elemente unter sich und die ungeraden Elemente unter sich
sortiert. Das reicht offensichtlich nicht, da der letzte Durchgang mit
Inkrement 1 fehlt.
Wenn Du den Distanzfaktor uebergibst, kommen eigentlich nur die Wert 2
und 3 in Frage. Die Startsequenz lautet dann.
for (h=1;h<N;h=h*distanz+1);
und dann folgt die Abarbeitung
while ( h/=distanz )
{
/* */
}
die garantiert, dass die Inkrementfolge bei
distanz=2 1 3 7 15 31 ..
distanz=3 1 4 13 40 121 ..
genau in diesser Reihenfolge ab dem groessten Wert <N rueckwaerts
durchlaufen wird.
Inkrementfolgen wie 1 2 4 8 16 oder 1 3 9 27 81 funktionieren zwar,
weil sie auch mit 1 enden, und der letzte Durchgang unter Garantie
sortiert, was noch nicht sortiert ist, aber die Laufzeit ist
gegenueber den oben erwaehnten Inkrementfolgen katastrophal, weil die
Fasern schlecht durchmischt werden. Probier es aus. Und achte immer
darauf, dass der Algorithmus nicht funktionieren kann, wenn der letzte
Durchgang nicht mit Inkrement 1 sortiert.
> Hätte gerne, dass ich z.B. 9 übergebe, er zuerst im 9er Schritt durch
> das Array geht, dann 5er (distanz/2+1),dann 3er und am Ende aber
> 1er(distanz/2).
> Habe es bis jetzt nicht geschafft :(
> Hier mal die version aus dem Buch, die so (falsch) arbeitet:
> > void shellsort(int array[], int elemente, int distanz)
> > {
> > int i,j,temp,n;
> > n=elemente;
> > for(; n>0; n/=distanz)
Dieser Algorithmus muss deshalb falsch sein, weil das letzte n>0
zwingend 1 sein muss, was bei der folge n/=distanz nicht der Fall sein
muss, denn der letzte Schritt des Algorithmus muss immer ein
"normales" Bubblesort mit Inkrement 1 sein.
Wie haeufig zu beobachten ist, haben die Autoren den Algorithmus nicht
verstanden und versucht, ihn zu "verbessern".
MfG
Horst
Sascha
seit Tagen suche (nur ohne es zu wissen) :-)
mfg Sascha