Sortieren durch EINFÜGEN - Direktes Einfügen (straight insertion)
Struktogramm - Direktes Einfügen (straight insertion)
Beispiel: Datenfeld mit 5 Elementen
INDEX I |
1 |
2 |
3 |
4 |
5 |
I |
Einfügeelement EE |
VI |
ELEMENT E[I] |
17 |
9 |
10 |
6 |
12 |
2 |
9 |
1 |
|
17 |
17 |
10 |
6 |
12 |
|
|
0 |
|
9 |
17 |
10 |
6 |
12 |
3 |
10 |
2 |
|
9 |
17 |
17 |
6 |
12 |
|
|
1 |
|
9 |
10 |
17 |
6 |
12 |
4 |
6 |
3 |
|
9 |
10 |
17 |
17 |
12 |
|
|
2 |
|
9 |
10 |
10 |
17 |
12 |
|
|
1 |
|
9 |
9 |
10 |
17 |
12 |
|
|
0 |
|
6 |
9 |
10 |
17 |
12 |
5 |
12 |
4 |
|
6 |
9 |
10 |
17 |
17 |
|
|
3 |
|
6 |
9 |
10 |
12 |
17 |
|
|
|
Algorithmus:
(Grobstruktur)
Finde für das Einfügeelement EE:=E[I] die richtige
Stelle in der bereits sortierten Teilfolge E[1] ...E[I-1] und ordne
das Einfügeelement EE dort ein!Programm-Code (in Java)
public class mainEx {
public static void main(String[] args) {
Straight_insertion X = new Straight_insertion();
X.fillArray();
System.out.println("unsortiert");
for(int i=1;i<6;i++)
{
System.out.print(X.Array1[i]+" ");
}
X.sortArray();
System.out.println();
System.out.println("sortiert");
for(int i=1;i<6;i++)
{
System.out.print(X.Array1[i]+" ");
}
}
package straight_insertion;
/*
* Created on 11.01.2004
*/
/**
* @author Florian Ercevic
*/
import java.util.Random;
public class Straight_insertion
{
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,EE=0;
for(int i=2;i<N+1;i++)
{
EE=Array1[i];
VI=i-1;
while(EE<Array1[VI] && VI>0)
{
Array1[VI+1]=Array1[VI];
VI=VI-1;
}
Array1[VI+1]=EE;
}
return Array1;
}
}
