Bubblesort

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Sorteeralgoritmen

Grondig onderzocht
Oplossen hoe je een ongesorteerde collectie oplopend/aflopend kunt sorteren
Kan complexiteit verlagen
Voorbeelden:
- bubblesort
- selection sort
- insertion sort
- merge sort
- quicksort

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het eerste element en een andere naar het tweede element.

Eerste waarde > tweede waarde

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het eerste element en een andere naar het tweede element. Het eerste en tweede element zijn verwisseld.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het tweede element en een andere naar het derde element.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het derde element en een andere naar het vierde element.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het derde element en een andere naar het vierde element. Het derde en vierde element zijn verwisseld.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het vierde element en een andere naar het vijfde element.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het vierde element en een andere naar het vijfde element. Het vierde en vijfde element zijn verwisseld.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het vierde element en een andere naar het vijfde element. Het vijfde element is blauw gekleurd omdat het op orde is.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het eerste element en een andere naar het tweede element. Het laatste element is blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het tweede element en een andere naar het derde element. Het laatste element is blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het tweede element en een andere naar het derde element. Het tweede en derde element zijn verwisseld. Het laatste element is blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het derde element en een andere naar het vierde element. Het laatste element is blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het derde element en een andere naar het vierde element. De laatste twee elementen zijn blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het eerste element en een andere naar het tweede element. De laatste twee elementen zijn blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het eerste element en een andere naar het tweede element. Het eerste en tweede element zijn verwisseld. De laatste twee elementen zijn blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het tweede element en een andere naar het derde element. De laatste twee elementen zijn blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het tweede element en een andere naar het derde element. De laatste drie elementen zijn blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het eerste element en een andere naar het tweede element. De laatste drie elementen zijn blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het eerste element en een andere naar het tweede element. De laatste vier elementen zijn blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort

Een schematische weergave van een lijst met ongesorteerde getallen. Eén pointer wijst naar het eerste element en een andere naar het tweede element. Alle elementen zijn blauw gekleurd.

Eerste waarde > tweede waarde
- Verwissel
Tweede waarde > eerste waarde
- Niets

Bubblesort - implementatie

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]

Bubblesort - implementatie

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

Bubblesort - complexiteit

Slechtste geval: $O(n^2)$
Beste geval - niet-verbeterde versie: $\Omega(n^2)$
Beste geval - verbeterde versie: $\Omega(n)$
Gemiddeld: $\Theta(n^2)$
Slecht bij sterk ongesorteerde grote lijsten
Goed bij:
- grote (bijna) gesorteerde lijsten
- kleine lijsten

Laten we oefenen!

Datastructuren en algoritmen in Python