Shell-Sort (D. L. Shell 1959)
Verbesserung des Einfügeverfahrens Sortieren
durch Einfügen mit abnehmender Schrittweite
Beispiel: Schrittweiten – h[1]
= 4; h[2] = 2; h[3] = 1
Struktogramm - Shell-Sort
Durch dieses Struktogramm und mit den gegebenen Beispielwerten, ergibt sich folgende Tracing-Tabelle:
INDEX I |
1 |
2 |
3 |
4 |
5 |
M |
SCHW |
I |
EE |
VI |
ELEMENT E[I] |
17 |
9 |
10 |
6 |
12 |
1 |
4 |
5 |
12 |
1 |
17 |
-3 |
|||||||||
12 |
||||||||||
12 |
9 |
10 |
6 |
17 |
2 |
2 |
3 |
10 |
1 |
|
12 |
-1 |
|||||||||
10 |
||||||||||
10 |
9 |
12 |
6 |
17 |
4 |
6 |
2 |
|||
9 |
0 |
|||||||||
6 |
||||||||||
10 |
6 |
12 |
9 |
17 |
5 |
17 |
3 |
|||
17 |
||||||||||
10 |
6 |
12 |
9 |
17 |
3 |
1 |
2 |
6 |
1 |
|
10 |
0 |
|||||||||
6 |
||||||||||
6 |
10 |
12 |
9 |
17 |
3 |
12 |
2 |
|||
12 |
||||||||||
12 |
4 |
9 |
3 |
|||||||
10 |
2 |
|||||||||
9 |
1 |
|||||||||
6 |
9 |
10 |
12 |
17 |
5 |
17 |
4 |
|||
17 |
||||||||||
6 |
9 |
10 |
12 |
17 |
Programm-Code (in Java)
/** Created on 11.01.2004
*/
import shell_sort.Shell_sort;
/**
* @author Florian Ercevic
*/
public class mainEx {
public static void main(String[] args) {
Shell_sort SS = new Shell_sort();
SS.fillArray();
System.out.println("unsortiert für Shell Sort");
for(int i=1;i<6;i++)
{
System.out.print(SS.Array1[i]+" ");
}
SS.sortArray();
System.out.println();
System.out.println("sortiert nach Shell Sort");
for(int i=1;i<6;i++)
{
System.out.print(SS.Array1[i]+" ");
}
System.out.println();
}
}
/*
* Created on 11.01.2004
*/
package shell_sort;
/**
* @author Florian Ercevic
*/
import java.util.Random;
public class Shell_sort
{
Random generator = new Random();
int N=5;
public int [] Array1 = new int[N+1];
public int [] fillArray()
{
for(int i=1;i<N+1;i++)
{
Array1[i] = 1 + generator.nextInt(100);
}
return Array1;
}
public int [] sortArray()
{
int VI=0,M=0,EE=0,SCHW=0;
int [] H = new int[4]; /*von 1 bis 3*/
H[1]=4; H[2]=2; H[3]=1;
for(int m=1;m<4;m++)
{
SCHW=H[m];
for(int i=SCHW+1;i<N+1;i++)
{
EE=Array1[i];
VI=i-SCHW;
while((VI>0)&&(EE<Array1[VI]))
{
Array1[VI+SCHW]=Array1[VI];
VI=VI-SCHW;
}
Array1[VI+SCHW]=EE;
}
}
return Array1;
}
}
