Quicksort

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Quicksort

  • Följer principen dela och härska
  • Används av många programmeringsspråk
  • Partitionering
    • Pivot
    • element mindre än pivot -> vänster
    • element större än pivot -> höger
  • Element till vänster sorteras rekursivt
  • Element till höger sorteras rekursivt
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal.

Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått.

  • Hoares partitionering
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Den vänstra pekaren pekar på det andra elementet och den högra pekaren på det sista elementet.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Den vänstra pekaren pekar på det tredje elementet och den högra pekaren på det sista elementet.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Den vänstra pekaren pekar på det tredje elementet och den högra pekaren på det femte elementet.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Den vänstra pekaren pekar på det tredje elementet och den högra pekaren på det femte elementet. Två pilar visar att det tredje och femte elementet kommer att bytas.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Den vänstra pekaren pekar på det tredje elementet och den högra pekaren på det femte elementet. Det tredje och femte elementet har bytats.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Den vänstra pekaren pekar på det fjärde elementet och den högra pekaren på det femte elementet.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Både den vänstra och den högra pekaren pekar på det fjärde elementet.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Den vänstra pekaren pekar på det fjärde elementet och den högra pekaren på det tredje elementet.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått. Det finns två pekare. Den vänstra pekaren pekar på det fjärde elementet och den högra pekaren på det tredje elementet. Två pilar visar att det första och tredje elementet kommer att bytas.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det tredje elementet är markerat i blått. Det första och tredje elementet har bytats.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det tredje elementet är markerat i grönt.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det tredje elementet är markerat i grönt och de två första elementen i orange, vilket representerar listans vänstra del.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått, det andra i orange och det tredje i grönt. Vänster och höger pekare pekar på det andra elementet.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått, det andra i orange och det tredje i grönt. Vänster och höger pekare pekar på det andra elementet. Två pilar visar att det första och andra elementet kommer att bytas.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i blått, det andra i orange och det tredje i grönt. Vänster och höger pekare pekar på det andra elementet. Det första och andra elementet har bytats.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första elementet är markerat i orange och det andra och tredje elementet i grönt.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra och tredje elementet är markerade i grönt.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra och tredje elementet är markerade i grönt. Listans högra del är markerad i orange.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra och tredje elementet är markerade i grönt. Det första elementet i den högra delen är markerat i blått. Den vänstra pekaren pekar på det andra elementet i den högra delen och den högra pekaren på det sista elementet i den högra delen.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra och tredje elementet är markerade i grönt. Det första elementet i den högra delen är markerat i blått. Både vänster och höger pekare pekar på det andra elementet i listans högra del.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra och tredje elementet är markerade i grönt. Det första elementet i den högra delen är markerat i blått. Den vänstra pekaren pekar på det första elementet i den högra delen och den högra pekaren på det andra elementet i den högra delen.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra, tredje och fjärde elementet är markerade i grönt, och det femte och sjätte elementet i orange.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra, tredje och fjärde elementet är markerade i grönt. Ett element är markerat i blått. Vänster och höger pekare pekar på det sista elementet.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra, tredje och fjärde elementet är markerade i grönt. Ett element är markerat i blått. Vänster och höger pekare pekar på det sista elementet. Två pilar visar att det femte och sjätte elementet kommer att bytas.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Det första, andra, tredje och fjärde elementet är markerade i grönt. Ett element är markerat i blått. Vänster och höger pekare pekar på det sista elementet. Det femte och sjätte elementet har bytats.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – i praktiken

En schematisk bild av en lista med oordnade tal. Alla element är markerade i grönt eftersom de är sorterade.

  • Hoares partitionering
    • Flytta vänster pekare tills ett värde större än pivot hittas
    • Flytta höger pekare tills ett värde mindre än pivot hittas
Datastrukturer och algoritmer i Python

Quicksort – implementation

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)
Datastrukturer och algoritmer i Python

Quicksort – implementation

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
Datastrukturer och algoritmer i Python

Quicksort – implementation

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]
Datastrukturer och algoritmer i Python

Quicksort – komplexitet

  • Värsta fall: $O(n^2)$
  • Mycket effektiv!
    • Genomsnittligt fall: $\Theta(n\log{}n)$
    • Bästa fall: $\Omega(n\log{}n)$
  • Minneskomplexitet: $O(n\log{}n)$
Datastrukturer och algoritmer i Python

Nu kör vi en övning!

Datastrukturer och algoritmer i Python

Preparing Video For Download...