# 3.4 Selection Sort

Quelle: https://inf.zone/lectures/3-algorithmen/short-3-4-selection-sort/

## Video

[Video ansehen (1080p)](https://videos.inf.zone/ffb9065bf0ce7e23/short-3-4-selection-sort-1080p.mp4) · [Video (720p)](https://videos.inf.zone/ffb9065bf0ce7e23/short-3-4-selection-sort-720p.mp4) · [Video (480p)](https://videos.inf.zone/ffb9065bf0ce7e23/short-3-4-selection-sort-480p.mp4) · [Video auf YouTube](https://youtu.be/IbZvEaUX61I)

## Material

- [Folien](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf)
- Folien und Transkript: unten auf dieser Seite

## Folien und Transkript

*Folientext aus den PDF-Folien, darunter jeweils der gesprochene Text des Videos. Der gesprochene Text ist maschinell transkribiert und nachkorrigiert, kann aber noch Fehler enthalten; im Video sprechen abwechselnd Prof und eine AI-Figur, die Sprecherwechsel sind nicht markiert. Die Zuordnung zu den Folien ist ungefähr. Die Zeitangaben verlinken auf die Stelle im Video (YouTube). Maßgeblich sind Video und Folien.*

### Folie 1 — Selection Sort

[Folie 1 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=1)

#### Transkript

**[Video 00:00–00:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=0)**

Dies ist Inf-Einf-B. Heute Selection Sort.

### Folie 2

[Folie 2 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=2)

Beim Selection Sort (auf Deutsch: „Auswahlsortierung“) besteht die Idee des Algorithmus darin, das kleinste unsortierte Element zu finden und nach vorne zu bringen, also an den Anfang des noch unsortierten Bereichs.

#### Transkript

**[Video 00:00–00:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=0)**

Willkommen zu unserer heutigen Vorlesung über Sortieralgorithmen. Heute werden wir uns mit einem grundlegenden, aber sehr interessanten Sortieralgorithmus beschäftigen, dem Selection Sort oder auf Deutsch dem Auswahlsortieren. Hallo, ich habe eine Idee, wie ich den Studierenden den Selection Sort erklären könnte. Ich kippe im Hörsaal eine Kiste Legosteine in verschiedenen Größen aus und bitte sie, sie nach der Anzahl der Noppen zu sortieren. Dazu sollen sie erst den Stein mit den wenigsten Noppen suchen und in eine Kiste legen, dann den mit den zweitwenigsten Noppen in die nächste Kiste und so weiter. Was hältst du davon?

**[Video 00:36–01:16](https://www.youtube.com/watch?v=IbZvEaUX61I&t=36)**

Das wäre dann aber kein Selection Sort und ganz ehrlich, ich glaube, du kannst die Zeit im Hörsaal sinnvoller verbringen. Ja, na gut, dann halt nicht. Fang einfach mal an. Lassen Sie uns nun die grundlegende Idee hinter dem Selection Sort betrachten. Der Algorithmus basiert auf einem sehr einfachen Prinzip. Wir finden das kleinste unsortierte Element und setzen es an den Anfang des noch unsortierten Bereichs. Schau, das ist so ähnlich wie bei meinem Lego-Beispiel. Schon, aber im Detail funktioniert der Selection Sort halt ganz anders als das, was du beschrieben hast. Also, stellen Sie sich vor, wir haben eine Reihe von unsortierten Zahlen. Der Selection Sort geht jetzt folgendermaßen vor: Wir durchsuchen die gesamte unsortierte Liste, um das kleinste Element zu finden.

**[Video 01:16–01:34](https://www.youtube.com/watch?v=IbZvEaUX61I&t=76)**

Dieses kleinste Element tauschen wir dann mit dem ersten Element des unsortierten Bereichs.

### Folie 3

[Folie 3 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=3)

Pseudocode

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 4 — Beispiel

[Folie 4 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=4)

5 2 1 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:16–01:34](https://www.youtube.com/watch?v=IbZvEaUX61I&t=76)**

Der sortierte Bereich wächst um eine Position und wir betrachten den Rest der Liste als unsortiert.

### Folie 5 — Beispiel

[Folie 5 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=5)

min

▾

5 2 1 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:16–01:34](https://www.youtube.com/watch?v=IbZvEaUX61I&t=76)**

Wir wiederholen diesen Prozess für den verbleibenden unsortierten Bereich.

### Folie 6 — Beispiel

[Folie 6 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=6)

min

▾

5 2 1 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:16–01:34](https://www.youtube.com/watch?v=IbZvEaUX61I&t=76)**

So bauen wir Schritt für Schritt eine sortierte Liste auf, indem wir immer das kleinste verbleibende Element

### Folie 7 — Beispiel

[Folie 7 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=7)

min

▾

5 2 1 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 8 — Beispiel

[Folie 8 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=8)

min

▾

5 2 1 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

an das Ende des bereits sortierten Teils setzen.

### Folie 9 — Beispiel

[Folie 9 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=9)

min

▾

5 2 1 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

Nun, da wir den grundlegenden Ablauf des Selection Sort verstanden haben, lassen Sie uns ein konkretes Beispiel betrachten.

### Folie 10 — Beispiel

[Folie 10 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=10)

min

▾

5 2 1 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

Wir haben hier eine Reihe von Zahlen: fünf, zwei, eins, drei, sechs, vier.

### Folie 11 — Beispiel

[Folie 11 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=11)

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

Wir werden Schritt für Schritt durch den Sortiervorgang gehen.

### Folie 12 — Beispiel

[Folie 12 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=12)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

Zunächst durchsuchen wir die gesamte Liste, um das kleinste Element zu finden.

### Folie 13 — Beispiel

[Folie 13 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=13)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

In diesem Fall ist es die eins.

### Folie 14 — Beispiel

[Folie 14 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=14)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

Wir tauschen sie mit dem ersten Element, der fünf.

### Folie 15 — Beispiel

[Folie 15 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=15)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

Jetzt sieht unsere Liste so aus: eins, zwei, fünf, drei, sechs, vier.

### Folie 16 — Beispiel

[Folie 16 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=16)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 01:34–02:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=94)**

Die eins ist nun sortiert und bildet den Anfang unseres sortierten Bereichs.

### Folie 17 — Beispiel

[Folie 17 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=17)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Im nächsten Durchgang betrachten wir nur noch den unsortierten Teil 2 5 3 6 4.

### Folie 18 — Beispiel

[Folie 18 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=18)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Das kleinste Element ist hier die 2, die bereits an der richtigen Position steht.

### Folie 19 — Beispiel

[Folie 19 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=19)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Wir müssen also nichts tauschen.

### Folie 20 — Beispiel

[Folie 20 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=20)

min

▾

1 2 5 3 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Wir fahren fort mit dem unsortierten Teil, also 5 3 6 4.

### Folie 21 — Beispiel

[Folie 21 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=21)

1 2 3 5 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Das kleinste Element ist die 3, die wir mit der 5 tauschen.

### Folie 22 — Beispiel

[Folie 22 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=22)

min

▾

1 2 3 5 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Unsere Liste sieht dann so aus: 1 2 3 5 6 4.

### Folie 23 — Beispiel

[Folie 23 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=23)

min

▾

1 2 3 5 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Lassen Sie uns den Sortiervorgang fortsetzen.

### Folie 24 — Beispiel

[Folie 24 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=24)

min

▾

1 2 3 5 6 4

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Wir sind bei der Konfiguration 1 2 3 5 6 4 angekommen.

### Folie 25 — Beispiel

[Folie 25 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=25)

1 2 3 4 6 5

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:05–02:36](https://www.youtube.com/watch?v=IbZvEaUX61I&t=125)**

Der unsortierte Bereich beginnt nun ab der vierten Position.

**[Video 02:36–03:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=156)**

Wir durchsuchen also fünf, sechs, vier nach dem kleinsten Element. Das ist die vier.

### Folie 26 — Beispiel

[Folie 26 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=26)

min

▾

1 2 3 4 6 5

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:36–03:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=156)**

Wir tauschen sie mit der fünf, sodass wir eins, zwei, drei, vier, sechs, fünf erhalten.

### Folie 27 — Beispiel

[Folie 27 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=27)

min

▾

1 2 3 4 6 5

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:36–03:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=156)**

