Kapitel 6: Sortieralgorithmen

Question 1

Was ist internes sortieren ?

Answer 1

Sortieren von Daten im Hauptspeicher, direkter Zugriff

Question 2

was ist externes sortieren ?

Answer 2

Sortieren von Dateien auf externen Datenträger, sequentieller Zugriff

Question 3

Was ist Stabilität ?

Answer 3

Bei gleichen Schlüsseln (Duplikaten) bleibt die Reihenfolge der Objekte erhalten

Question 4

Was ist natürliches Verhalten ?

Answer 4

Bei bereits (weitgehend) sortierter Ausgangsfolge ist die Ausführungszeit am geringsten.

Question 5

Was ist Insertion Sort ?

Answer 5

Das 1. Element der umsortieren Teilfolge (index i) anschauen und in sortierte Teilfolge einsetzen (an die richtige Stelle (von rechts nach links geschaut))

Question 6

Weist Insertion Sort Stabilität auf ?

Answer 6

Ja

Question 7

Weist Insertion Sort ein natürliches Verhalten auf ?

Answer 7

Ja

Question 8

Was ist Selection Sort ?

Answer 8

Suche in der unsortierten TF das Minimum und vertausche das Minimum mit dem 1. Platz der unsortierten TF

Question 9

Weist Selection Sort Stabilität auf ?

Answer 9

Nein

Question 10

Weist Selection Sort ein natürliches Verhalten auf ?

Answer 10

Nein

Question 11

Wann ist Selection Sort Empfehlenswert ?

Answer 11

Bei teuren Bewegungen der Daten

Question 12

Wann ist Insertion Sort Empfehlenswert ?

Answer 12

Bei kleinen Eingabefolgen (n<100)

Question 13

Was ist BubbleSort ?

Answer 13

Starte am Ende der Folge und vertausche benachbarte Elemente. Die jeweils kleineren Elemente steigen nach oben bzw. vorne im Array und das Minimum der unsortierten Teilfolge bis zur 1. Position der Unsortierten Teilfolge.

Question 14

Weist BubbleSort Stabilität auf ?

Answer 14

Ja

Question 15

Weist BubbleSort ein natürliches Verhalten auf ?

Answer 15

Bei den Vergleichen nicht, bei den Bewegungen schon.

Question 16

Insertion Sort Aufwand Vergleiche

Answer 16

Vmin = O(n)
Vavg = O(n^2/4)
VMax = O(n^2/2)

Question 17

Selection Sort Aufwand Vergleiche

Answer 17

Vmin = O(n^2/2)
Vavg = O(n^2/2)
VMax = O(n^2/2)

Question 18

Bubble Sort Aufwand Vergleiche

Answer 18

Vmin = O(n^2/2)
Vavg = O(n^2/2)
VMax = O(n^2/2)

Question 19

Insertion Sort Aufwand Bewegungen

Answer 19

Bmin = O(3n)
Bavg = O(n^2/4)
Bax = O(n^2/2)

Question 20

Selection Sort Aufwand Bewegungen

Answer 20

Bmin = O(3n)
Bavg = O(3n)
Bax = O(3n)

Question 21

Bubble Sort Aufwand Bewegungen

Answer 21

Bmin = 0
Bavg = O(3n^2/4)
Bax = O(3n^2/2)

Question 22

Was ist Shell Sort ?

Answer 22

Mit einem (anfangs größtmöglichen) gap werden die Elemente verglichen. Gap wird anschließend immer halbiert (Insertion Sort)

Question 23

Was wendet Shell Sort auch noch an ?

Answer 23

Insertion Sort

Question 24

Weist Shell Sort Stabilität auf ?

Answer 24

Nein

Question 25

Weist Shell Sort ein natürliches Verhalten auf ?

Answer 25

Ja wenn Teilfolgen im Abstand GAP teilweise sortiert sind

Question 26

Was ist Merge Sort ?

Answer 26

Aufteilen einer Folge in Teilfolgen (bis TF nurnoch 1 Element beinhalten). TF werden anschließend Gemerged und dabei sortiert

Question 27

Weist Merge Sort Stabilität auf ?

Answer 27

Ja

Question 28

Weist Merge Sort ein natürliches Verhalten auf ?

Answer 28

Ja

Question 29

Was ist Quick Sort ?

Answer 29

Pivotelement wird ausgewählt, anschließend werden alle Elemente die kleiner oder größer gleich sind in entsprechende Teilfolgen gepackt. Rekursiv wird QuickSort dann auch auf die TF angewendet.

Question 30

Was ist der Cross Over Point ?

Answer 30

Der Punkt (n Datensätze) an denen ein Algorithmus schneller ist als ein anderer (sie kreuzen sich)

Question 31

MinHeap Eigenschaften

Answer 31

- Binärbuam - Vollständiger Baum - Schlüssel jeder Knoten <= Schlüssel seiner Kinder - Kein BST!

Question 32

HeapSort: Kindknoten zu A[i]:

Answer 32

Linker Knoten = A[2*i+1] | Rechter Knoten = A[2*i+2]

Question 33

HeapSort: Elternknoten zu A[i]:

Answer 33

A[(i-1)/2]

Question 34

Was macht der percDown Algorithmus ?

Answer 34

"Durchsickern" der Elemente nach unten

Question 35

Auf welche Teile des Arrays muss percDown aufgerufen werden ?

Answer 35

A[0..(n-1)/2] also auf die erste Hälfte des Arrays (alles keine Blattknoten)

Question 36

Was ist Heap Sort ?

Answer 36

Ein Array wird durch den Heap-Aufbau so vorsortiert das alle Knoten nurnoch kleinere oder größere (min/max heap) Nachfolger haben. Anschließend wird von jedem heap sortiert.

Question 37

Weist Heap Sort Stabilität auf ?

Answer 37

Nein

Question 38

Weist Heap Sort ein natürliches Verhalten auf ?

Answer 38

Ja

Question 39

Was liefert eine absteigende Sortierung, Min- oder Max-Heap ?

Answer 39

Min-Heap