Quicksort

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Quicksort

Folgt dem Prinzip Teile und herrsche
In vielen Programmiersprachen implementiert
Partitionierung
- Pivot
- Elemente kleiner als Pivot -> links
- Elemente größer als Pivot -> rechts
Elemente links werden rekursiv sortiert
Elemente rechts werden rekursiv sortiert

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen.

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert.

Hoare-Partition

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert. Es gibt zwei Zeiger. Der linke zeigt auf das zweite Element und der rechte auf das letzte.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert. Es gibt zwei Zeiger. Der linke zeigt auf das dritte Element und der rechte auf das letzte.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert. Es gibt zwei Zeiger. Der linke zeigt auf das dritte Element, der rechte auf das fünfte.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert. Es gibt zwei Zeiger. Der linke zeigt auf das dritte Element, der rechte auf das fünfte. Zwei Pfeile zeigen, dass das dritte und fünfte Element getauscht werden.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert. Es gibt zwei Zeiger. Der linke zeigt auf das vierte Element und der rechte auf das fünfte.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert. Es gibt zwei Zeiger. Der linke zeigt auf das vierte Element und der rechte auf das vierte.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert. Es gibt zwei Zeiger. Der linke zeigt auf das vierte Element und der rechte auf das dritte.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau markiert. Es gibt zwei Zeiger. Der linke zeigt auf das vierte Element und der rechte auf das dritte. Zwei Pfeile zeigen, dass das erste und das dritte Element getauscht werden.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das dritte Element ist blau markiert. Das erste und dritte Element wurden getauscht.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das dritte Element ist grün markiert.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das dritte Element ist grün markiert und die ersten zwei Elemente sind orange – der linke Teil der Liste.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau, das zweite orange, das dritte grün. Linker und rechter Zeiger zeigen auf das zweite Element.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist blau, das zweite orange, das dritte grün. Linker und rechter Zeiger zeigen auf das zweite Element. Zwei Pfeile zeigen, dass das erste und zweite Element getauscht werden.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste Element ist orange, das zweite und dritte sind grün.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste, zweite und dritte Element sind grün.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste, zweite und dritte Element sind grün. Der rechte Teil der Liste ist orange.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste, zweite und dritte Element sind grün. Das erste Element des rechten Teils ist blau markiert. Der linke Zeiger zeigt auf das zweite Element des rechten Teils und der rechte auf das letzte Element des rechten Teils.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste, zweite und dritte Element sind grün. Das erste Element des rechten Teils ist blau markiert. Linker und rechter Zeiger zeigen auf das zweite Element des rechten Teils.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste, zweite und dritte Element sind grün. Das erste Element des rechten Teils ist blau markiert. Der linke Zeiger zeigt auf das erste Element des rechten Teils und der rechte auf das zweite Element des rechten Teils.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste, zweite, dritte und vierte Element sind grün, das fünfte und sechste orange.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Das erste, zweite, dritte und vierte Element sind grün. Ein Element ist blau markiert. Linker und rechter Zeiger zeigen auf das letzte Element.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – in Aktion

Ein schematisches Diagramm einer Liste mit ungeordneten Zahlen. Alle Elemente sind grün markiert, da sie sortiert sind.

Hoare-Partition
- Bewege den linken Zeiger bis ein Wert größer als der Pivot ist
- Bewege den rechten Zeiger bis ein Wert kleiner als der Pivot ist

Quicksort – Implementierung

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)

Quicksort – Implementierung

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer

Quicksort – Implementierung

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]

Quicksort – Komplexität

Schlechtester Fall: $O(n^2)$
Sehr effizient!
- Durchschnitt: $\Theta(n\log{}n)$
- Bester Fall: $\Omega(n\log{}n)$
Speicherbedarf: $O(n\log{}n)$

Lass uns üben!

Datenstrukturen und Algorithmen in Python