Im nächsten Durchgang betrachten wir nur noch sechs und fünf.

### Folie 28 — Beispiel

[Folie 28 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=28)

1 2 3 4 5 6

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:36–03:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=156)**

Die fünf ist kleiner, also tauschen wir sie mit der sechs.

### Folie 29 — Beispiel

[Folie 29 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=29)

1 2 3 4 5 6

Wiederhole, bis keine unsortierten Elemente mehr vorhanden sind:

Durchsuche den unsortierten Teil der Daten, um den kleinsten Wert zu finden.

Vertausche den kleinsten gefundenen Wert mit dem ersten Element des unsortierten Teils.

#### Transkript

> Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet.

**[Video 02:36–03:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=156)**

Unser Array sieht nun so aus: eins, zwei, drei, vier, fünf, sechs.

### Folie 30 — Fälle

[Folie 30 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=30)

Worst Case: Im schlimmsten Fall müssen wir bei jedem Durchgang alle n Elemente des Arrays durchsuchen, um das kleinste Element zu finden. Diesen Prozess wiederholen wir n-mal, da wir in jedem Durchgang nur ein Element sortieren.

Best Case: Das Array ist bereits perfekt sortiert. Auch dann müssen wir bei jedem Durchgang alle n Elemente des Arrays durchsuchen, um das kleinste Element zu finden. Diesen Prozess wiederholen wir n-mal, da wir in jedem Durchgang nur ein Element sortieren.

#### Transkript

