Bubbel­sortering

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Sorteringsalgoritmer

  • Noggrant studerade
  • Löser hur man sorterar en osorterad samling i stigande/fallande ordning
  • Kan minska komplexiteten hos problem
  • Några sorteringsalgoritmer:
    • bubbelsortering
    • urvalssortering
    • insättningssortering
    • sammanfogningssortering
    • quicksort
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det första elementet och en annan pekare pekar på det andra elementet.

  • Första värdet är större än det andra
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det första elementet och en annan pekare pekar på det andra elementet. Det första och det andra elementet har bytts om.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det andra elementet och en annan pekare pekar på det tredje elementet.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det tredje elementet och en annan pekare pekar på det fjärde elementet.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det tredje elementet och en annan pekare pekar på det fjärde elementet. Det tredje och det fjärde elementet har bytts om.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det fjärde elementet och en annan pekare pekar på det femte elementet.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det fjärde elementet och en annan pekare pekar på det femte elementet. Det fjärde och det femte elementet har bytts om.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det fjärde elementet och en annan pekare pekar på det femte elementet. Det femte elementet är markerat i blått eftersom det är sorterat.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det första elementet och en annan pekare pekar på det andra elementet. Det sista elementet är markerat i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det andra elementet och en annan pekare pekar på det tredje elementet. Det sista elementet är markerat i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det andra elementet och en annan pekare pekar på det tredje elementet. Det andra och det tredje elementet har bytts om. Det sista elementet är markerat i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det tredje elementet och en annan pekare pekar på det fjärde elementet. Det sista elementet är markerat i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det tredje elementet och en annan pekare pekar på det fjärde elementet. De två sista elementen är markerade i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det första elementet och en annan pekare pekar på det andra elementet. De två sista elementen är markerade i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det första elementet och en annan pekare pekar på det andra elementet. Det första och det andra elementet har bytts om. De två sista elementen är markerade i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det andra elementet och en annan pekare pekar på det tredje elementet. De två sista elementen är markerade i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det andra elementet och en annan pekare pekar på det tredje elementet. De tre sista elementen är markerade i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det första elementet och en annan pekare pekar på det andra elementet. De tre sista elementen är markerade i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det första elementet och en annan pekare pekar på det andra elementet. De fyra sista elementen är markerade i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering

En schematisk bild av en lista med osorterade tal. En pekare pekar på det första elementet och en annan pekare pekar på det andra elementet. Alla element är markerade i blått.

  • Första värdet är större än det andra
    • Byt plats
  • Andra värdet är större än det första
    • Gör ingenting
Datastrukturer och algoritmer i Python

Bubbelsortering – implementation

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

Bubbelsortering – implementation

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

Bubbelsortering – komplexitet

  • Värsta fall: $O(n^2)$
  • Bästa fall – ej förbättrad version: $\Omega(n^2)$
  • Bästa fall – förbättrad version: $\Omega(n)$
  • Genomsnittligt fall: $\Theta(n^2)$
  • Fungerar dåligt för stora, kraftigt osorterade listor
  • Fungerar bra för:
    • stora sorterade/nästan sorterade listor
    • små listor
Datastrukturer och algoritmer i Python

Nu kör vi en övning!

Datastrukturer och algoritmer i Python

Preparing Video For Download...