Quicksort

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Quicksort

Volgt het divide-and-conquer-principe
Geïmplementeerd in veel programmeertalen
Partitioneer-techniek
- Pivot
- items kleiner dan de pivot -> links
- items groter dan de pivot -> rechts
Elementen links worden recursief gesorteerd
Elementen rechts worden recursief gesorteerd

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen.

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw.

Hoare-partitionering

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw. Er zijn twee pointers. De linker wijst naar het tweede element en de rechter naar het laatste.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw. Er zijn twee pointers. De linker wijst naar het derde element en de rechter naar het laatste.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw. Er zijn twee pointers. De linker wijst naar het derde element en de rechter naar het vijfde.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw. Er zijn twee pointers. De linker wijst naar het derde element en de rechter naar het vijfde. Twee pijlen geven aan dat het derde en vijfde element worden verwisseld.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw. Er zijn twee pointers. De linker wijst naar het vierde element en de rechter naar het vijfde.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw. Er zijn twee pointers. De linker wijst naar het vierde element en de rechter ook naar het vierde.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw. Er zijn twee pointers. De linker wijst naar het vierde element en de rechter naar het derde.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw. Er zijn twee pointers. De linker wijst naar het vierde element en de rechter naar het derde. Twee pijlen geven aan dat het eerste en derde element worden verwisseld.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het derde element is blauw. Het eerste en derde element zijn verwisseld.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het derde element is groen.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het derde element is groen en de eerste twee zijn oranje, wat het linker deel aangeeft.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw, het tweede oranje en het derde groen. De linker en rechter pointers wijzen naar het tweede element.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is blauw, het tweede oranje en het derde groen. De linker en rechter pointers wijzen naar het tweede element. Twee pijlen geven aan dat het eerste en tweede element worden verwisseld.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste element is oranje en het tweede en derde zijn groen.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn groen.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn groen. Het rechter deel van de lijst is oranje.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn groen. Het eerste element van het rechter deel is blauw. De linker pointer wijst naar het tweede element van het rechter deel en de rechter naar het laatste element van het rechter deel.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn groen. Het eerste element van het rechter deel is blauw. De linker en rechter pointers wijzen naar het tweede element van het rechter deel.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede en derde element zijn groen. Het eerste element van het rechter deel is blauw. De linker pointer wijst naar het eerste element van het rechter deel en de rechter naar het tweede.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede, derde en vierde element zijn groen, en het vijfde en zesde oranje.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Het eerste, tweede, derde en vierde element zijn groen. Het element is blauw. De linker en rechter pointers wijzen naar het laatste element.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - aan het werk

Een schematische weergave van een lijst met ongesorteerde getallen. Alle elementen zijn groen omdat ze gesorteerd zijn.

Hoare-partitionering
- Verplaats de linker pointer tot je een waarde groter dan de pivot vindt
- Verplaats de rechter pointer tot je een waarde kleiner dan de pivot vindt

Quicksort - implementatie

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 - implementatie

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 - implementatie

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 - complexiteit

Slechtste geval: $O(n^2)$
Zeer efficiënt!
- Gemiddeld: $\Theta(n\log{}n)$
- Beste geval: $\Omega(n\log{}n)$
Geheugengebruik: $O(n\log{}n)$

Laten we oefenen!

Datastructuren en algoritmen in Python