Bubblesort

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Sortieralgorithmen

  • Gründlich erforscht
  • Problem: unsortierte Sammlung auf-/absteigend sortieren
  • Kann Problemkomplexität verringern
  • Beispiele für Sortieralgorithmen:
    • Bubblesort
    • Selection Sort
    • Insertion Sort
    • Mergesort
    • Quicksort
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das erste Element, ein weiterer auf das zweite.

  • Erstes > zweites Element
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das erste Element, ein weiterer auf das zweite. Das erste und das zweite Element wurden vertauscht.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das zweite Element, ein weiterer auf das dritte.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das dritte Element, ein weiterer auf das vierte.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das dritte Element, ein weiterer auf das vierte. Das dritte und das vierte Element wurden vertauscht.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das vierte Element, ein weiterer auf das fünfte.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das vierte Element, ein weiterer auf das fünfte. Das vierte und das fünfte Element wurden vertauscht.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das vierte Element, ein weiterer auf das fünfte. Das fünfte Element ist blau markiert, da es einsortiert ist.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das erste Element, ein weiterer auf das zweite. Das letzte Element ist blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das zweite Element, ein weiterer auf das dritte. Das letzte Element ist blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das zweite Element, ein weiterer auf das dritte. Das zweite und das dritte Element wurden vertauscht. Das letzte Element ist blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das dritte Element, ein weiterer auf das vierte. Das letzte Element ist blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das dritte Element, ein weiterer auf das vierte. Die letzten zwei Elemente sind blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das erste Element, ein weiterer auf das zweite. Die letzten zwei Elemente sind blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das erste Element, ein weiterer auf das zweite. Das erste und das zweite Element wurden vertauscht. Die letzten zwei Elemente sind blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das zweite Element, ein weiterer auf das dritte. Die letzten zwei Elemente sind blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das zweite Element, ein weiterer auf das dritte. Die letzten drei Elemente sind blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das erste Element, ein weiterer auf das zweite. Die letzten drei Elemente sind blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das erste Element, ein weiterer auf das zweite. Die letzten vier Elemente sind blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort

Schematische Darstellung einer Liste mit ungeordneten Zahlen. Ein Zeiger zeigt auf das erste Element, ein weiterer auf das zweite. Alle Elemente sind blau markiert.

  • Erstes > zweites Element
    • Tauschen
  • Zweites > erstes Element
    • Nichts
Datenstrukturen und Algorithmen in Python

Bubblesort – Implementierung

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

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]
Datenstrukturen und Algorithmen in Python

Bubblesort – Implementierung

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list
Datenstrukturen und Algorithmen in Python

Bubblesort – Komplexität

  • Schlechtester Fall: $O(n^2)$
  • Bester Fall – nicht optimiert: $\Omega(n^2)$
  • Bester Fall – optimiert: $\Omega(n)$
  • Durchschnitt: $\Theta(n^2)$
  • Schwach bei stark unsortierten großen Listen
  • Gut bei:
    • großen (fast) sortierten Listen
    • kleinen Listen
Datenstrukturen und Algorithmen in Python

Lass uns üben!

Datenstrukturen und Algorithmen in Python

Preparing Video For Download...