Selection Sort und Insertion Sort

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Ein Zeiger zeigt auf das erste Element.

  • Kleinsten Wert bestimmen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Ein Zeiger zeigt auf das erste Element. Das erste Element ist orange markiert.

  • Kleinsten Wert bestimmen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Ein Zeiger zeigt auf das zweite Element. Das erste Element ist orange markiert.

  • Kleinsten Wert bestimmen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Ein Zeiger zeigt auf das zweite Element. Das zweite Element ist orange markiert.

  • Kleinsten Wert bestimmen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Ein Zeiger zeigt auf das dritte Element. Das zweite Element ist orange markiert.

  • Kleinsten Wert bestimmen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Ein Zeiger zeigt auf das vierte Element. Das zweite Element ist orange markiert.

  • Kleinsten Wert bestimmen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Ein Zeiger zeigt auf das vierte Element. Das vierte Element ist orange markiert.

  • Kleinsten Wert bestimmen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Ein Zeiger zeigt auf das fünfte Element. Das vierte Element ist orange markiert.

  • Kleinsten Wert bestimmen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das vierte Element ist orange markiert. Zwei Pfeile zeigen, dass das erste und das vierte Element getauscht werden.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste Element ist orange markiert. Das erste und das vierte Element wurden getauscht.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste Element ist blau, das zweite orange markiert. Ein Zeiger zeigt auf das zweite Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste Element ist blau, das zweite orange markiert. Ein Zeiger zeigt auf das dritte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste Element ist blau, das zweite orange markiert. Ein Zeiger zeigt auf das vierte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau markiert. Ein Zeiger zeigt auf das dritte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau markiert. Ein Zeiger zeigt auf das dritte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau, das dritte orange markiert. Ein Zeiger zeigt auf das dritte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau, das dritte orange markiert. Ein Zeiger zeigt auf das vierte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau, das vierte orange markiert. Ein Zeiger zeigt auf das vierte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau, das vierte orange markiert. Ein Zeiger zeigt auf das fünfte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau, das vierte orange markiert. Zwei Pfeile zeigen, dass das dritte und vierte Element getauscht werden.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau, das dritte orange markiert. Das dritte und das vierte Element wurden getauscht.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau markiert. Ein Zeiger zeigt auf das vierte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau, das vierte orange markiert. Ein Zeiger zeigt auf das vierte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau, das vierte orange markiert. Ein Zeiger zeigt auf das fünfte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau, das fünfte orange markiert. Ein Zeiger zeigt auf das fünfte Element.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau, das fünfte orange markiert. Zwei Pfeile zeigen, dass das vierte und fünfte Element getauscht werden.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau, das vierte orange markiert. Das vierte und fünfte Element wurden getauscht.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite, dritte und vierte Element sind blau markiert.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Alle Elemente sind blau markiert.

  • Kleinsten Wert bestimmen
  • Kleinsten Wert mit dem ersten unsortierten Element tauschen
Datenstrukturen und Algorithmen in Python

Selection Sort – Implementierung

def selection_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length - 1):

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list
Datenstrukturen und Algorithmen in Python

Selection Sort – Komplexität

  • Schlechtester Fall: $O(n^2)$
  • Durchschnitt: $\Theta(n^2)$
  • Bester Fall: $\Omega(n^2)$
Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste Element ist blau, das zweite wurde angehoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste Element ist blau, das zweite wurde angehoben. Das erste Element wurde nach rechts verschoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das zweite Element ist blau. Das angehobene Element steht nun an erster Position.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau markiert.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste und zweite Element sind blau markiert. Das dritte Element wurde angehoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau markiert.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau markiert. Das dritte Element wurde angehoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau markiert. Das dritte Element wurde angehoben. Das dritte Element wurde nach rechts verschoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau markiert. Das dritte Element wurde angehoben. Das dritte und zweite Element wurden nach rechts verschoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau markiert. Das dritte Element wurde angehoben. Das dritte, zweite und dritte Element wurden nach rechts verschoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite und dritte Element sind blau markiert. Das dritte Element wurde angehoben. Das dritte, zweite und dritte Element wurden nach rechts verschoben. Das angehobene Element steht nun an erster Position.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite, dritte und vierte Element sind blau markiert.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite, dritte und vierte Element sind blau markiert. Das fünfte Element wurde angehoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite, dritte und vierte Element sind blau markiert. Das fünfte Element wurde angehoben. Das vierte Element wurde nach rechts verschoben.

Datenstrukturen und Algorithmen in Python

Insertion Sort

Schematische Darstellung einer Liste mit unsortierten Zahlen. Das erste, zweite, dritte und vierte Element sind blau markiert. Das fünfte Element wurde angehoben. Das angehobene Element steht nun an vierter Position.

Datenstrukturen und Algorithmen in Python

Insertion Sort – Implementierung

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list
Datenstrukturen und Algorithmen in Python

Insertion Sort – Komplexität

  • Schlechtester Fall: $O(n^2)$
  • Durchschnitt: $\Theta(n^2)$
  • Bester Fall: $\Omega(n)$
Datenstrukturen und Algorithmen in Python

Lass uns üben!

Datenstrukturen und Algorithmen in Python

Preparing Video For Download...