Sortieren durch Einfügen (Insertionsort). Lothar Färber Gymnasium Am Anger 2 gegeben: unsortierte...

Preview:

Citation preview

Sortieren durch Einfügen(Insertionsort)

Lothar Färber Gymnasium Am Anger

2

gegeben: unsortierte Zahlenreihe: zahlen[1] bis zahlen[6]

5 2 7 4 8 1

[1] [2] [3] [4] [5] [6]

Lothar Färber Gymnasium Am Anger

3

das erste Datum wird als vorsortiert angesehen

5 2 7 4 8 1

[1] [2] [3] [4] [5] [6]

Lothar Färber Gymnasium Am Anger

4

alle weiteren Daten müssen nacheinander an der richtigen Stelle eingefügt werden, zunächst geht es um zahlen[2]

5 2 7 4 8 1

[1] [2] [3] [4] [5] [6]

Lothar Färber Gymnasium Am Anger

5

das aktuelle Datum wird in merke zwischen gespeichert

5 2 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 2

Lothar Färber Gymnasium Am Anger

6

ich werde merke mit Vorgänger(n) vergleichen

5 2 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 2

Lothar Färber Gymnasium Am Anger

7

da 2<5 5 muss nach rechts verschoben werden, damit auf seiner alten Position Platz für das mögliche Einfügen der 2 geschaffen wird

5 2 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 2

Lothar Färber Gymnasium Am Anger

8

ich habe die 5 in zahlen[2] kopiert

5 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 2

Lothar Färber Gymnasium Am Anger

9

ich werde Inhalt von merke in zahlen[1] kopieren

5 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 2

Lothar Färber Gymnasium Am Anger

10

ich habe Inhalt von merke in zahlen[1] kopiert

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 2

Lothar Färber Gymnasium Am Anger

11

zahlen[1] und zahlen[2] sind vorsortiert

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 2

Lothar Färber Gymnasium Am Anger

12

ich habe Laufzeiger um 1 weiter gerückt

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 2

Lothar Färber Gymnasium Am Anger

13

ich habe Inhalt von zahlen[3] in merke kopiert

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 7

Lothar Färber Gymnasium Am Anger

14

Inhalt von merke wird mit Vorgänger(n) verglichen

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 7

Lothar Färber Gymnasium Am Anger

15

da 7>5 7 steht bereits an richtiger Position

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 7

Lothar Färber Gymnasium Am Anger

16

zahlen[1] bis zahlen[3] sind vorsortiert

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 7

Lothar Färber Gymnasium Am Anger

17

ich habe Laufzeiger um 1 weiter gerückt

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 7

Lothar Färber Gymnasium Am Anger

18

ich habe Inhalt von zahlen[4] in merke kopiert

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

19

Inhalt von merke wird mit Vorgänger(n) verglichen

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

20

4<7 7 muss nach rechts verschoben werden

2 5 7 4 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

21

ich habe die 7 in zahlen[4] kopiert

2 5 7 7 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

22

4<5 5 muss nach rechts verschoben werden

2 5 7 7 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

23

ich habe die 5 in zahlen[3] kopiert

2 5 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

24

4>2 die 2 steht richtig, die gemerkte 4 muss rechts neben der 2 - also in zahlen[2] - eingefügt werden

2 5 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

25

ich habe die 4 in zahlen[2] kopiert

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

26

zahlen[1] bis zahlen[4] sind vorsortiert

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

27

ich habe Laufzeiger 1 weiter gerückt

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 4

Lothar Färber Gymnasium Am Anger

28

ich habe Inhalt von zahlen[5] gemerkt

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 8

Lothar Färber Gymnasium Am Anger

29

ich werde merke mit Vorgänger(n) vergleichen

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 8

Lothar Färber Gymnasium Am Anger

30

da 8>7 8 steht an richtiger Position

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 8

Lothar Färber Gymnasium Am Anger

31

zahlen[1] bis zahlen[5] sind vorsortiert

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

merke 8

Lothar Färber Gymnasium Am Anger

32

ich habe Laufzeiger um 1 weiter gerückt

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

8

Lothar Färber Gymnasium Am Anger

33

ich habe Inhalt von zahlen[6] gemerkt

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

34

ich vergleiche merke mit Vorgänger(n)

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

35

da 1<8 8 nach rechts verschieben

2 4 5 7 8 1

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

36

ich habe die 8 in zahlen[6] kopiert

2 4 5 7 8 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

37

ich vergleiche merke mit zahlen[4]

2 4 5 7 8 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

38

da 1<7 7 nach rechts verschieben

2 4 5 7 8 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

39

ich habe die 7 in zahlen[5] kopiert

2 4 5 7 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

40

ich vergleiche merke mit zahlen[3]

2 4 5 7 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

41

da 1<5 5 nach rechts verschieben

2 4 5 7 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

42

habe 5 in zahlen[4] kopiert

2 4 5 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

43

ich vergleiche merke mit zahlen[2]

2 4 5 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

44

da 1<4 4 nach rechts verschieben

2 4 5 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

45

habe 4 in zahlen[3] kopiert

2 4 4 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

46

ich vergleiche merke mit zahlen[1]

2 4 4 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

47

da 1<2 2 nach rechts verschieben

2 4 4 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

48

habe 2 in zahlen[2] kopiert

2 2 4 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

49

ich werde merke in zahlen[1] kopieren

2 2 4 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

50

ich habe die 1 in zahlen[1] kopiert

1 2 4 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

51

alle Zahlen liegen nun sortiert vor

1 2 4 5 7 8

[1] [2] [3] [4] [5] [6]

1

Lothar Färber Gymnasium Am Anger

52

Einfügesort beendet

Recommended