**[Video 02:36–03:05](https://www.youtube.com/watch?v=IbZvEaUX61I&t=156)**

Schließlich bleibt nur noch die sechs übrig, die bereits korrekt einsortiert ist. Damit ist unser Array vollständig sortiert. Man sieht ganz gut, dass der Algorithmus immer die gleichen Schritte durchführt, unabhängig davon, wie das ursprüngliche Array aussieht.

**[Video 03:05–03:41](https://www.youtube.com/watch?v=IbZvEaUX61I&t=185)**

Das wird gleich für die Laufzeitanalyse noch wichtig. Ganz genau. Lassen Sie uns über die Effizienz dieses Algorithmus sprechen. Wir betrachten dabei wieder zwei Szenarien: den schlimmsten Fall und den besten Fall. Im schlimmsten Fall müssen wir bei jedem Durchgang alle n Elemente des Arrays durchsuchen, um das kleinste Element zu finden. Diesen Prozess wiederholen wir n Mal, da wir in jedem Durchgang nur ein Element sortieren. Interessanterweise sieht der beste Fall genauso aus wie der schlimmste Fall. Selbst wenn das Array bereits sortiert wäre, müssten wir trotzdem jeden Durchgang vollständig ausführen, um sicherzustellen, dass wir das kleinste Element gefunden haben. Genau, das ist ein wichtiger Punkt.

### Folie 31

[Folie 31 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=31)

O(n²)

Laufzeitkomplexität

Ω(n²)

#### Transkript

**[Video 03:41–04:15](https://www.youtube.com/watch?v=IbZvEaUX61I&t=221)**

In der Praxis bedeutet das, dass die Laufzeit des Selection Sort vorhersehbar ist, unabhängig davon, wie die Daten angeordnet sind. Das kann in bestimmten Anwendungsfällen durchaus von Vorteil sein. Jetzt können wir die Laufzeitkomplexität des Selection Sort bestimmen. Wie wir gesehen haben, müssen wir in beiden Fällen n Elemente n Mal durchlaufen. Das kommt Ihnen vielleicht bekannt vor. In der Notation der Komplexitätstheorie ausgedrückt ergibt sich daraus eine Laufzeit von O von n Quadrat im schlechtesten Fall und Omega von n Quadrat im besten Fall. Das bedeutet, dass die Anzahl der Operationen quadratisch mit der Größe des Eingabearrays wächst.

### Folie 32

[Folie 32 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=32)

E X T R A S I N 3 M I N U T E N FRAGEN – ANTWORTEN – RÄTSEL UND KURZE ZUSAMMENFASSUNG

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 33

[Folie 33 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=33)

F1:

Was wird im Selection Sort „selected“?

F2:

Wie programmiert man denn die Suche nach dem kleinsten Wert in einem unsortierten Array?

#### Transkript

**[Video 04:15–04:31](https://www.youtube.com/watch?v=IbZvEaUX61I&t=255)**

Diese quadratische Laufzeit macht den Selection Sort für große Datenmengen ineffizient. Bevor wir schließen, kommen wir aber unbedingt noch zu den drei Extra Minuten, oder? Ich habe zwei Fragen heute mitgebracht. Hier ist die erste: Was wird im Selection Sort eigentlich selected?

**[Video 04:31–05:08](https://www.youtube.com/watch?v=IbZvEaUX61I&t=271)**

Im Selection Sort Algorithmus wird in jedem Durchgang das kleinste Element aus dem unsortierten Teil des Arrays ausgewählt. Dieses ausgewählte Element wird dann an die richtige Position im sortierten Teil des Arrays verschoben, indem es mit dem ersten Element des unsortierten Teils getauscht wird. Sehr gut. Nun zur zweiten Frage: Wie programmiert man denn die Suche nach dem kleinsten Wert am besten, wenn das Array noch unsortiert ist? Um den kleinsten Wert in einem unsortierten Array zu finden, können wir eine einfache Schleife verwenden, die durch alle Elemente läuft und den aktuell kleinsten Wert verfolgt. Hier ist ein Beispiel in C. Sehr gut. Ich denke, das reicht für heute.

**[Video 05:08–05:14](https://www.youtube.com/watch?v=IbZvEaUX61I&t=308)**

Ich auch. Bis bald. Dies war Inf-Einf-B.

### Folie 34

[Folie 34 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=34)

```c
int find_index_of_smallest(int arr[], int length)
{
    int indexOfSmallest = 0;
    for (int i = 1; i < length; i++)
    {
        if (arr[i] < arr[indexOfSmallest])
        {
            indexOfSmallest = i;
        }
    }
    return indexOfSmallest;
}
```

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*

### Folie 35 — Grundprinzip: Finde das

[Folie 35 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.4-selection-sort.pdf#page=35)

kleinste Element im unsortierten Bereich und tausche es mit dem ersten

Vorteil: Einfach zu implementieren und zu verstehen; vorhersagbare

Element des unsortierten

Laufzeit.

Bereichs.

Nachteil: Ineffizient bei

Der sortierte Bereich wächst

großen Datenmengen aufgrund der quadratischen

von links nach rechts, ein

Element pro Durchgang.

Laufzeit.

Praxistipp: Gut geeignet für kleine Arrays und Situationen, in denen Einfachheit wichtiger

Laufzeitkomplexität: O(n²) im

schlechtesten Fall, Ω(n²) im

besten Fall.

ist als Geschwindigkeit.

> Bildinhalte sind nicht transkribiert; siehe Originalfolie.

#### Transkript

*Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*