Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithmen und Datenstrukturen SS2018 > Kapitel 6: Sortieralgorithmen > Flashcards

Kapitel 6: Sortieralgorithmen Flashcards

1
Q

Was ist internes sortieren ?

A

Sortieren von Daten im Hauptspeicher, direkter Zugriff

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

was ist externes sortieren ?

A

Sortieren von Dateien auf externen Datenträger, sequentieller Zugriff

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Was ist Stabilität ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Was ist natürliches Verhalten ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Was ist Insertion Sort ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Weist Insertion Sort Stabilität auf ?

A

Ja

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Weist Insertion Sort ein natürliches Verhalten auf ?

A

Ja

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Was ist Selection Sort ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Weist Selection Sort Stabilität auf ?

A

Nein

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Weist Selection Sort ein natürliches Verhalten auf ?

A

Nein

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Wann ist Selection Sort Empfehlenswert ?

A

Bei teuren Bewegungen der Daten

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Wann ist Insertion Sort Empfehlenswert ?

A

Bei kleinen Eingabefolgen (n<100)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Was ist BubbleSort ?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Weist BubbleSort Stabilität auf ?

A

Ja

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Weist BubbleSort ein natürliches Verhalten auf ?

A

Bei den Vergleichen nicht, bei den Bewegungen schon.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Insertion Sort Aufwand Vergleiche

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

Selection Sort Aufwand Vergleiche

A 
Vmin = O(n^2/2)
Vavg = O(n^2/2)
VMax = O(n^2/2)
18
Q

Bubble Sort Aufwand Vergleiche

A 
Vmin = O(n^2/2)
Vavg = O(n^2/2)
VMax = O(n^2/2)
19
Q

Insertion Sort Aufwand Bewegungen

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

Selection Sort Aufwand Bewegungen

A 
Bmin = O(3n)
Bavg = O(3n)
Bax = O(3n)
21
Q

Bubble Sort Aufwand Bewegungen

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

Was ist Shell Sort ?

A

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

23
Q

Was wendet Shell Sort auch noch an ?

A

Insertion Sort

24
Q

Weist Shell Sort Stabilität auf ?

A

Nein

25
Q

Weist Shell Sort ein natürliches Verhalten auf ?

A

Ja wenn Teilfolgen im Abstand GAP teilweise sortiert sind

26
Q

Was ist Merge Sort ?

A

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

27
Q

Weist Merge Sort Stabilität auf ?

A

Ja

28
Q

Weist Merge Sort ein natürliches Verhalten auf ?

A

Ja

29
Q

Was ist Quick Sort ?

A

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.

30
Q

Was ist der Cross Over Point ?

A

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

31
Q

MinHeap Eigenschaften

A
  • Binärbuam
  • Vollständiger Baum
  • Schlüssel jeder Knoten <= Schlüssel seiner Kinder
  • Kein BST!
32
Q

HeapSort: Kindknoten zu A[i]:

A

Linker Knoten = A[2*i+1]

Rechter Knoten = A[2*i+2]

33
Q

HeapSort: Elternknoten zu A[i]:

A

A[(i-1)/2]

34
Q

Was macht der percDown Algorithmus ?

A

“Durchsickern” der Elemente nach unten

35
Q

Auf welche Teile des Arrays muss percDown aufgerufen werden ?

A

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

36
Q

Was ist Heap Sort ?

A

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.

37
Q

Weist Heap Sort Stabilität auf ?

A

Nein

38
Q

Weist Heap Sort ein natürliches Verhalten auf ?

A

Ja

39
Q

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

A

Min-Heap

Algorithmen und Datenstrukturen SS2018 (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions